Тема ТЕОРИЯ ЧИСЕЛ

Делимость и делители (множители) → .02 Разложение на множители, основная теорема арифметики

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Делимость и делители (множители)

Условия про НОД и НОК

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

Оценки для доказательства делимости

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 21#131890Максимум баллов за задание: 7

Каждое натуральное число, большее 1000, окрасили либо в красный, либо в синий цвет. Оказалось, что произведение любых двух различных красных чисел — синее. Может ли случиться, что никакие два синих числа не отличаются на 1?

Источники: ВСОШ, ЗЭ, 2023, 9.3 (см. olympiads.mccme.ru)

Показать ответ и решение

Первое решение. Предположим противное. Пусть существует такая раскраска натуральных чисел больше 1000 в красный и синий цвета, что произведение любых двух различных красных чисел синее, и никакие два синих числа не отличаются на 1.

Если число $n$ синее, то числа $n− 1$ и $n+ 1$ обязаны быть красными. Тогда их произведение $2 (n − 1)(n +1)= n − 1$ должно быть синим, а значит, $2 n$ должно быть красным.

Возьмём любое синее число $k> 1001.$ Тогда $2 k$ красное. Если $3 k$ синее, то $6 32 k =(k )$ красное. Но $6 2 4 k = k ⋅k,$ где $2 k$ и $6 k$ красные, значит, $4 k$ должно быть синим. Тогда $8 42 k =(k )$ красное, но $8 2 6 k = k ⋅k$ — произведение красных чисел, что невозможно.

Если же $3 k$ красное, то $5 2 3 k =k ⋅k$ синее, а $10 52 k =(k )$ красное. Так как

k10 = k2⋅k8 = k3 ⋅k7,

где $2 k$ и $3 k$ красные, то $7 k$ и $8 k$ должны быть синими. Тогда $14 7 2 k = (k)$ и $16 82 k = (k)$ красные, но $16 2 14 k =k ⋅k$ — произведение красных чисел, что приводит к противоречию.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что такая раскраска существует. Если $a$ и $b$ различные красные числа, то $ab$ синее, а $ab+ 1$ красное.

Цвета не могут строго чередоваться по чётности, поэтому найдутся два красных числа $a$ и $a+ 1$ одинаковой чётности. Тогда $b= a(a+1)+ 1$ красное,

c= ab+ 1= a3+a2+ a+ 1

красное, а

4 3 2 d= (a+ 1)c=a + 2a +2a + 2a+ 1

синее.

С другой стороны,

p =(a+ 1)b+ 1= a3+ 2a2+ 2a+ 2

красное, значит,

ap =a4+ 2a3+2a2+ 2a= d− 1

синее. Получаем соседние синие числа $d$ и $d− 1,$ что противоречит условию.

Ответ:

не может

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 22#31010Максимум баллов за задание: 7

На гранях куба записали натуральные числа. Затем в каждую вершину записали произведение чисел на трёх прилегающих к ней гранях. Сумма чисел в вершинах равна $1001$ . Чему равна сумма чисел на гранях?

Подсказки к задаче

Подсказка 1

Попробуем посмотреть, что за сумма у нас получилась. Из каких переменных состоит каждая из них, можно ли переформулировать это на язык комбинаторики?

Подсказка 2

Верно, можно сказать, что мы из трёх скобок вида (x+y) выбирали по переменной и в итоге получилось сумма их произведений. Теперь вспомним, как раскладывается число на простые множители и сколькими способами?

Подсказка 3

Ага, по основной теореме арифметики это делается единственным способом. Но тогда осталось только понять, почему скобка не может быть равна единице.

Показать ответ и решение

Пусть на противоположных гранях были числа $a 1$ и $a 2$ , $b 1$ и $b 2$ , $c 1$ и $c 2$ . Тогда заметим, что произведение любых трёх разных букв будет написано в одной из вершин ровно по одному разу, то есть сумма в вершинах равна $(a1+a2)(b1+ b2)(c1+ c2)= 1001= 11 ⋅7 ⋅13$ . Каждая сумма натуральных чисел не меньше $2$ , а произведение раскладывается в произведение трёх чисел, больших единицы, единственным способом. Значит, одна из сумм $(a1+ a2), (b1+ b2), (c1+ c2)$ равна $11$ , другая $7$ и третья $13$ , поэтому $(a1+ a2)+ (b1+ b2)+ (c1+ c2)=11+ 7+ 13= 31$ .

