Тема Делимость и делители (множители)

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

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

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

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

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

Подтемы раздела делимость и делители (множители)

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

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

Задача 1#121760

Дано натуральное число $n.$ Натуральное число $m$ назовём удачным, если найдутся $m$ последовательных натуральных чисел, сумма которых равна сумме $n$ следующих за ними натуральных чисел. Докажите, что количество удачных чисел нечётно.

Источники: Турнир городов - 2025, устный тур, 11.2(см. turgor.ru)

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

Подсказка 1:

Ясно, что m > n. Давайте для удобства обозначим m = n + k и будем считать количество таких k. Осталось записать условие на равенство сумм, пользуясь формулой суммы членов арифметической прогрессии.

Подсказка 2:

Пусть первой наименьшее число среди n чисел равно x. Тогда у вас должно получиться равенство, в котором участвуют x, k и n. Обратите внимание на чётность множителей.

Подсказка 3:

У вас должно было получиться равенство (2x + k - 1)k = 2n². Давайте заметим, что у 2n² нечётное количество нечётных делителей. А сколько значений х соответствует распределению делителей по скобочкам?

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

Решение 1. Ясно, что $m > n,$ положим $m =n +k,$ где $k$ — натуральное, и будем искать количество подходящих $k,$ то есть таких $k,$ для которых уравнение

x +(x+ 1)+...+(x+ k− 1)+ ((x+ k)+ ...+(x+ k+ n− 1))= (x+ k+n)+ ...+ (x+k +2n− 1)

имеет решение в натуральных $x.$ Преобразуем, пользуясь формулой суммы арифметической прогрессии. Получим:

(2x+-k−-1)⋅k- (2x+-2k+-n−-1)⋅n- (2x-+2k+-3n−-1)⋅n- 2 + 2 = 2

Умножив на $2$ и приведя подобные слагаемые получаем:

(2x+ k− 1)k= 2n2 (∗)

Слева в уравнении (*) два сомножителя разной чётности, дающие в произведении $2 2n ,$ при этом левый сомножитель больше правого. Наоборот, если зафиксировать нечётный делитель $d$ числа $2 2n ,$ то, зная $d,$ найдём дополнительный делитель $′ 2n2 d = d ,$ и далее из системы $′ ′ k= min{d,d} ,2x+ k− 1= max{d,d }$ однозначно находим натуральное $x$ (равное $(d−d′+1) |-2|-- ).$

Итак, количество подходящих $k$ равно количеству нечётных делителей числа $2n2,$ которое, в свою очередь, равно количеству всех делителей числа $s2,$ где (нечётное) $s$ получается из $n$ делением на наибольшую степень двойки, входящую в разложение $n.$ Но количество делителей точного квадрата нечётно (так как все делители числа $s2,$ кроме $s,$ можно разбить на пары: $t↔ st2 ,$ и только делитель $s$ остаётся без пары).

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2.

Очевидно, $m =n +k,$ где $k$ натуральное. Запишем равенство из условия в виде

(a+1)+ ...+ (a +m )=(a+ m +1)+ ...+ (a+ m +n)

Отсюда:

2 a = n-− k+-1 (∗∗) k 2

Чтобы условие задачи выполнялось с данным $k,$ необходимо и достаточно, чтобы $a$ было целым неотрицательным.

Положим $n =s⋅2r,$ где $s$ нечётное, $r$ целое неотрицательное. Тогда $a$ будет целым в двух случаях: (а) если оба члена равенства (**) целые $;$ (б) если оба они полуцелые $.$ Первый случай имеет место, когда $k$ — нечётный делитель числа $n2,$ то есть делитель числа $s2.$ Количество $c$ таких значений $k$ нечётно, поскольку это всевозможные делители полного квадрата. Второй случай означает, что

k= d⋅22r+1,

где $d$ — делитель числа $s2.$ Между первым и вторым множеством значений $k$ есть биекция: каждому $k$ из первого множества соответствует число $2nk2$ из второго множества, и обратно.

Пусть $(f,g)$ — пара из указанной биекции, причём $f <g.$ Тогда при $k =f$ получится неотрицательное $a,$ а при $k =g$ отрицательное. Действительно, в силу $(∗∗)$ требуется проверить неравенство

k(k+1)≤ 2n2.

Но $f(f + 1) ≤fg = 2n2, g(g+ 1)> gf =2n2,$ что и требовалось. Поэтому подходящих значений $k$ будет ровно $c,$ то есть нечётное количество.

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

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

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

Задача 2#123926

Степень вхождения простого числа $p$ в натуральное $a$ равна $α,$ а степень вхождения $p$ в натуральное $b$ равна $β.$ Докажите, что степень вхождения $p$ в $НО Д(a,b)$ равна $min(α,β),$ а степень вхождения $p$ в $НОК(a,b)$ равна $max(α,β).$

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

Вспомним, что одно натуральное число делится на другое тогда и только тогда, когда для каждого простого множителя, входящего в разложение первого и второго чисел, степень вхождения в первое число не меньше степени вхождения во второе число.

Не умаляя общности, пусть $α≤ β,$ тогда $min(α,β)= α,max (α,β)= β.$

1) Пусть НОД $(a,b)= d.$ По определею НОД $(a,b)$ — это наибольший общий делитель $a$ и $b,$ то есть и $a,$ и $b$ делятся на $d,$ и нет числа, большего, чем $d,$ на которое так же делятся и $a,$ и $b.$

