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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сколькими способами можно представить число $n= 2401 ⋅3500$ в виде произведения двух натуральных чисел $x$ и $y,$ где $y$ делится на $x?$

Источники: Физтех 2025 11.2 (olymp-online.mipt.ru)

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

Подсказка 1

Заметим, что x и y имеют в разложении на простые множители только двойки и тройки. Как соотносятся их степени вхождения, если y делится на x?

Подсказка 2

Да, степень вхождения и двойки, и тройки в y больше, чем в x. Тогда можно обозначить эти степени вхождения переменными, а дальше перемножить варианты степени вхождения двойки и тройки в y.

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

Заметим, что делитель числа $n$ не может иметь простые множители кроме 2 и 3, так как само $n$ имеет только эти простые числа в своем каноническом разложении. Отсюда любой делитель $n$ имеет вид $a b 2 3,$ где $a,b∈ ℤ$ и $0≤ a≤401,0≤ b≤500.$

Тогда $y$ так же имеет вид $a b y = 23$ с аналогичными условиями на $a$ и $b.$ Отсюда

n 24013500 401−a 500−b x= y = -2a3b--=2 3

Рассмотрим отношение чисел $y$ и $x:$

a b y = -4012−a3500−b = 22a−40132b−500 x 2 3

Получившееся число является целым, так как $y$ делится на $x$ по условию. Это значит, что $2a− 401≥ 0$ и $2b− 500≥ 0,$ то есть $a ≥201$ и $b≥250.$

Таким образом, у нас есть $401 − 201+ 1= 201$ способ выбрать число $a,$ на каждый из которых есть $500− 250+1 =251$ способ выбрать число $b,$ откуда количество способов выбрать пару $a$ и $b$ равно $201⋅251= 50451.$ При этом каждая такая пара задаёт разложение числа $n$ на множители $x$ и $y,$ где $y$ делится на $x,$ поэтому $50451$ и будет ответом.

Ответ:

50451

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

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

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

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

Верно ли, что число

2026 2024 − 2024⋅2026+ 2025

делится на $20232?$

Источники: Надежда Энергетики - 2025, 11.5(см. www.energy-hope.ru)

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

Подсказка 1

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

Подсказка 2

Чтобы было удобнее раскладывать, можно попробовать заменить какое-то число на переменную x.

Подсказка 3

Для удобства заменим 2024, чтобы было проще работать со степенью. Осталось проверить делимость на (x - 1)².

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

Заметим, что

2026 2026 2024 − 2024⋅2026+2025= 2024 − 1− 2023⋅2026

Пусть $x= 2024.$ Тогда выражение примет вид

x2026 − 1− 2026(x− 1)=(x− 1)(x2025+ x2024+...+x +1)− 2026(x− 1)=

= (x − 1)(x2025 − 1+ x2024− 1+ ...+x − 1)

Нам необходимо проверить делимость на $20232 = (x− 1)2.$

Одна из скобок уже равна $(x − 1),$ осталось проверить делимость второй на $(x − 1).$ А это верно, так как каждая из разностей вида $(xk− 1)$ делится на $(x− 1),$ а, значит, и сумма тоже делится.

Ответ:

Верно

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

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

Пусть $a$ и $b$ — целые числа. Докажите, что если $a2+ 9ab+b2$ делится на $11,$ то и $a2− b2$ делится на $11.$

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

Выделим полный квадрат:

2 2 2 2 2 a + 9ab+ b = a − 2ab+ b+ 11ab =(a− b) + 11ab

По условию

2 (a− b) + 11ab

кратно 11, кроме того и $11ab$ тоже кратно 11. Значит, $(a− b)2$ тоже обязано быть кратно 11. Так как 11 — это простое число, то это означает, что $a− b$ кратно 11.

Теперь распишем $a2− b2$ как разность квадратов и получим $(a− b)(a+ b)$ , а, так как ранее определили, что множитель $a− b$ кратен 11, то и все произведение тоже будет делиться на 11.

Ответ:

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

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

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

Источники: БИБН - 2025, 10.5 (см. www.unn.ru)

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

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

Раз просят наименьшее, то давайте будем пробовать добавлять по одному числу, начиная с 0. Что будет, если у нас всего одно число во второй группе?

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