Ответ:

$31$

Ошибка.
Попробуйте повторить позже

Задача 23#31291Максимум баллов за задание: 7

Несколько натуральных чисел перемножили, и получилось $1120.$ Что это были за числа, если самое большое из них вдвое больше самого маленького?

Подсказки к задаче

Подсказка 1

Рассмотрите разложение 1120 на простые множители

Подсказка 2

Какие значения может принимать наименьшее из перемноженных чисел?

Подсказка 3

Оно не может делиться на 5 или 7, так как тогда 1120 делилось бы на 25 или 49. Значит, оно делится только на 2

Показать ответ и решение

Разложим на множители наше число

2 5 1120= 2⋅5⋅112 =2 ⋅5⋅56= 2 ⋅5⋅7

Пусть наши числа это $a1 ≤a2 ≤ ...≤ an.$ Тогда $2a1 =an$ и $1120= a1a2...an = 12a2...an− 1a2n.$ Если $a1...7,$ то $an ...7$ и тогда $1120= a1a2...an ...49.$ Аналогично, $a1$ не делится на $5.$ Значит $a1$ это степень $2.$

1.: Пусть $a1 = 1,$ тогда $ai ≤ an = 2$ и ни одно из чисел не делится на $5.$
2.: Пусть $a1 = 2,$ тогда $a≤ an = 4 i$ и ни одно из чисел не делится на $5.$
3.: Пусть $a =4, 1$ тогда $4≤ a ≤a =8. i n$ Тогда одно из чисел должно делится на $5,$ между $4$ и $8$ такое одно — $5,$ так же одно из чисел должно делится на $7,$ между $4$ и $8$ такое одно — $7.$ Таким образом среди чисел должно быть числа $4,8,5,7.$ Их произведение равно $1120,$ значит у нас всего $4$ числа $4,8,5,7.$
4.: Пусть $.. a1.8,$ тогда $.. an.16$ и ни одно из чисел не делится на $5,$ но тогда $.. 7 a1a2...an = 1120.2 .$

Ответ:

$4,5,7,8$

Ошибка.
Попробуйте повторить позже

Задача 24#31293Максимум баллов за задание: 7

Найдите наименьшее натуральное число, половина которого — точный куб, а треть — точный квадрат.

Подсказки к задаче

Подсказка 1

Посмотрите на разложение такого числа на простые.

Подсказка 2

Посмотрите на степени вхождения 2 и 3 в разложении числа на простые

Подсказка 3

Пусть 2 входит в число в степени a, 3 входит в степени b. Тогда условие говорит, что:
a и b - 1 четные
a - 1 и b делятся на 3

Показать ответ и решение

Наше число точно должно делится на $2$ и на $3.$ Пусть $2$ входит в наше число в степени $a,$ а $3$ в степени $b.$ Если число является квадратом, то все простые входят в него в четной степени, то есть $.. .. a.2,(b − 1).2.$ Если число является кубом, то все простые входят в него в степени, кратной $3,$ то есть $.. .. (a− 1).3,b.3.$

Таким образом, из условия, что $.. b.3$ следует, что $b≥ 3$ и $b= 3$ подходит под оба условия на $b,$ из условия, что $.. a− 1.3$ следует, что либо $a =1,$ что не подходит, так как $.. a.2,$ либо $a≥ 4$ и $a= 4$ подходит под оба условия на $a.$

Итого, наше число точно $4 3 ≥ 2 ⋅3.$

Заметим, что число $4 3 2 ⋅3 =432$ уже подходит под условие.

Ответ:

$432$

Ошибка.
Попробуйте повторить позже

Задача 25#31298Максимум баллов за задание: 7

На сколько нулей заканчивается число $100!?$

Подсказки к задаче

Подсказка 1

Количество нулей на конце числа равно максимальной степени 10, на которую оно делится.

Подсказка 2

Число делится на 10^n тогда и только тогда, когда оно делится на 2^n и 5^n

Подсказка 3

Посмотрите на степени вхождения пятерки и двойки в факториал!

Подсказка 4

Степень вхождения простого p в n! можно посчитать так:
d = [n / p] + [n / p²] + [n / p³] + ...
[x] - целая часть числа x