Если степень вхождения $p$ в $d$ больше $α,$ то $a$ не будет делиться на $d$ — противоречие.

Если степень вхождения $p$ в $d$ меньше $α$ и равна $γ,$ то $′ γ d =d ⋅p ,$ где $′ d$ и $p$ взаимнопросты. Тогда и $a,$ и $b$ делятся на $′ d ,$ а так же и $a,$ и $b$ делятся на $α p.$ Из взаимнопростости $′ d$ и $p$ следует, что и $a,$ и $b$ делятся на $′ α d ⋅p ,$ при этом $′ α d ⋅p > d$ — противоречие.

Получается, степень вхождения $p$ в $d$ равна $α.$

2) Пусть НОК $(a,b)= k.$ По определею НОК $(a,b)$ — это наименьшее общее кратное $a$ и $b,$ то есть $d$ делится и на $a,$ и на $b,$ и нет числа, меньшего, чем $k,$ которое так же делится и на $a,$ и на $b.$

Если степень вхождения $p$ в $k$ меньше $β,$ то $k$ не будет делиться на $b$ — противоречие.

Если степень вхождения $p$ в $k$ больше $β$ и равна $ω,$ то $k =k′⋅pω,$ где $k′$ и $p$ взаимнопросты. Рассмотрим число $k′⋅pβ.$ Так как $k$ делится на $a$ и $b,$ то в $k′$ входят все простые числа, входящие в $a$ и $b,$ кроме $p,$ при этом их степень не меньше, чем в $a$ и $b.$ Получатся, $k′⋅pβ$ делится и на $a,$ и на $b,$ при этом $k′⋅pβ <k$ — противоречие.

Получается, степень вхождения $p$ в $k$ равна $β.$

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

Задача 3#126725

Найдите все натуральные $n,$ для которых существует такое чётное натуральное $a,$ что число

2 n (a− 1)(a − 1)...(a − 1)

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

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

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

Подсказка 1:

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

Подсказка 2:

Итак, скорее всего вы поняли, что n = 1, 2 подойдёт, а n = 3 — нет. Чем остальные случаи отличаются. Например, если n > 3, то оно находится между двумя натуральными степенями двойки. То есть существует такое натуральное k, что 2^k ≤ n < 2^{k + 1}. Подумайте, как это можно использовать.

Подсказка 3:

Если записать скобку a^{2^k} – 1 как (a^{2^{k – 1}} – 1)(a^{2^{k – 1}} + 1), то становится ясно, что все произведение состоит из скобки a^{2^{k – 1}} + 1 и скобок вида a^m – 1. А как насчёт того, чтобы посмотреть на нод выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с произвольной скобкой a^m – 1?

Подсказка 4:

Нод второго выражения и a^m – 1 кратен ноду первого выражения и a^m - 1. Чтобы было проще работать, вот вам интересный факт: нод второй скобки и a^m – 1 равен a^нод(2^k, m) – 1. Осталось поработать с нодом 2^k и m.

Подсказка 5:

Исходя из выбора k, ясно, что нод 2^k и m не превышает 2^{k – 1}. Попробуйте теперь показать, что ноды выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с a^m – 1 совпадают. Кажется, это раскроет идею подсказки 3.

Подсказка 6:

Стало быть, a^{2^{k – 1}} + 1 — точный квадрат. А вас это не смущает?

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

Заметим, что для $n= 1$ подойдёт $a =10.$ Для $n =2$ подойдёт $a= 8.$

Предположим, что для $n =3$ нашлось требуемое число $a.$ Тогда число

2 3 3 2 (a − 1)(a − 1)(a − 1)= (a− 1) (a +1)(a + a+ 1)

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

2 a + a+ 1= a(a+ 1)+1,

числа $a+ 1$ и $a2+ a+ 1$ взаимно просты. Раз число $a+1$ нечётно, числа $a+ 1$ и $a− 1$ также взаимно просты. Следовательно, числа $a+ 1$ и $(a− 1)(a2+a +1)$ — точные квадраты. В частности, число $a+ 1$ при делении на 3 может давать лишь остаток 0 или 1, а тогда число $a− 1$ не делится на 3. Отсюда

2 НО Д(a− 1,a + a+1)= НОД (a − 1,(a +2)(a − 1)+ 3)= НО Д(a − 1,3)=1,

значит, числа $a− 1$ и $a2 +a+ 1$ также являются точными квадратами. Но второе являться квадратом не может, поскольку

a2 < a2 +a+ 1< (a+1)2.

Противоречие.

Осталось доказать, что требуемого $a$ не существует при $n ≥4.$ Предположим, что такое $a$ нашлось. Возьмём такое натуральное $k ≥2,$ что $2k ≤n < 2k+1.$ Поскольку

a2k − 1= (a2k−1 − 1)(a2k−1 + 1),

число

(a− 1)(a2 − 1)...(an− 1)

представляется в виде произведения $2k−1 a +1$ и нескольких множителей вида $m a − 1,$ где $1≤ m ≤n$ и $k m ⁄=2 .$

Докажем, что множитель $2k−1 a +1$ взаимно прост со всеми остальными множителями в этом разложении. Пусть $2k−1 a + 1$ и $am − 1$ имеют некоторый общий делитель $d.$ Тогда и НОД $k a2 − 1$ и $am − 1$ кратен $d.$ Но

k k НОД(a2 − 1,am− 1)= aНОД(2 ,m)− 1.