Сумма оставшихся чисел не меньше 190 — сильно много. Теперь для двух чисел во второй группе.

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

211 = (a+1)(b+1), бывает ли так?

Пункт а, Подсказка 4

211 — простое. Приведите пример для трёх чисел.

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

Как можно снизу оценить произведение через количество выбранных чисел?

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

Если чисел хотя бы 6, то произведение хотябы 6! = 720 > 210. Значит, чисел не больше 5.

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

Предположим, подойдёт пятёрка (1,2,3,4,x). Найдите x.

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

a) Сумма всех чисел от 1 до 20 равна 210. Очевидно, что во второй группе больше одного числа, так как в противном случае оно было бы равно сумме оставшихся 19 чисел, тоесть не меньше, чем $1+2 +...+ 19= 190.$ Покажем, что на самом деле во второй группе больше двух чисел. Действительно, в противном случае для чисел $a$ и $b$ из второй группы выполнялось бы равенство

210− a− b= ab

211= (a+1)(b +1)

Раз 211 — простое число, следовательно, данное уравнение не имеет решений на промежутке от 1 до 20. Приведем пример второй группы из 3 чисел. Сначала возьмем единицу, будет верно, что

209− a− b= ab

210= (a+1)(b +1)

Нам подойдут тройки ${1;9;20}$ и ${1;13;14}.$

б) Докажем, что чисел во второй группе меньше 6. В противном случае, наименьшее произведение чисел второй группы равнялось бы

1⋅2⋅3 ⋅4 ⋅5 ⋅6 =720> 210

Получили противоречие с равенством произведения чисел второй группы и суммы чисел первой группы. Подберем пример для случая, когда во второй группе 5 чисел. Предположим, что подойдет пятерка вида $(1;2;3;4;x),$ где $x ∈[5;20].$ Должно выполниться условие

210− 10− x= 24x

x= 8

Подойдет набор $(1;2;3;4;8).$

Ответ:

а) 3; б) 5

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

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

Является ли простым число $2...27999...9$ ? (сначала $2$ написано $2024$ раза, затем $9$ написано $2024$ раза).

Источники: Миссия выполнима - 2025, 10.4 (см. www.fa.ru)

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

Подсказка 1

Что легче доказать: простоту числа или обратное утверждение?

Подсказка 2

Конечно же, второе! Попробуем явно найти делитель.

Подсказка 3

Банальные признаки делимости не подходят, но может, есть что-то другое? На что всегда делится число, записанное одинаковыми цифрами?

Подсказка 4

Казалось бы, задача почти решена, но мешает 7. Вот если бы на 7 делились числа из двоек и девяток...

Подсказка 5

Осталось только всё строго записать! Представьте исследуемое число в виде суммы, в которой каждое из слагаемых кратно 7.

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

Заметим, что число $111111 =7 ⋅15873$ делится на $7.$ Тогда числа $222222= 2⋅111111$ и $999999= 9⋅111111$ тоже делятся на $7.$ Также на $7$ делится и число $22799 =7 ⋅3257.$ Откуда следует, что число

4043 2027 2022 2016 2...279...9= 222222⋅10 + ...+222222⋅10 + 22799⋅10 + 999999⋅10 +...+ 999999

делится на $7,$ так как каждое из слагаемых суммы, в виде которой можно представить заданное число, тоже делится на $7.$ А раз у нужного числа есть делитель, отличный от самого себя и $1,$ то оно не является простым.

Ответ: Нет

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

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

При каких натуральных $n$ число $20n+ 16n− 3n − 1$ делится на 323?

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

__________________________________________________________________________________________________

Лемма. Число $n n a − b$ кратно числу $a− b,$ где $a,b$ — натуральные, $n$ — неотрицательное целое.

Доказательство. По формуле сокращенного умножения

n n n−1 n−2 n−2 n−1 a − b =(a− b)(a + a b+ ...+ ab + b )

Значит, $an− bn$ кратно $a − b.$

______________________________________________________________________________________________________________________________________________________

Заметим, что $323= 17⋅19,$ при этом 17 и 19 взаимнопростые, откуда число делится на 323 тогда и тогда тогда, когда оно делится на 17 и на 19.