Подсказка 5

Нам достаточно посчитать степень вхождения 5 в факториал - степень вхождения 2 будет не меньше

Показать ответ и решение

Посчитаем, в какой степени пятёрка входит в число $100!:$

[100] [100] [100] -5- + -25 + 125 = 24

Посчитаем, в какой степени двойка входит в $100!:$

[ ] [ ] 100 + 100- +...>24 2 4

Значит, $100!$ заканчивается на $24$ нуля.

Замечание.Такие формулы для поиска степени вхождения получаются последовательным подсчётом количества чисел, кратных $pk$ ( $p$ — простое), которые не превышают $100,$ тогда степень $k$ будет посчитана $k$ раз, что равно степени, которая ей добавляется в произведение.

Ответ:

$24$

Ошибка.
Попробуйте повторить позже

Задача 26#31300Максимум баллов за задание: 7

Можно ли расставить по кругу $333$ различных натуральных числа так, чтобы для любых двух соседних чисел отношение большего из них к меньшему было простым числом?

Подсказки к задаче

Подсказка 1

В подобных задачах с кругом часто можно прийти к противоречию, либо же придумать пример, если выбрать произвольное число и сделать обход круга, рассматривая соседние наборы чисел, чтобы подойти к этому числу с другой стороны. Подумайте, как можно применить такой метод в этой задаче.

Подсказка 2

Выберем произвольное число и будем обходить круг в одну сторону. Заметим, что каждое соседнее число получается умножением или делением предыдущего на простое число. Когда мы дойдём до исходного числа, мы сделаем 333 операции. Возникает ли здесь какое-то противоречие?

Подсказка 3

Конечно, ведь если мы n раз умножали, то, чтобы прийти к исходному числу, надо n раз поделить, т.е. общее кол-во операций чётное. А мы сделали нечётное кол-во — 333!

Показать ответ и решение

Первое решение.

Предположим, что это возможно. Тогда давайте для каждого числа $α1 α2 αk n =p1 p2 ...pk ,$ стоящего по кругу, напишем рядом число $α1+ α2+ ...+ αk.$ Оставим теперь только новые числа. Раз для любых двух изначальных соседних чисел отношение большего из них к меньшему было простым числом, то теперь для новых чисел верно, что любые два соседних числа отличаются на $1.$ Такого не может быть, так как числа стоят по кругу и их нечетное число.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Рассмотрим произвольное число $n$ из круга. "Пройдём"по всем числам в одну сторону по кругу. При переходе к соседнему числу нужно умножить или разделить на простое число. Через $333$ шага мы должны прийти к изначальному числу $n.$ Но так как мы умножали и делили $333$ раза, то получить тот же результат не удастся: каждому умножению на простое число должно соответствовать последующее когда-то деление на то же число.

Ответ: нет

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 27#31303Максимум баллов за задание: 7

а) Существуют ли пять натуральных чисел таких, что ни одно из них не делится на другое, но квадрат любого числа делится на каждое из остальных?

б) Существуют ли пять натуральных чисел таких, что ни одно из них не делится на другое, но квадрат любого числа делится на произведение остальных?

Подсказки к задаче

Пункт а), подсказка 1

Попробуем построить пример, может быть, такое возможно. Логично рассмотреть какой-то набор простых чисел и попробовать из них поконструировать пять чисел.

Пункт а), подсказка 2

Пусть есть простые числа p₁, p₂, p₃, p₄, p₅. Пусть каждое из пяти чисел включает в своё разложение на простые произведение p₁p₂p₃p₄p₅. Можно ли подкорректировать числа, чтобы выполнялось условие?

Пункт а), подсказка 3

Оказывается, что да. Действительно, пусть первое число есть p₁²p₂p₃p₄p₅, второе — p₁p₂²p₃p₄p₅ и т.д. Тогда условие выполнено!

Пункт б), подсказка 1

Пусть есть такие числа a, b, c, d, e. Тогда запишите условие для квадрата каждого числа, что из них можно вывести?

Пункт б), подсказка 2

Из них следует, что a²b²c²d²e² ⋮ a⁴b⁴c⁴d⁴e⁴. Но тогда 1 ≥ a²b²c²d²e² ≥ 1. Какой вывод можно сделать?