Поскольку $k m ⁄= 2$ и $k+1 m ≤n < 2 ,$ число $m$ не может делиться на $k 2 .$ Таким образом, $k Н ОД(2,m )$ — степень двойки, не превосходящая $k−1 2 .$ Следовательно, $2k−1 a − 1$ делится на НОД $2k a − 1$ и $m a − 1,$ а, значит, делится и на $d.$ Поскольку $a$ чётно, числа $2k−1 a − 1$ и $2k−1 a + 1$ не имеют общих делителей, отличных от 1, значит, $d= 1,$ что и требовалось.

Множитель $2k−1 a + 1$ взаимно прост со всеми остальными множителями в произведении, являющемся точным квадратом, поэтому он сам является точным квадратом. Тогда $k−1 a2 +1$ и $k−1 a2$ — отличающиеся на 1 квадраты натуральных чисел, что невозможно. Значит, наше предположение неверно, и для $n≥ 4$ требуемых чисел $a$ не найдётся.

Ответ:

$n =1$ и $n =2$

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

Задача 4#78906

Найдите все такие составные числа $n,$ что для любого разложения на два натуральных сомножителя $n= xy$ сумма $x +y$ является степенью двойки.

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

Подставив $x= 1,y = n,$ получим, что $n= 2k− 1$ для некоторого натурального $k.$ Пусть $n =ab,$ где $a≥ b>2,$ и пусть $a +b= 2t$ для некоторого натурального числа $t.$ Очевидно, что $k >t.$ Тогда

k t 2 +2 = ab+ a+b+ 1= (a+ 1)(b+1), 2k− 2t = ab− a− b+ 1= (a− 1)(b− 1)

Перемножив эти равенства, получим, что число $(a − 1)(a +1)× (b− 1)(b+ 1)$ делится на $2t 2 .$ Но двойка входит в одно из чисел $b− 1$ или $b+1$ в первой степени, а во второе — в степени, не большей $t− 1.$ Аналогично для чисел $a − 1$ и $a+ 1.$ Следовательно, делимость на $2t 2$ возможна, только если в обеих упомянутых оценках двойки входит в степени ровно $t− 1.$ Это возможно, лишь если $t−1 t−1 b= 2 − 1,a =2 + 1$ (поскольку $a≥ b$ и $t a+b =2$ ). Тогда $k= 2t− 2$ и $k 2 − 1$ делится на $3.$ Значит, можно считать, что в наших рассуждениях выбрано $b =3.$ Тогда $a= 5,$ и $n= 15$ — единственное подходящее число.

Ответ:

$n =15$

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

Задача 5#85447

На доске в ряд написаны $2n$ простых чисел. Известно, что среди них менее $n$ различных. Докажите, что можно выбрать несколько подряд идущих написанных чисел, произведение которых является точным квадратом.

Источники: Ломоносов-2016, 11.8 (см. olymp.msu.ru)

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

Рассмотрим произведения первых $k$ чисел в ряду. Всего таких произведений $2n+ 1$ (также учитваем произведение, в котором $0$ простых чисел, будем считать, что оно равно $1$ ).

Ясно, что произведение чисел любой подпоследовательности этого ряда — частное каких-то двух произведений первых чисел.

Пусть ряд состоит из чисел $p1,p2,...,pk(k ≤n − 1).$ Тогда любое произведение первых чисел имеет вид $α1 α2 αk p1 p2 ...pk .$ Если мы найдём два произведения первых чисел, у которых чётности соответствующих $αi$ совпадают, то мы найдём подпоследовательность ряда, произведение чисел которой равно квадрату.

Всего существует $k 2$ наборов чётностей $αi$ (каждое $αi$ либо чётное, либо нет). Осталось заметить, что $k n−1 n 2 ≤ 2 < 2 + 1.$ Значит, найдутся два произведения с одинаковым набором чётностей у $αi,$ получили требуемое.

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

Задача 6#96953

Натуральные взаимно простые в совокупности $a,$ $b,$ $c$ таковы, что $ab= c(a − b).$ Докажите, что $(a− b)$ — точный квадрат.

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

Подсказка 1

Давайте докажем от противного, что любое простое число p входит в a и b в одной степени.

Подсказка 2

Рассмотрим простой делитель p, который входит в a и b в какой-то степени. Предположим, что эти степени не равные между собой, также не равны 0. Что тогда можно сказать о данном равенстве?

Подсказка 3

Докажем, что в таком случае равенство не будет выполняться. Но как это сделать?

Подсказка 4

По условию, a, b и c взаимно просты в совокупности, это поможет нам доказать необходимое!

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

Рассмотрим произвольный простой делитель $p.$ Пусть его степени вхождения в $a$ и $b$ ненулевые и не равны, тогда в разность $a − b$ $p$ войдёт в минимальной из степеней вхождения в $a$ и $b,$ при этом $c$ на $p$ не делится, ведь $a,b,c$ взаимно проcты в совокупности. Получили, что степени вхождения $p$ в левую и правую части не равны. Значит, для любого $p$ на которое делится $a− b$ оно входит в $a$ и $b$ в равных степенях, то есть степень его вхождения в $a − b$ чётна, откуда следует, что $(a− b)$ — точный квадрат.

Курсы

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

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

Задача 7#100473

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

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

Подсказка 1

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

Подсказка 2

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

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