Для начала рассмотрим делимость на 17. По лемме $n n 20 − 3$ кратно $20− 3= 17,$ то есть наше число делится на 17 тогда, когда $n 16 − 1$ кратно 17. При этом $n n 16 ≡ (− 1) (mod 17),$ то есть $n 16 − 1$ кратно 17 только при чётном $n.$

Теперь рассмотрим делимость на 19. По лемме $n n 20 − 1$ делится на $20− 1= 19,$ а при $n =2k$ число $n n 2k 2k 16 − 3 = 16 − 3$ делится на $2 2 16 − 3 =13⋅19.$

Итак, исходное число делится на 323 при чётных $n.$

Ответ:

При четных $n$

Курсы

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

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

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

Пусть $n >1,$ а

1= d1 < d2 <...<dk =n

— все натуральные делители числа $n.$ Оказалось, что ровно для одного индекса $2≤ i≤k − 1$ число $di−1di+1$ не делится на $di.$ Может ли число $n$ быть квадратом натурального числа?

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

Подсказка 1:

Обратите внимание на то, что если dᵢ₊₁ является простым числом, то dᵢ₋₁ должно делиться на dᵢ, чего не может быть. Подумайте над этим.

Подсказка 2:

Рассуждения из предыдущей подсказки должны вызывать резонный вопрос: сколько может быть простых делителей в разложении n?

Подсказка 3:

Их ровно 2. То есть n = p₁ˣp₂ʸ, p₂ > p₁. Попробуйте рассмотреть какую-нибудь удобную тройку делителей dᵢ₋₁, dᵢ, dᵢ₊₁ и применить к ней условие.

Подсказка 4:

Давайте возьмём такое i, что dᵢ = p₂, тогда d = p₁ᵏ, где k — некоторое натуральное число. Чему может быть равно dᵢ₊₁?

Подсказка 5:

dᵢ₊₁ = p₁p₂ и x = k. Если вы к этому ещё не пришли, обязательно обоснуйте эти равенства на основании предыдущих подсказок. Попробуйте теперь подобрать ещё какую-нибудь тройку делителей, для которых не выполняется делимость из условия.

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

Предположим, что $n$ является квадратом натурального числа. Пусть $n= p2α1...p2αs. 1 s$ Рассмотрим произвольное $2≤ i≤s.$ Пусть $pi = dj,$ понятно, что $j ≥3.$ Тогда, если $dj−1$ делит $dj−2dj,$ то $dj−1$ делит и $dj−2,$ так как $(dj−1,dj)= 1.$ Но $dj−2 < dj−1$ — противоречие. Значит, если у $n$ есть хотя бы три разных простых делителя, то есть хотя бы два индекса $1≤ i≤ k,$ для которых число $di−1di+1$ не делится на $di$ — противоречие. Также понятно, что у $n$ должно быть хотя бы два простых делителя, иначе таких индексов $i$ бы не было, поскольку $n$ было бы степенью простого числа.

Осталось разобрать случай, когда у $n$ ровно два различных простых делителя $p1 <p2.$ Если $p2 = dj,$ то $k dj−1 =p1,$ $k−1 dj−2 = p1 .$ Как мы знаем, для $i= j− 1$ число $di−1di+1$ не делится на $di.$ Поэтому для всех остальных индексов должна быть выполнена делимость. Это в частности означает, что она выполнена для $i=j,$ то есть $dj+1$ делится на $p2.$ Тогда он равен $p2p1,$ и это больше $k+1 p1 .$ А значит, у $n$ нет делителя $k+1 p1 ,$ то есть $2α1 =k.$ Теперь пусть $2 p2 = dl,$ $l> j+1.$ Тогда $k dl− 1 =p2⋅p1,$ $k−1 dl−2 =p2⋅p1 .$ То есть $dl−1$ не делит $dl−2dl$ — противоречие!

Ответ:

нет

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

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

Серёжа выписал в ряд все натуральные делители некоторого натурального числа $N$ в порядке возрастания. Оказалось, что для любых двух соседних чисел в этом ряду $N$ делится и на разность этих чисел. Докажите, что для любых соседних чисел $a> b$ в этом ряду $ab$ делится на $a− b.$

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

Подсказка 1.

По условию мы можем работать с выражениями вида N/(a−b). С другой стороны, нужно получить, что ab/(a−b) является целым числом. Значит, нужно как-то попытаться сократить на N.