Пункт б), подсказка 3

Конечно же, такое возможно только при a = b = c = d = e = 1, но такой набор не удовлетворяет условию. Отсюда следует ответ!

Показать ответ и решение

а) Да, существуют. Рассмотрим числа $p2pp p p 1 23 45$ , $p p2p p p 1 23 4 5$ , $p p p2p p 1 23 4 5$ , $p p pp2p 1 2 34 5$ , $pp pp p2 1 2 34 5$ . Для любых пяти попарно различных простых чисел $pi$ этот набор соответствует условию пункта (а).

Замечание. Другой пример: $100 100 101 99 102 98 103 97 104 96 2 ⋅3 ,2 ⋅3 ,2 ⋅3 ,2 ⋅3 ,2 ⋅3 .$

б) Предположим, что существуют такие натуральные числа $a,b,c,d,e$ . Тогда из $2.. a .bcde$ , $2.. b.acde$ , $2.. c.abde$ , $2 .. d .abce$ , $2.. e .abcd$ немедленно следует $2 22 22 ..4 44 4 4 a b cd e .ab cd e$ . Но тогда $2 22 2 2 4 44 44 ab cd e ≥a b cd e$ и $2 22 22 1 ≥a bc de ≥ 1$ , а в таком случае единственно возможная ситуация: $a= b= c= d= e=1$ . Но это противоречит предположению, что ни одно из чисел не делится на другое.

Ответ:

а) да

б) нет

Ошибка.
Попробуйте повторить позже

Задача 28#31499Максимум баллов за задание: 7

Является ли число $123456789012345$ квадратом натурального числа?

Подсказки к задаче

Подсказка 1

В подобных задачах часто помогает идея разложения квадрата на простые множители. Можно ли что-нибудь сказать про степени вхождения простых в квадрат?

Показать ответ и решение

Первое решение.

С одной стороны, это число оканчивается на цифру $5$ , то есть делится на $5$ . С другой, число дает при делении на $25$ такой же остаток, что и число, образованное последними двумя цифрами. В нашем случае число, образованное последними двумя цифрами, — это $45$ . Оно не делится на $25$ , значит, и исходное число не делится на $25$ . Итак, число делится на $5$ , но не делится на $25$ .

Заметим, что если число квадрат, то простые числа входят в него в четной степени. Значит, если квадрат делится на 5, то делится и на 25. Но перед нами число, которое делится на $5$ и не делится на $25$ . Значит, оно не квадрат.

Второе решение.

Это число даёт остаток $8$ при делении на $11$ , однако квадраты могут быть сравнимыми только с $0,1,3,4,5,9$ по модулю $11$ , значит, искомое число не квадрат.

Ответ:

нет

Ошибка.
Попробуйте повторить позже

Задача 29#32932Максимум баллов за задание: 7

Существует ли натуральное число, которое при умножении на $2$ станет квадратом, при умножении на $3$ — кубом, а при умножении на $5$ — пятой степенью?

Подсказки к задаче

Подсказка 1

По сути, в рамках этой задачи вас ничего не должно волновать, кроме степеней вхождения 2,3 и 5, так как все остальное здесь никак не используется. Попробуйте подумать какие должны быть степени вхождения 2,3 и 5.

Подсказка 2

Когда мы умножаем число на 2, то изменяется только степень вхождения 2, а все остальное-остается таким же как было. Значит какими должны быть степени вхождения 3 и 5? Попробуйте применить похожие рассуждения к каждому из чисел 2,3,5.

Показать ответ и решение

Рассмотрим число $215⋅320 ⋅524.$ Легко видеть, что оно нам подходит. Придумать пример можно примерно так. Рассмотрим степень вхождения $2$ в наше число. Она должна быть нечетным числом (после прибавления единицы станет чётным), делящемся на $3$ и на $5$ (умножение на $3$ и $5$ степень двойки не меняют). Например, нам подходит $15.$ Проделав аналогичные действия для $3$ и $5,$ получим пример.

Ответ:

да

Ошибка.
Попробуйте повторить позже

Задача 30#32934Максимум баллов за задание: 7

Какое наибольшее количество различных натуральных чисел, не превосходящих $2021$ , можно выбрать так, чтобы произведение любых двух выбранных чисел было точным квадратом?

Подсказки к задаче

Подсказка 1