Предположим, что в наборе существует число $d,$ кратное простому числу $p,$ большему $3.$ Тогда для любых трех чисел $a,b,c$ набора, отличных от $d$ верно, что

4 4 4 4 4 4 4 a + b +c ≡ a + b +c + d ≡abcd≡ 0 (mod p) (∗)

В частности, для произвольного числа $e$ набора, отличного от чисел $a,b,c,d$

4 4 4 4 4 4 a +b + c ≡0 ≡b + c +e (mod p)

Таким образом,

a4 ≡ e4 (mod p)

для любых двух различных чисел набора, отличных от $d.$ Пусть $q$ — остаток при делении числа $a4$ на $p,$ тогда в силу $(∗)$

0≡ a4+b4+ c4 ≡3q4 (mod p)

следовательно, $q$ кратно $p,$ то есть все числа набора кратны $p,$ что невозможно, следовательно, среди чисел набора не существует числа, которое имело бы простой делитель, больший $3.$

Таким образом, все числа набора суть степени тройки. Поскольку все числа набора взаимно просты в совокупности, в наборе участвует единица. Тогда для произвольных чисел $3x,3y,3z > 1$ набора

1+ 34x+ 34y +34z кратно 3x+y+z

что неверно, поскольку

1 +34x+ 34y+ 34z ≡1 (mod 3)

следовательно, такого набора не существует.

Ответ:

Нет, не существует

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

Задача 8#100477

На доске в ряд выписано $2n$ простых чисел, среди которых не более, чем $n$ различных. Докажите, что существует несколько подряд идущих чисел, произведение которых является точным квадратом.

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

Подсказка 1

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

Подсказка 2

Количество различных чисел в нашей последовательности ограничено, значит, все числа имеют понятный вид! Осталось разделить отношение первых k на отношение первых m и понять, при каком условии получается точный квадрат!

Подсказка 3

Верно! Все произведения подряд идущих чисел являются произведениями степеней простых, содержащихся в нашем ряде. Тогда степени вхождений соответствующих простых по четности совпадают. Осталось доказать, что найдутся два набора, у которых степени простых совпадают по четности! Как это сделать?

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

Пусть ряд состоит из чисел $p1,p2,...,pk(k ≤n).$ Тогда любое произведение первых чисел имеет вид $α1 α2 αk p1 p2 ...pk .$ Если мы найдём два произведения первых чисел, у которых чётности соответствующих $αi$ совпадают, то мы найдём подпоследовательность ряда, произведение чисел которой равно квадрату.

Всего существует $k 2$ наборов чётностей $αi$ (каждое $αi$ либо чётное, либо нет). Осталось заметить, что $k n n 2 ≤2 < 2 + 1.$ Значит, найдутся два произведения с одинаковым набором чётностей у $αi,$ получили требуемое.

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

Задача 9#61649

Известно, что делители всякого “неквадратного” (не является точным квадратом) числа можно разбить на пары (у “квадратного” числа нечётное количество делителей, в связи с чем разбить на пары невозможно) так, чтобы произведения делителей в каждой паре были равными. Например, $18= 1⋅18= 2⋅9= 3⋅6.$ А существуют ли “неквадратные” числа, все делители которых можно разбить на тройки так, чтобы произведения делителей в каждой тройке были равными?

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

Подсказка 1

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

Подсказка 2

Перемножаем все эти k троек делителей и получаем x в степени k. А теперь воспользуемся утверждением из условия о том, что любое "неквадратное" можно разбить на пары делителей с равными произведениями! Давайте посчитаем аналогично: чему равно произведение тех же самых всех 3k делителей, если в каждой паре произведение n?

Подсказка 3

Перемножаем и получаем n в степени 3k/2 (пополам 3k делителей разбиваются на пары). Осталось найти какое-то противоречие, что произведение всех делителей равно x^k и одновременно n^(3k/2). Попробуйте свести это к тому, что квадрат равен кубу "неквадратного" числа, и порассуждать в терминах разложения на простые множители :)

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

Предположим, что существует такое не являющееся точным квадратом натуральное число $n> 1,$ у которого $k$ делителей бьются на тройки с произведением $t$ в каждой тройке. Тогда произведение $P$ всех делителей равно $k∕3 t .$

С другой стороны, если число $n$ не является точным квадратом, то его делители можно разбить на пары с произведением $n$ (если число $n$ делится нацело на $√ - m < n,$ то оно делится нацело и на $n- -n- √- m > √ n = n$ ). Так что делители бьются на пары с произведением $n$ в каждой, откуда $k∕2 P = n .$

В итоге

P = tk∕3 = nk∕2 =⇒ t2 = n3

Так как число $n$ не является точным квадратом, то в его разложении на простые множители найдётся какой-то простой делитель в нечётной степени. При возведении в куб степень этого простого делителя останется нечётной. Получаем противоречие с равенством $t2 = n3$ (в левой части равенства все простые делители должны быть в чётной степени, а справа есть делитель в нечётной степени).

Ответ:

нет

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

Задача 10#72108

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

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

Подсказка 1

Работать напрямую с условием, что число — степень выше первой, неудобно. Лучше перейти к простым множителям: как выглядит разложение на простые у таких чисел?

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Рассмотрите простое p, взаимно простое с первым членом прогрессии и её разностью. Возьмите достаточно много первых членов прогрессии и посмотрите на их остатки по модулю p².

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