Показать доказательство

Заметим, что если $a$ и $b$ — два соседних делителя числа $N,$ то $N- a$ и $N- b$ — тоже два соседних делителя числа $N.$ Применяя для этих двух делителей условие задачи, получаем, что $N$ делится на $N- N- b − a ,$ то есть

N ab N-−-N-= a−-b ∈ ℤ b a

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

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

Пусть $1= d < d < ...< d = n 1 2 k$ — все натуральные делители натурального числа $n,$ являющегося точным квадратом. Может ли среди $di$ оказаться поровну чисел вида $3k+ 1$ и $3k+2?$

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

Подсказка 1.

Для начала рассмотрим случай, в котором n не делится на 3. Тогда делителей вида 3k не будет. Может ли выполняться условие задачи в этом случае?

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

Предположим, что такое возможно. Пусть $n= 32am,$ где $m$ не делится на 3. Тогда $m$ тоже является точным квадратом, причём делители $n,$ не кратные 3, совпадают с делителями $m.$ У $m,$ как у точного квадрата, нечётное число делителей, все они не делятся на 3, так что разбить на две равные группы их точно не получится.

Ответ:

нет

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

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

Пусть $1= d < d < ...< d = n 1 2 k$ — все натуральные делители натурального числа $n.$ Докажите, что если $d 3$ не делится на $d , 2$ то $dk−1+ dk−2$ делится на $d3+ d2.$

Показать доказательство

Пусть $n =pα1pα2...pαk 1 2 k$ — разложение $n$ на простые множители, причём $p < 1$ $p < 2$ …< $p . k$ Ясно, что $d =p , 2 1$ а $d = min(p2,p). 2 1 2$ По условию $d3$ не делится на $d2,$ поэтому $d3 = p2.$ Вспомним, что делители $n$ разбиваются на пары $( n) d,d .$ Отсюда следует, что

n n n n n(p1+p2) n dk−1+ dk−2 = d1-+ d2 = p1 + p2 =-p1p2-= p1p2(d1+ d2).

Так как $p1p2 |n,$ то это выражение делится на $d1+ d2.$

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

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

Можно ли вычеркнуть из произведения $1!⋅2!⋅3!⋅...⋅56!$ один из факториалов так, чтобы произведение оставшихся было квадратом целого числа?

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

2 2 2 28 2 1!⋅...⋅56!=(1!) ⋅2⋅(3!) ⋅4 ⋅...⋅(55!) ⋅56=2 ⋅(1!⋅3!⋅...⋅55!)⋅28!

Отсюда видно, что, вычеркнув $28!,$ мы получим квадрат числа $214⋅1!⋅3!⋅...⋅55!.$

Ответ:

Да, можно

Интенсивы

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

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

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

Дано $41$ различное натуральное число, меньшее $1000.$ Известно, что среди любых трех из них есть два, дающих в произведении точный квадрат. Докажите, что среди этих чисел есть точный квадрат.

Показать доказательство

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

То есть мы показали, что различных последовательностей может быть не больше $2.$ Обозначим эти последовательности через $a1,...,an$ и $b1,...,bn.$ Обозначим через $a a b b a =p11⋅⋅⋅pnn,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.$ Получили противоречие с количеством данных чисел.

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

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

Про натуральные числа $a,b,c$ известно, что $ab$ делится на $2c,bc$ делится на $3a$ , а $ac$ делится на $5b$ . Найдите наименьшее возможное значение их произведения $abc$ .

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

Подсказка 1

Обратите внимание, что если w является делителем x и y является делителем z, то xz кратно wy. Как это можно применить относительно нашего условия?

Подсказка 2

Правильно, перемножив попарно все три условия кратности и сократив лишнее, получим, что a² ⫶ 10, b² ⫶ 6 и c² ⫶ 15. Все эти числа не включают в себя полные квадраты. Что это говорит о числах a, b и c?

Подсказка 3

Правильно, сами числа тогда тоже делятся на 10, 6 и 15 соответственно, а значит, не могут быть меньше них. Тогда и abc тоже будет не меньше произведения этих чисел.

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

.. .. 2 .. 2.. ab.2c,bc.3a =⇒ ab c.6ac =⇒ b .6