Пусть у вас есть некий набор из этих чисел, который подходит под условие. Попробуйте преобразовать каждое из чисел по общему правилу так, чтобы набор, который получился после преобразования, также удовлетворял условию про «произведение любых двух-квадрат».

Подсказка 2

Да, нужно поделить каждое из чисел на максимальный квадрат, который делит данное число. Что тогда можно сказать про получившееся число? Какие степени вхождения простых?

Подсказка 3

Да, степени вхождения простых равны 1. Теперь возьмем два любых числа из получившегося набора. Их произведение также будет квадратом(ровно так мы и получили эти числа). Какой вывод можно сделать про эти два числа на основе первого и третьего предложения? А какой тогда вывод можно сделать про все числа?

Подсказка 4

Да, выходит, что эти два числа равны(поскольку если у одного из них есть какое-то простое, которого нет у другого, то степень этого простого будет равна 1 и число точно не будет квадратом). Но мы же взяли два любых числа и сделали такой вывод. Что это значит в рамках всего набора?

Подсказка 5

Это значит, что все числа из получившегося набора равны. Попробуйте вернуть то, на что поделили каждое число из изначального набора и понять, сколько максимум можно взять чисел вида n*x^2(n-их общая часть, х^2-то на что делили) из набора от 1 до 2021. Каким нужно взять n для максимизации кол-ва?

Показать ответ и решение

Рассмотрим выбранные числа и поделим каждое на наибольший точный квадрат, на который оно делится. Поскольку мы делим на квадрат, то любое произведение останется квадратом. Однако простые множители входят в каждое число не больше, чем в первой степени. Если для каких-то двух чисел этот набор простых оказался разным, то хотя бы одно в произведении будет в нечётной степени и произведение не будет квадратом. Потому все полученные числа совпадают и равны некоторому $m$ . Каждое число из первоначального набора получается умножением $m$ на какой-то квадрат. Если $m = 1$ , то чисел не более $44$ (они будут равны $2 2 2 1 ,2,...44$ ), поскольку $2 45 > 2021$ . Если же $m > 1$ , то $2 2 44 ⋅m ≥ 2⋅44 >2021$ , то есть чисел меньше $44$ .

Ответ:

$44$

Ошибка.
Попробуйте повторить позже

Задача 31#33938Максимум баллов за задание: 7

Разложите число $1001$ на два натуральных множителя всеми возможными способами.

Показать ответ и решение

Сначала разложим число $1001$ на простые множители: $1001= 7⋅11 ⋅13$ . Итак, у этого числа $3$ различных простых множителя. Значит, когда мы раскладываем число на два натуральных множителя, возможны два варианта: либо в одном числе оказываются $3$ простым сомножителя, в другом $0$ , либо в одном числе оказываются $2$ простых сомножителя, в другом $1$ .

В первом случае мы получаем только разложение $1 ⋅1001$ . Во втором случае одно из чисел простое, и у нас есть $3$ разложения: $7⋅143$ , $11⋅91$ , $13⋅77$ .

Ответ: 1 ⋅1001, 7⋅143 , 11⋅91 , 13⋅77

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 32#33940Максимум баллов за задание: 7

Можно ли числа от $1$ до $10$ разбить на две группы так, чтобы произведение чисел в одной группе равнялось произведению чисел в другой группе?

Показать ответ и решение

Рассмотрим простое число $7$ . Никакое другое число от $1$ до $10$ на него не делится, и более того, так как $7$ простое, то никакое произведение остальных чисел от $1$ до $10$ не будет делиться на $7$ . При любом разбиении чисел от $1$ до $10$ на две группы число $7$ попадет только в одну группу. Тогда произведение чисел в этой группе будет делиться на $7$ , а в другой — не будет. Таким образом, произведения чисел в двух группах не могут быть равны.

Ответ: Нет, нельзя

Ошибка.
Попробуйте повторить позже

Задача 33#33942Максимум баллов за задание: 7

Найдите наименьшее число, произведение цифр которого равно $200$ .

Показать ответ и решение