Если натуральное число делится на некоторое простое число $p,$ но не делится на $p2,$ то оно точно не является степенью выше первой. Попробуем найти такой член в прогрессии. Пусть $a1$ — первый член, $d$ — разность. Возьмём простое число, на которое не делятся $a1$ и $d.$ Среди первых $p$ членов точно найдётся такой член $x,$ который делится на $p$ (потому что эти члены дают попарно разные остатки при делении на $p$ ). Этот член является хотя бы второй степенью, значит, он делится и на $2 p .$ Рассмотрим член $x+pd.$ Ясно, что он делится на $p,$ но не на $2 p.$ То есть такой последовательности нет.

Ответ:

Не существует

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

Задача 11#73160

Найдите все натуральные $m$ такие, что $33+ 66+...+(3m)3m$ является квадратом натурального числа.

Источники: автор И. А. Ефремов

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

Подсказка 1

В первом слагаемом 3 входит в 3 степени. А в остальных?

Подсказка 2

Верно! Все остальные слагаемые делятся 3⁴, а первое не делится. Какой вывод можно сделать?

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

Заметим, что все слагаемые кроме первого делятся на $34$ , а первое слагаемое делится только на $33$ . Тогда и все выражение делится ровно на третью степень тройки, то есть не может быть точным квадратом.

Ответ: таких нет

Интенсивы

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

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

Задача 12#75901

Решите в целых числах уравнение $5x3+ x2y− y3 =0.$

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

Запишем равенство в следующем виде: $5x3 =y3− x2y.$ Если какая-то из переменных равна $0,$ то вторая тоже равна $0.$ Пусть теперь $x,y$ ненулевые и степень вхождения $5$ в $x$ равна $a,$ а в $y$ — $b.$ Если $a =b,$ то в левой части степень вхождения $5$ равна $3a+ 1,$ а в правой $3a.$ Получаем противоречие, так как пять входит в левую часть в большей степени, чем в правую. Пусть теперь $a ⁄=b.$ Тогда в левую часть $5$ входит в степени $3a+ 1,$ а в левую — $min{3b,2a+ b},$ причём эти числа не равны между собой. Ясно, что эти степени вхождения должны быть равными, иначе равенства не будет. Однако $3b⁄=3a+ 1,$ потому что остатки при делении на $3$ разные. Значит, $3a+ 1= 2a+ b$ и получаем $a+ 1= b.$ Пусть тогда $a x= 5 t,$ а $a+1 y = 5 z,$ причём $t$ и $z$ не содержат степени пятёрок. Запишем теперь в новых обозначениях наше уравнение, сократим максимальную степень пятёрки и разложим на скобки выражение. Получаем

53a+1t3 =53a+3z3− 53a+1t2z

3a+13 3a+1 23 2 5 t = 5 (5z − tz)

3 t =z(5z− t)(5z+ t)

Пусть $t$ и $z$ имеют НОД $d$ не равный $1.$ Но тогда после его сокращения(слева $d3$ и из каждого множителя справа получается $d3$ ) правая часть будет делиться на какой-то простой множитель, входящий в $z,$ но в левой части его не будет. Противоречие. В ином случае получаем, что $t= z,$ но тогда они равны нулю, поэтому и $x =y =0.$ Этот случай уже рассмотрен.

Ответ:

$(0,0)$

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

Задача 13#75903

Натуральные числа $a,b,c$ таковы, что $a + b+ c b c a$ — целое. Докажите, что $abc$ — точный куб.

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

Подсказка 1

Заметим, что можно предполагать, что числа взаимно просты в совокупности. Рассмотрим простое число p, которое делит abc. Сколько из чисел a, b, c на него могут делиться?

Подсказка 2

Поскольку мы уже предполагаем, что числа a, b, c взаимно просты в совокупности, то все 3 числа делиться на p не могут. А может ли делиться ровно одно?

Подсказка 3

Верно, не может! Если привести три дроби к общему знаменателю, то видно, что c²b должно делиться на a, а если только a делится на p, то это невозможно. Тогда p содержится в двух числах. Пусть в число a оно входит в степени m, а в число b в степени n. В каких степенях оно входит в слагаемые числителя исходного выражения после приведения к общему знаменателю?

Подсказка 4

Верно! В a²c в степени 2m, в c²b в степени n, а в b²a в степени 2n + m. Можно ли теперь как-то сравнить m и n?

Подсказка 5

Верно, 2m ≥ n из соображений делимости! А может ли 2m быть больше n?

Подсказка 6

Не может! Если 2m ≥ n + 1, тогда знаменатель делится на (n+1)-ю степень p, а тогда и c²b на нее делится. В какой степени тогда p входит в abc?

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

Приведём дроби к одному знаменателю: $a2c+b2a+c2b. abc$ Будем считать, что переменные взаимно просты, иначе можно просто сократить на НОД. Пусть некоторое простое число $p$ входит в $abc$ в некоторой натуральной степени. Все переменные на $p$ делиться не могут. Пусть на $p$ делится только одна переменная, например $a.$ Чтобы дробь была целой, необходимо, чтобы $2 cb$ делилось на $a,$ но этого не может быть, поскольку $2 cb$ не делится на $p,$ а $a$ — делится.

Значит, число $p$ распределено по двум переменным. Пусть оно входит в $a$ в степени $m,$ а в $b$ — в степени $n.$ Тогда в $2 ac$ оно входит в степени $2m,$ в $2 b a$ — в степени $2n +m,$ в $2 c b$ — в степени $n.$