Но раз квадрат $b$ делится на 2 и на 3, то и само $b$ делится на 2 и на 3. Тогда $b...6$ , значит, $b≥ 6.$

.. .. 2 .. 2.. ab.2c,ac.5b =⇒ a bc.10bc =⇒ a .10

Но раз квадрат $a$ делится на 2 и на 5, то и само $a$ делится на 2 и на 5. Тогда $a...10$ , значит, $a≥ 10.$

bc...3a,ac...5b =⇒ abc2...15ab =⇒ c2...15

Но раз квадрат $c$ делится на 3 и на 5, то и само $c$ делится на 3 и на 5. Тогда $. c..15$ , значит, $c≥ 15.$

В итоге $abc≥ 10⋅6⋅15= 900,$ причём при $a =10$ , $b= 6$ , $c= 15$ достигается равенство.

Ответ: 900

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

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

Дано простое число $p.$ Пусть $n$ — наименьшее натуральное число, большее 1, такое, что $n6− 1$ делится на $p.$ Докажите, что тогда одно из чисел $6 (n+ 1) − 1$ или $6 (n +2) − 1$ также делится на $p.$

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

Подсказка 1

Известно, что n — наименьшее натуральное, большее 1... Может ли оно быть большим? Есть ли какой-то очевидный "подозреваемый" среди чисел меньше p, который точно удовлетворяет сравнению n⁶ − 1 ≡ 0 (mod p)?

Подсказка 2

n⁶ − 1, это же не монолит! Можно же разломать на более мелкие кусочки, на несколько множителей.

Подсказка 3

n⁶ − 1 = (n + 1)(n − 1)(n² + n + 1)(n² − n + 1). Значит, p делит один из данных множителей.

Подсказка 4

Многочлены x² + x + 1, x² − x + 1 очень похожи. Можно ли простым преобразованием переменной один превратить в другой?

Подсказка 5

x² + x + 1 = (x + 1)² − (x + 1) + 1. Что можно сказать о (n − 1)⁶ − 1, (n + 1)⁶ − 1, в случае когда p делит (n² + n + 1)(n² − n + 1)?

Показать доказательство

Для $p= 2$ утверждение задачи очевидно, ведь числа $(n+ 1)6− 1,(n+ 2)6− 1$ — разной четности. Далее считаем $p> 2.$

Сразу заметим, что

6 6 (p− 1)− 1≡ (−1)− 1≡ 0 (mod p),

при этом $p− 1>1,$ то есть $p− 1$ подходит на роль $n,$ значит, $n≤ p− 1.$

Заметим, что

6 2 2 n − 1= (n − 1)(n +n +1)(n +1)(n − n+ 1).

Значит, $p$ делит один из множителей. Если $n − 1$ делится на $p,$ то $n ≥p +1$ — противоречие. Если $n+ 1$ делится на $p,$ то $n +2≡ 1 (mod p),$ откуда $(n+ 2)6− 1≡ 0 (mod p).$ Если

2 2 n − n+ 1= (n− 1) +(n− 1)+1

делится на $p,$ то $(n− 1)6− 1$ также делится на $p,$ что противоречит минимальности $n.$ Наконец, если

n2+ n+ 1= (n+ 1)2− (n+ 1)+1

делится на $p,$ то $(n+ 1)6− 1$ делится на $p.$

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

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

В произведении $1 ⋅2 ⋅...⋅n (n≥ 2)$ разрешается приписать некоторым сомножителям восклицательный знак (при этом сомножитель $k$ заменяется на $k!$ ). При каких $n$ в результате можно получить точный квадрат?

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

Подсказка 1

Давайте прикинем, какие вообще числа подойдут. Перебираем ручками и понимаем, что простые числа вроде 2,3,5 не подходят в качестве n. А, например, сами квадраты вроде 4 или 9 подойдут, ведь можно поставить после числа !, то есть получить 1 * 2 * 3 * ... * 7 * 8 * 9! два раза произведение чисел от 1 до 8 и саму девятку, а в итоге (8!)² * 9 = (3 * 8!)²

Подсказка 2

Надо подумать в терминах множителей, что вообще добавляет в произведение эта операция постановки восклицательного знака после множителя k.

Подсказка 3

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

Подсказка 4