Разложим число $200$ на множители: $200 =2 ⋅2 ⋅2 ⋅5 ⋅5$ . Число тем меньше, чем меньше в нем знаков. При этом произведение цифр делится на $25$ , значит, в нем обязательно есть цифры, которые делятся на $5$ . Это либо $0$ , либо $5$ . В числе не может быть нулей, так как тогда произведение цифр будет равно $0$ . Значит, в числе обязательно есть две пятерки. Произведение оставшихся цифр равно $8$ . Чтобы получить такое произведение, нужна либо одна восьмерка, либо хотя бы две цифры. Так как цифр должно быть как можно меньше, мы используем одну восьмерку. Итак, число состоит из цифр $5$ , $5$ и $8$ . Нам нужно найти наименьшее число, значит, в начало нужно поставить меньшие цифры, а в конец большие. Получается число $558$ , это и является ответом.

Ответ: 558

Ошибка.
Попробуйте повторить позже

Задача 34#33954Максимум баллов за задание: 7

Прямоугольник с целыми длинами сторон разбит на двенадцать квадратов со следующими длинами сторон: $2$ , $2$ , $3$ , $3$ , $5$ , $5$ , $7$ , $7$ , $8$ , $8$ , $9$ , $9$ . Каков периметр прямоугольника?

Подсказки к задаче

Подсказка 1

Нам известно, что прямоугольник разбит на 12 квадратов с заданными длинами сторон. Что мы можем найти в этой фигуре, зная размеры внутренних квадратов?

Подсказка 2

Верно, мы можем рассчитать её площадь. Также эта площадь равна произведению сторон прямоугольника. Из условия нам известно, что они целые. Разложим значение площади на множители и посмотрим, какие значения могут принимать стороны прямоугольника. Не забывайте, что прямоугольник должен иметь разбиение на квадраты.

Подсказка 3

Так как у нас есть квадрат стороной 9, то обе стороны не меньше 9, и единственное возможное разбиение: 16 и 29. Остаётся только найти периметр такого прямоугольника

Показать ответ и решение

Найдем площадь прямоугольника

S = 2⋅2+2 ⋅2 +3⋅3+ 3⋅3+ 5⋅5+5 ⋅5 +7⋅7+ 7⋅7+ 8⋅8+ 8⋅8+9⋅9+ 9⋅9=

=464= 2⋅2⋅2⋅2⋅29

Обе стороны прямоугольника должны быть не меньше $9$ , так как присутствует квадрат со стороной $9$ . Тогда единственный вариант разложения числа $464$ на $2$ множителя:

464= 16 ⋅29

Периметр прямоугольника в это случае будет равен $90.$

Замечание. По условию сказано, что прямоугольник разбит. Это значит, что какое-то разбиение существует. Мы сейчас на самом деле доказали, что если разбиение и существует, то только когда этот прямоугольник со сторонами $16$ и $29$ . Так как из условия следует, что разбиение существует, то нам приводить пример этого разбиения не обязательно. Вот если бы мы нашли два возможных варианта ответа, нам бы пришлось дополнительно приводить к каждому из них пример. Тем не менее, пример действительно есть, и дотошный читатель может его без проблем нарисовать.

Ответ: 90

Ошибка.
Попробуйте повторить позже

Задача 35#35512Максимум баллов за задание: 7

Можно ли расставить по кругу 2021 различное натуральное число так, чтобы для любых двух соседних чисел отношение большего из них к меньшему было простым числом?

Показать ответ и решение

Будем решать задачу от противного. Рассмотрим разложение чисел на простые множители, представив каждое число в виде $pα1pα2...pαk 1 2 k$ . Посмотрим, что происходит при переходе от одного числа к другому. У нас либо добавляется, либо пропадает один простой множитель, либо одна из $α$ изменяется на 1. В любом случае сумма $α1+ α2+ ...+ αk$ изменяется на 1, то есть меняет чётность. Значит, чётность этой суммы должна чередоваться — но это невозможно, если чисел всего 2021, то есть нечётное количество.

Ответ: Нет, нельзя

Ошибка.
Попробуйте повторить позже

Задача 36#35514Максимум баллов за задание: 7

Какое наибольшее количество чисел, не превосходящих $2021,$ можно выбрать так, чтобы произведение любых двух выбранных чисел было точным квадратом?

Показать ответ и решение