Ясно, что $2m ≥ n,$ поскольку знаменатель, а также второе и третье слагаемые числителя делятся на $n p ,$ а значит и $2 a c$ делится на $n p .$ Значит степень вхождения $p$ в $2 a c$ не меньше $n.$ Предположим, что $2m ≥n +1.$ Заметим, что знаменатель делится на $n+1 p ,$ так как он делится на $n+m p ,$ а $n+ m ≥n+ 1.$ Также на $n+1 p$ делятся первое и второе слагаемые числителя. Значит, на $n+1 p$ делится и $c2b,$ однако $p$ входит в это число лишь в степени $n.$ Значит, $2m = n,$ то есть $p$ входит в $abc$ в степени $3m.$ В силу произвольности выбора $p$ получаем требуемое.

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

Задача 14#75904

Найдите все натуральные $a$ и $b,$ для которых

----1---- ----1---- --1-- НОК(a2,b3) + НО К(b2,a3) =2023ab

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

Для удобства обозначим первый НОК через $m,$ а второй, через $n.$ Тогда равенство можно записать в виде $2023ab(m + n)=mn.$ Рассмотрим произвольное простое число $p.$ Пусть оно входит в $a$ в степени $x,$ а в $b$ — в степени $y.$ Тогда в $m$ оно входит в степени $max{2x,3y},$ в $n$ — в степени $max{2y,3x}.$ Значит, в $mn$ оно входит в степени $max {2x,3y} +max{2y,3x}.$

Теперь оценим степень вхождения $p$ в левую часть равенства:

vp(2023ab(m + n))= vp(2023)+x +y+ vp(m + n)≥vp(2023)+x +y +min{max{2x,3y},max{2y,3x}}

Степени вхождения в левой и правой части равны, поэтому

max{2x,3y}+ max{2y,3x}≥ vp(2023)+ x+ y+ min{max{2x,3y},max{2y,3x}}

Запишем $min{max{2x,3y},max{2y,3x}}$ как

max {2x,3y}+max {2y,3x} − max{max{2x,3y},max{2y,3x}}= max{2x,3y}+ max{2y,3x}− max{3x,3y}

и приведём подобные. Получим, что $max{3x,3y} ≥vp(2023)+x +y.$

Заметим, что строгий знак в полученном неравенстве возможен лишь когда $max{2x,3y}= max{2y,3x}.$ Также отметим, что последнее равенство возможно лишь когда $x =y.$ Действительно, если $max{2x,3y}= 2x,$ то $max{2y,3x} =2y,$ иначе равенство $max{2x,3y} =max {2y,3x}$ будет верным лишь при $x =y =0.$ Аналогично рассматривается другой случай. Предположим, что $x= y$ . Если равенство $x =y$ верно для любого простого $p$ , то $a= b$ . Тогда уравнение примет вид: $a3 = 4046a2,$ а значит $a =b= 4046.$

Пусть существует такое $p,$ для которого $x⁄= y,$ тогда $max{3x,3y}= vp(2023)+ x+ y.$ Уравнение симметрично, поэтому пусть $x> y,$ тогда равенство примет вид $2x= y+v (2023). p$ Правую часть можно оценить сверху: $y+v (2023)< x+ v(2023), p p$ то есть $2x< x+ v (2023), p$ откуда $x< v(2023). p$ Простое число может входить в $2023$ в степени $2,$ если оно равно $17,$ в степени $1,$ если оно равно $7,$ в степени $0$ в иных случаях. Однако $x >y ≥0,$ поэтому $v(2023)> 1. p$ Значит, $v (2023)=2,p= 17,x =1,y = 0. p$ Получается, что если такое $p$ существует, то оно равно $17$ и входит в одно число в первой степени, а в другое — в нулевой. То есть либо $a= 17t,b= t,$ где $t$ не кратно $17,$ либо наоборот. Подставим $a= 17t,b= t$ в равенство и получим $t= 126,$ откуда $a= 2142,b= 126.$ Учитывая симметрию, запишем ответ.

Ответ:

$(4046,4046),(126,2142),(2142,126)$

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

Задача 15#75905

Натуральное число $b$ назовем удачным, если для любого натурального $a,$ такого, что $a5$ делится на $b2,$ число $a2$ делится на $b.$ Найдите количество удачных чисел, меньших $2023.$

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

Лемма. Число $b$ является удачным тогда и только тогда, когда каждое простое число входит в разложение $b$ на простые множители с одним из следующих показателей: $0,1,2,3,4,6,8.$

Доказательство. Назовем целое неотрицательное число $k$ счастливым, если не существует такого целого $m,$ что $2m < k≤ 2,5m.$ Заметим, что счастливыми являются в точности числа $0,1,2,3,4,6,8.$ При $k ≤9$ в этом можно убедиться прямой проверкой. Если же $k >9,$ то выберем такое максимальное число $m,$ что $2m< k.$ Тогда $m > 4,$ и $2,5m > 2m+ 2= 2(m + 1)>k$ по выбору $m,$ то есть $k$ несчастливо.

Пусть число $b$ неудачно, то есть $5 a$ делится на $2 b,$ но $2 a$ не делится на $b$ для некоторого $a.$ Тогда некоторое простое $p$ входит в разложение $2 a$ в меньшей степени, чем в разложение $b.$ Пусть $p$ входит в разложения $a$ и $b$ в степенях $m$ и $k$ соответственно; тогда $2m < k,$ но $5m ≥2k.$ Значит, число $k$ — несчастливое. Итак, если все степени вхождения простых чисел в $b$ счастливы, то $b$ удачно.