Приписать восклицательный знак нужно к числу p+1 (где p-наибольшее простое в нечетной степени вхождения). Ого, мы исправили ситуацию с p. А можно ли также сделать и для других простых?

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

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

Операция постановки восклицательного знака, применённая к числу $k ≥2,$ даёт возможность добавить в произведение множители от $1$ до $k − 1$ включительно.

Заметим, что если число $n$ простое, то как бы мы ни расставляли восклицательные знаки, в произведении всё равно останется простой множитель $n$ в первой степени, так что получить квадрат не удастся.

При составном $n$ будем действовать следующим образом. Разложим произведение $1⋅2⋅...⋅n$ в виде произведения степеней простых и посмотрим, какие простые числа входят в нечётных степенях. Если таких чисел нет, то перед нами уже квадрат. Иначе обозначим наибольшее из этих простых за $p1.$ Поставим восклицательный знак после числа $p1+1.$ Так мы добавили в произведение все числа от $1$ до $p1,$ так что степень простого числа $p1$ увеличилась на $1$ и стала чётной. Кроме того, степени вхождения простых чисел, больших $p1,$ не изменились. Для нового произведения сделаем ту же операцию, то есть пересчитаем степени вхождения простых чисел и упорядочим те простые, что входят в нечётных степенях, в порядке убывания, и снова “исправим” наибольшее. Такими операциями мы в итоге придём к числу, являющимся точным квадратом.

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

Предположим, что $n$ простое. Тогда степень вхождения $n$ в произведение будет равна $1$ (как бы мы ни приписывали восклицательные знаки). Тогда число не является точным квадратом. Предположим, что $n= k2.$ Тогда можно приписать факториал после $n.$ В итоге останется $((n − 1)!)2⋅n$ — точный квадрат.

Теперь предположим, что $n = ab,$ где $a⁄= b$ и $a,b <n.$ Не нарушая общности, $a> b.$ Рассмотрим два случая.

Если $a= b+1,$ то припишем факториал к $a+1,n$ и $b$ (эти три числа различны). Останется

((b− 1)!)2⋅b⋅a⋅((n− 1)!)2⋅n= n2⋅((b− 1)!(n− 1)!)2

Если же $a >b+ 1,$ то припишем факториал к $b,b+1,a,a +1,n$ (все эти числа различны). Получится

((b− 1)!)2⋅b⋅((a− 1)!)2 ⋅a ⋅((n− 1)!)2⋅n =n2⋅((b− 1)!(a− 1)!(n− 1)!)2

что также является точным квадратом.

Ответ:

при составных

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

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

Через терминал оплаты на мобильный телефон можно перевести деньги, при этом взимается комиссия — натуральное число процентов. Федя положил целое количество рублей на мобильный телефон, и его счёт пополнился на $847$ рублей. Сколько денег положил на счёт Федя, если известно, что комиссия менее $30%$ ?

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

Пусть Федя положил $N$ рублей на свой телефон и комиссия составила натуральное число $p <30$ процентов. Тогда от его суммы вычитается $p-- 100$ рублей. Получается $Nx- 100$ рублей, где $100 >x = 100− p> 70.$

Итак,

Nx 7⋅10 ⋅10⋅11⋅11 100 =847 =⇒ x = -----N------∈ ℕ∩ (70;100)

По основной теореме арифметике из сократимости дроби следует, что $x$ это произведение каких-то множителей из числителя. Простым перебором можно убедиться, что в заданный интервал $(70;100)$ попадает только произведение $7⋅11.$ Так что $N = 7⋅107⋅0⋅11211 =100⋅11= 1100.$

Ответ:

$1100$

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

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

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

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

Докажите, что произведение трех последовательных натуральных чисел не может быть степенью (выше первой) натурального числа.

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

Подсказка 1

Попробуем идти от противного. Пусть наши числа — это n-1, n и n+1. Тогда нас спрашивают о произведении чисел n и n² - 1, которые взаимно просты. Что тогда можно сказать об этих числах, если их произведение является натуральной степенью выше 2?

Подсказка 2

Верно, n и n^2-1 сами являются точными степенями, причем с одним и тем же показателем b двух взаимно простых чисел x и y. Можно ли найти связь между x и y?

Подсказка 3