Решаю эту задачу, довольно быстро приходит на ум хороший пример: когда все выбранные числа сами являются точными квадратами. В таком случае чисел $44,$ так как $2 44 = 1936,$ а $2 45 = 2025.$ Теперь сделаем оценку. Для этого нам пригодится ввести новое понятие: бесквадратная часть числа. Рассмотрим, например, число $5 2 2016 =2 ⋅3 ⋅7.$ Выделим в нём наибольший квадрат: мы можем взять $4 2$ и $2 3 .$ Оставшиеся множители, а именно $2⋅7,$ как раз и образуют бесквадратную часть. Более строго: бесквадратной частью будем называть произведение тех простых множителей числа, что входят в него в нечётной степени. Если число является квадратом, будем считать, что его бесквадратная часть равна $1.$

С этой бесквадратной частью связано такое интересное свойство: произведение двух чисел является квадратом тогда и только тогда, когда их бесквадратные части равны. Докажем эту лемму. Во-первых, в одну сторону это очевидно: если у чисел равны бесквадратные части (обозначим их через $a$ ), то числа можно представить как $2 a⋅x$ и $2 a ⋅y .$ Тогда их произведение равно $2 (axy).$ Теперь в обратную сторону: допустим, что произведение чисел является квадратом. Получается, что если у одного числа какой-то простой множитель входил в него в нечётной степени, то и у другого этот множитель должен присутствовать в нечётной степени, иначе в произведении этот простой множитель так и останется в нечётной степени, и произведение не станет точным квадратом. Таким образом, наборы простых чисел, которые входят в эти два числа в нечётных степенях, совпадают, значит, будут равны и бесквадратные части.

Теперь воспользуемся доказанной леммой. Из условия сразу следует, что бесквадратные части всех чисел равны. Обозначим эту бесквадратную часть через $a.$ Тогда все числа представимы в виде $ax2,$ и во всех числах обязательно разные $x.$ Если бы чисел было хотя бы $45,$ то один из $x$ был бы не меньше $45,$ а само число не меньше $a⋅452 = 2025a,$ что больше $2021,$ ведь $a≥ 1,$ противоречие.

Ответ:

$44$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 37#35515Максимум баллов за задание: 7

Вася придумал новую теорему: если произведение двух взаимно простых чисел $x$ и $y$ делится на произведение двух взаимно простых чисел $a$ и $b$ , то хотя бы одно из чисел $x$ и $y$ делится хотя бы на одно из чисел $a$ или $b$ . Верна ли эта теорема?

Показать ответ и решение

Можно взять $x= 2⋅3= 6$ , $y = 5⋅7=35$ , $a= 2⋅5= 10$ , $b= 3⋅7= 21$ . Легко видеть, что $xy = ab$ , и ни одно из чисел $x,y$ не делится ни на какое из чисел $a,b$ .

Ответ: Не верна

Ошибка.
Попробуйте повторить позже

Задача 38#35516Максимум баллов за задание: 7

Натуральное число умножили последовательно на каждую из его цифр. Получилось 1995. Найдите исходное число.

Подсказки к задаче

Подсказка 1

Давайте для начала разложим 1995 на простые множители. Получим 3, 5, 7 и 19. Часть из них является делителями исходного числа, другая часть - его цифрами. Подумайте, какие числа точно не могут являться цифрами искомого числа

Подсказка 2

Правильно, "19" - не цифра, а значит, точно относится к делителям. Но 19 не равно 3·5·7, так что у исходного числа есть ещё хотя бы один делитель. Подумайте, какой ещё из множителей не может быть цифрой по признакам делимости на него и его квадрат?

Подсказка 3

Верно, если бы 5 входило в начальное число, то получившееся в результате умножения делилось бы на 25. Тогда 5 является только цифрой.
Теперь нужно перебрать все оставшиеся варианты и найти подходящие под условие.

Показать ответ и решение

Разложим число на простые множители

1995 =3 ⋅5 ⋅7 ⋅19

Надо разбить это произведение на две группы: часть множителей войдёт в исходное число, а другая часть будет его цифрами. Ясно, что 19 войдёт в искомое число, ведь цифры “19” нет. Произведение цифр числа 19 не равно $3⋅5⋅7,$ поэтому в число должен войти хотя бы ещё один множитель из 3,5,7. При этом все три множителя входить не могут, потому что тогда получится само число 1995, у которого произведение цифр не равно 1.