Если же $b= pkb′,$ где $b′$ не кратно $p$ и $k$ несчастливо $(2m <k ≤2,5m),$ то при $a =pmb′$ число $a5$ делится на $b2,$ а $a2$ не делится на $b,$ то есть $b$ неудачно.

Согласно лемме, каждое неудачное число имеет простой делитель, входящий в разложение на простые множители с показателем $5,7$ или более $8.$ Поскольку $210 < 2023 <211,36 < 2023 <37,25⋅35 >2023$ и $55 >2023,$ каждое неудачное число, меньшее $2023,$ принадлежит одному из следующих непересекающихся классов:

$1)$ Числа вида $25q,$ где $q$ нечётно и $q ≤ 63(25⋅63< 2023< 25⋅65);$

$2)$ Числа вида $27q,$ где $q$ нечётно и $q ≤ 15(27⋅15< 2023< 27⋅17);$

$3)$ Числа вида $29q,$ где $q = 1$ или $3(29⋅3< 2023< 29⋅5);$

$4)$ Число $210;$

$5)$ Числа вида $35q,$ где $q$ не кратно $3$ и $q ≤ 8(35⋅8< 2023< 35⋅10).$

Таким образом, общее количество неудачных чисел, меньших $2010,$ равно $32+ 8+ 2+1 +6= 49,$ а количество удачных чисел равно $2009− 49 =1960.$

Ответ:

$1960$

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

Задача 16#94019

Для натурального числа $n$ обозначим через $S n$ наименьшее общее кратное всех чисел $1,2,3,...,n.$ Существует ли такое натуральное число $m,$ что $Sm+1 = 4Sm?$

Источники: Всеросс., 2023, РЭ, 9.6(см. olympiads.mccme.ru)

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

Подсказка 1

Предположим, что это возможно и посмотрим на максимальную степень двойки, которую можно найти среди первых n+1 чисел. А что можно сказать о степени двойки, которую можно найти среди первых n чисел?

Подсказка 2

Верно! Если максимальная степень двойки среди первых n+1 чисел равна k, то среди первых n точно не меньше k/2. Какой вывод можно сделать?

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

Предположим, что такое $m$ существует. Пусть $S m+1$ делится на $2s,$ но не делится на $2s+1.$ Тогда $s≥ 2.$ Значит, среди чисел $1,...,m+ 1$ есть число $a$ , делящееся на $s 2 .$ Но тогда число $a∕2$ делится на $s−1 2 ,$ поэтому $Sm$ делится на $s−1 2 .$ Тогда, поскольку $Sm+1 = 4Sm,$ то $Sm+1$ делится на $s+1 2 ,$ что неверно.

Ответ:

Нет

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

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

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

Задача 17#35518

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

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

Рассмотрим 16 различных простых чисел. Обозначим их через $p,p ,...,p 1 2 16$ . Через $x$ обозначим квадрат их произведения. Возьмем наши 16 чисел, равными $x--x -x- p1,p2,...,p16$ . Заметим, что в произведение двух любых наших чисел каждое из 16 простых чисел входит хотя бы во второй степени. Но в каждом из наших чисел каждое простое входит в 1 или во второй степени, поэтому произведение любых 2 чисел будет делиться на любое число. Сами числа друг на друга очевидно не делятся (у каждого свое уникальное простое входит в разложение в первой степени, остальные простые — во второй).

Ответ: Существуют

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

Задача 18#35519

Про натуральные числа $m$ и $n$ известно, что $3n3 = 5m2$ . Найдите наименьшее возможное значение $m +n$ .

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

Обозначим через $n 3$ и $m 3$ степени вхождения числа $3$ в $n$ и $m$ соответственно. Тогда из равенства степени вхождения 3 в правую и левую части получаем, что $3n3+1 =2m3$ . Из этого условия легко видеть, что $m3 ≥ 2$ , $n3 ≥1$ . Проделаем аналогичные рассуждения для числа 5. Введя аналогичные обозначения, получаем, что $2m5+ 1= 3n5$ , откуда $n5 ≥ 1$ , $m5 ≥1$ . Таким образом, мы доказали, что $n ≥3⋅5 =15$ , $m ≥ 9⋅5 =45$ . Тогда $m + n≥ 15 +45= 60$ . Легко видеть, что такая сумма могла оказаться, так как $3 2 3⋅15 = 5⋅45$ .

Ответ: 60

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

Задача 19#94020

Для натурального числа $n$ есть ровно два из чисел $1,2,...,2022,$ на которые оно не делится. Пусть эти числа — $a$ и $b.$ Может ли оказаться, что $a− b =13?$

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

Подсказка 1

Попробуем идти от противного. Сразу ясно, что одно из чисел a или b четно. Назовем это число 2k. Может ли n не делиться на k?

Подсказка 2

Если n не делится на k, то k и 2k — те самые числа, на которые n не делится. Тогда k = 13. Может ли так получиться?

Подсказка 3

Верно, не может! Тогда n не делится на 39 и многие другие числа. Тогда выходит, что n не делится именно на 2k. А по какой причине?

Подсказка 4

Верно! Из-за того, что степень вхождения двойки в 2k больше, чем в n. А какой вывод можно сделать тогда о делимости n на степени двойки?