Верно! Так как n = x^b и n² - 1 = y^b, получаем x^(2b) - y^b = 1. А можно ли от степеней 2b и b перейти к более простым степеням?

Подсказка 4

Можно! Нетрудно видеть, что x² - y делит левую часть приведенного выше уравнения. А тогда x² - y делит и число 1, то есть равно 1. Таким образом, x² = y + 1. Имеет ли тогда решения уравнение, полученное в предыдущей подсказке?

Подсказка 5

Верно, не имеет! Можно подставить x² = y+1 и заметить, что (y+1)² - y² = 2y + 1 > 1. А можно ли доказать, что при b > 2 разность степеней чисел y+1 и y будет больше?

Показать доказательство

Предположим противное. Пусть последовательные числа имеют вид $n − 1,n,n+1$ ( $n> 1$ ). Их произведение равно $2 (n− 1)n(n+ 1)=n(n − 1).$ Заметим, что числа $n$ и $2 n − 1$ взаимно просты. Следовательно, если их произведение равно $b a ,$ где $b≥ 2$ , то $b 2 b n= x ,n − 1 =y ,$ $(x,y)= 1.$ Таким образом, $2b b x − y = 1.$ Нетрудно видеть, что $2b b x − y$ делится на $2 x − y,$ а значит это число делит единицу. То есть $2 x − y =1.$ Подставим $y+ 1$ вместо $2 x$ в уравнение и получим $b b (y+ 1)− y = 1.$

Ясно, что для натурального $y$ и $b≥ 2$ справедливо неравенство $b+1 b+1 b b (y+ 1) − y ≥ (y+ 1) − y,$ поскольку оно сводится к неравенству $b b (y +1)y >y (y− 1),$ которое очевидно верное. Таким образом, $b b 2 2 (y+ 1)− y ≥ (y +1) − y =2y+ 1> 1$ при $y >0.$ Если же $y =0,$ то $2 n =1,$ откуда $n= 1,$ но тогда число $n − 1$ не натуральное, пришли к противоречию.

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

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

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

Источники: Лига Открытий - 2022

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

Подсказка 1

Если какое-то из наших чисел достаточно большое, то один только его куб может быть больше произведения всех чисел. Это наталкивает на мысль, что если условие задачи выполнено, все числа должны быть “не слишком велики”.

Подсказка 2

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

Подсказка 3

Каждый простой множитель числа 20222022 входит как множитель в какое-то из искомых чисел. Если среди простых есть “слишком большое” (то есть такое, куб которого больше произведения всех чисел), то для нас это заведомо значит, что сумма всех кубов тоже будет слишком большой!

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

Разложим число 20222022 на простые множители: $20222022= 2⋅3⋅73⋅137⋅337$ . Предположим, что такой набор существует. Тогда легко видеть, что сумма кубов не меньше, чем $3 337 >20212021$ — противоречие.

Ответ: не существует

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

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

Докажите, что у чисел вида $n4+ 1$ бесконечно много простых делителей.

Показать доказательство

Предположим, противное, тогда существует конечное множество $S = {p }k i i=1$ простых делителей чисел вида $n4+ 1.$ Заметим, что число $k∏ pi+1 i=1$ не кратно $pi$ для всеx $i∈ {1,2,...,k},$ следовательно кратно некоторому простому числу $q,$ которое не принадлежит $S$ — противоречие.

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

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

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

(b) А если потребовать, чтобы квадрат делился на произведение остальных?

Показать доказательство

(a) Рассмотрим числа $2 2 2 2 2 p1p2p3p4p5,p1p2p3p4p5,p1p2p3p4p5,p1p2p3p4p5,p1p2p3p4p5.$ Для любых $5$ разных простых чисел $pi$ оно подходит под пункт $(a).$

(b) Допустим, что можно, и нам подходят числа $a,b,c,d,e.$ Тогда $. . . . . a2..bcde,b2..acde,c2 ..abde,d2..abce,e2..abcd.$ Значит, $. a2b2c2d2e2..a4b4c4d4e4.$ Но тогда $a2b2c2d2e2 ≥a4b4c4d4e4$ и $1≥ a2b2c2d2e2.$ но в этом случае $a= b=c =d =e =1,$ но тогда условие, что ни одно из них не делится на другое, не выполняется.

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

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