Если 5 входит в исходное число, то по признаку делимости это число может оканчиваться только на 0 или на 5. Если оно оканчивается на 0, то при умножении на цифры должно было получиться 0, а не 1995. Если оно оканчивается на 5, то с произведением цифр должно получиться уже кратное 25 число, но 1995 не делится на 25.

Остаётся проверить три варианта:

19⋅3 =57 подходит, произведение цифр равно 5⋅7

19⋅7= 133 не подходит, произведение цифр не равно 5⋅3

19⋅3⋅7= 399 не подходит, произведение цифр не равно 5

Ответ: 57

Ошибка.
Попробуйте повторить позже

Задача 39#35517Максимум баллов за задание: 7

Мальвина написала на доске верное равенство. Буратино переписал его в тетрадку и стёр с доски. В тетради оказалось написано 437093 = 713695. Тут Буратино понял, что пропустил знаки умножения, которых было ровно три. Помогите ему восстановить написанное Мальвиной равенство. Найдите все варианты и докажите, что других нет.

Показать ответ и решение

Решение

Независимо от расстановок знаков умножения правая часть равенства делится на 5, а значит, и левая часть должна делиться на 5, тогда после цифры 0 в левой части стоит знак умножения. Но тогда левая часть делится на 2, поэтому в правой части знак умножения должен стоять после какой-то четной цифры. Единственный вариант поставить знак умножения после 6. Далее несложным перебором легко убедиться, что последний знак нужно поставить перед цифрой 6 в правой части.

Ответ: 4370⋅93 =713⋅6⋅95 .

Ошибка.
Попробуйте повторить позже

Задача 40#35520Максимум баллов за задание: 7

На доске выписаны несколько различных натуральных чисел, не превосходящих $1000$ . Ни одно из выписанных чисел не является квадратом. Известно, что среди любых трёх чисел найдутся два, дающих в произведении точный квадрат. Какое наибольшее количество чисел может быть выписано?

Показать ответ и решение

Обозначим через $p ,...,p 1 n$ все простые числа, меньшие 1000. Заметим, что по условию каждое выписанных чисел раскладывается в произведение $p1,...,pn$ в некоторых степенях. Каждое из наших простых чисел входит в одно выписанное число в четной или нечетной степени. Сопоставим каждому выписанному числу последовательность из 0 и 1 длины $n$ . Число на $i$ - ой позиции будет равно 1, если $pi$ в ходит в выписанное число в нечетной степени и 0 в противном случае (на самом деле это и есть бесквадратная часть, про которую мы говорили в теории). Предположим, что среди последовательностей выписанных чисел есть три различные. Тогда для трех соответствующих этим последовательностям чисел не выполнено условие (два числа в произведении могут давать точный квадрат, только если четности вхождения каждого $pi$ - ого одинаковые).

То есть мы показали, что различных последовательностей может быть не больше 2. Обозначим эти последовательности через $a1,...,an$ и $b1,...,bn$ . Обозначим через $a a a= p11⋅⋅⋅pnn$ , $b b b=p11⋅⋅⋅pnn$ . Очевидно что $a⁄= b$ . Считаем. что $a <b$ , тогда $a≥ 2$ , $b≥ 3$ , так как при $a= 1$ мы получим, что числа являются квадратами — по условию, квадратов среди выписанных чисел нет. Каждое из выписанных чисел дает точный квадрат либо при делении на $a$ , либо при делении на $b$ . Причем для чисел, которым соответствуют одинаковые последовательности, эти квадраты должны быть различными. Рассмотрим наибольшее выписанное число, которому соответствует последовательность $a$ -шек. Оно равно $a ⋅s2$ для некоторого натурального $s$ , откуда $s2 ≤ 500$ , то есть $s≤ 22$ . Но тогда количество выписанных чисел, которым соответствует первая последовательность, не превосходит 22. Аналогично поступаем со второй последовательностью. Опять рассматривает наибольшее число $bh2 ≤ 1000$ , откуда $h2 ≤ 1000∕3$ , то есть $h ≤18$ , откуда таких чисел не больше 18. То есть всего чисел не больше, чем $22+ 18= 40$ .

Пример строится из доказательства, а именно берем все точные квадраты от 1 до 22, умноженные на 2, и все точные квадраты чисел от 1 до 18, умноженные на 3.

Ответ: 40

Предыдущая подтема

Следующая подтема