Подсказка 5

Верно! Тогда n не делится на наибольшую степень двойки 1024, которая есть среди наших чисел. А на какое число тогда наше n еще не делится?

Подсказка 6

Верно, n не делится на 1011 и 1037! Являются ли эти числа простыми?

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

Будем рассуждать от противного. Тогда одно из чисел $a$ и $b$ — чётное. Обозначим это число через $2k.$ Если $n$ не делится на $k,$ то $k$ и $2k$ как раз и есть два числа из $1,2,...,2022,$ на которые не делится $n.$ Поэтому $2k− k= 13,$ откуда $k= 13.$ Но тогда $n$ не делится также на число $39,$ и чисел, на которые не делится $n,$ хотя бы $3.$

Значит, $n$ не делится на $2k$ потому, что в $2k$ двойка содержится в большей степени, чем в $n.$ Тогда $n$ не делится на наибольшую степень двойки среди $1,2,...,2022,$ то есть на $1024.$ Таким образом, пара чисел, на которые не делится $n$ — это $(1024,1037)$ или $(1011,1024).$ Но $1037= 17⋅61$ и $1011= 3⋅337,$ поэтому в обоих случаях $n$ не делится также на одно из простых чисел $17,61,3$ или $337.$

Ответ:

Нет, не может

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

Задача 20#89085

На доске написаны $2n$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего числа меньшее, все замены происходят одновременно). Докажите, что на доске больше никогда не появятся $2n$ последовательных целых чисел.

Источники: ММО - 2020, первый день, 11.6(см. mmo.mccme.ru)

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

Подсказка 1

Каким способом можно доказать, что состояние фиксированного объекта в процессе его изменения не приведёт к тому, что он примет начально состояние?

Подсказка 2

Найти полуинвариант! Давайте найдем величину, которая будет меняться монотонно в ходе процесса, и, как следствие, не вернется к изначальному состоянию.

Подсказка 3

Как найти полуинвариант в данной задаче? В условии задачи сказано, что при замене двух чисел x и y на их сумму x+y, второе число равно x-y или y-x. Было бы хорошо, если бы наш полуинвариант вел себя одинаково вне зависимости от этого выбора. Ясно, что данные числа равны по модулю. Как это помогает найти полуинвариант?

Подсказка 4

Пусть S является искомым полуинвариантом. Ясно, что S - это функция от набора чисел, написанных на доске в данный момент. Если мы положим в качестве S функцию от их квадратов, то значение S будет совпадать при выборе любой из разности чисел (x-y или y-x), что является хорошим знаком. Осталось доопределить S.

Подсказка 5

Самые естественные функции от набора переменных - их сумма или произведение. С суммой в данном случае работать проще (итак, в качестве предполагаемого полуинварианта мы пока положим S - сумму квадратов чисел написанных на доске), поскольку мы можем легко получить значения данного полуинварианта на каждом ходу. Поймите, как это можно сделать.

Подсказка 6

Если на доске были написаны числа x² и y², то сумма их квадратов измениться на (x-y)²+(x+y)²=2(x²+y²). Таким образом, значение S после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 2n идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?

Подсказка 7

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

Подсказка 8

Пусть 2n=l*2^k, где l - нечетное натуральное число, k - натуральное число, не меньшее 1. Докажите, что степень вхождения двойки в сумму квадратов 2n последовательных чисел равна k-1.

Подсказка 9

Искомую сумму можно представить как l сумм 2^k последовательных квадратов натуральных чисел. Если мы докажем, что каждая из них имеет вид 2^{k-1}t, для некоторого нечетного числа t, то явно получим, что и вся сумма делится на 2^{k-1}, но не делится на 2^k. Сделайте это!

Подсказка 10

Рассмотрим сумму последовательных 2^k квадратов по модулю 2^k. Квадраты этих чисел имеют тот же набор остатков при делении на 2k, что и набор чисел 1², 2², 3²,..., (2^k)², а значит сравнимо по этому модулю c суммой 1²+2²+...+(2^k)². Каким образом ее можно преобразовать?

Подсказка 11

По известной формуле суммы квадратов первых n чисел, 1²+2²+...+(2^k)²=2^{k-1}(2^k+1)(2^{k+1}+1)/3 - кратно 2^{k-1}, но не кратно 2^k. Это как раз то, что мы хотели показать!

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

Рассмотрим набор из $2k$ подряд идущих чисел, квадраты этих чисел имеют тот же набор остатков при делении на $2k,$ что и набор чисел $2 2 2 ( k)2 1 ,2,3,..., 2 .$ Поскольку

2 2 2 ( k)2 1 +2 + 3 + ...+ 2 (= )( ) ( )( ) = 2k-2k+-1-2-⋅2k+-1-= 2k−12k+-1-2⋅2k-+1-- 6 3

сумма квадратов $k 2$ подряд идущих чисел делится на $k−1 2 ,$ но не делится на $k 2 .$

Представим число $2n$ в виде $k 2 ⋅l,$ где $l$ нечётно. Тогда сумма $2n$ последовательных квадратов разбивается на $l$ сумм вида $k−1 2 ti,$ где все $ti$ нечётны, поэтому вся сумма также делится на $k−1 2 ,$ но не делится на $k 2.$ Следовательно, наибольшая степень двойки, на которую делится сумма квадратов $2n$ последовательных чисел, зависит только от $n,$ но не от самих чисел.