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

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

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

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

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

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

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

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

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

Задача 1#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$

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

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

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

Задача 2#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,$ получили требуемое.

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

Задача 3#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)$ — точный квадрат.

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

Задача 4#100473

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

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

Подсказка 1

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

Подсказка 2

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

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

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

4 4 4 4 4 4 2 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+ 3x +3y+ 3z кратно 3x+y+z

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

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

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

Ответ:

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

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

Задача 5#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,$ получили требуемое.

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

Задача 6#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$ (в левой части равенства все простые делители должны быть в чётной степени, а справа есть делитель в нечётной степени).

Ответ:

нет

Курсы

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

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

Задача 7#72108

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

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

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

Ответ:

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

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

Задача 8#73160

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

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

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

Подсказка 1

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

Подсказка 2

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

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

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

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

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

Задача 9#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)$

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

Задача 10#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$ получаем требуемое.

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

Задача 11#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)$

Интенсивы

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

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

Задача 12#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$

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

Задача 13#92983

Натуральные числа $a,b,c,d,k$ таковы, что

ab a2-− b2 k= cd = c2− d2

Докажите, что число $k$ — точный квадрат.

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

Подсказка 1

Тут будет разумно рассмотреть произвольное простое число p. Если доказать, что оно входит в k в чëтной степени, задача решится.

Подсказка 2

Давайте обозначим степени вхождения p в a, b, c, d через x, y, z, t. Также давайте запишем равенство из условия как ab(c²-d²) = cd(a²-b²). Что можно сказать про степени вхождения p в левую и правую часть? А про степень вхождения p в k?

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

Перепишем равенство в виде $ab(c2− d2)=cd(a2− b2).$ Давайте возьмём произвольное простое $p$ и обозначим через $x,y,z,t$ его степени вхождения в $a,b,c,d.$ Степень вхождения $p$ в левую часть равна $x+ y+2min(z,t),$ а в правую — $z+ t+2min(x,y).$ То есть эти степени вхождения равны. Если приравнять их и заметить, что $x +y− min(x,y)= max(x,y)$ (аналогично для $z,t),$ то мы получим равенство

max(z,t)+ min(x,y)= min(z,t)+ max(x,y)

Давайте запишем его так:

max(z,t)− max(x,y)= min(z,t)− min(x,y)

Теперь же давайте заметим, что степень вхождения $p$ в $ab cd$ равна

(max(x,y)− max(z,t))+ (min(x,y)− min(z,t)) =2(max(x,y)− max(z,t))

То есть $p$ входит в $k$ в ӵeтной степени. В силу произвольности выбора $p$ получаем требуемое.

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

Задача 14#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 ,$ что неверно.

Ответ:

Нет

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

Задача 15#35518

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

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

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

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

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

Задача 16#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

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

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

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

Задача 17#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.$

Ответ:

Нет, не может

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

Задача 18#89085

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

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

Подсказка 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,$ но не от самих чисел.

В то же время сумма квадратов имеющихся чисел после замены удваивается. Действительно, заменив числа $a$ и $b$ на $a− b$ и $a+ b,$ получим:

( ) (a− b)2+ (a+ b)2 = 2a2+2b2 = 2 a2 +b2

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

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

Задача 19#75242

Найдите все натуральные $m$ и $n,$ удовлетворяющие равенству

n n n n−1 (2 − 1)(2 − 2)...(2 − 2 )= m!

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

Далее в решении, как обычно, $v (N) p$ — показатель наибольшей степени простого числа $p,$ делящей $N.$

Пусть $n n n ( n n− 1) Ln = (2 − 1)(2 − 2)(2 − 4)...2 − 2 .$ Тогда

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

следовательно,

n(n−-1) v2(Ln)= 1+2 +⋅⋅⋅+ (n− 1) = 2

С другой стороны, по формуле Лежандра, верно неравенство

∞∑ ⌊ ⌋ ∑∞ v2(m!)= mi < mi = m i=1 2 i=12

Приравнивая показатели, имеем

n(n-− 1) 2 = v2(Ln)= v2(m!)< m

Кроме этого заметим, что

Ln = (2n− 1)(2n− 2)⋅⋅⋅(2n − 2n−1)< (2n)n = 2n2

Мы хотим показать, что для всех $n ≥6$ верно

( ) 2n2 < n(n-− 1) 2

что влечет невозможность равенства $Ln = m!$ для указанных $n.$

Для $n =6$ имеем

( ) 262 < 6.9⋅1010 < 1.3 ⋅1012 < 15!< n(n−-1) 2

Пусть $n≥ 7,$ тогда

( n(n − 1)) n(n− 1) n(n−1)−15 --2----!= 15!⋅16⋅17 ⋅⋅⋅--2---->236⋅16 2 = 22n(n− 1)−24 = 2n2 ⋅2n(n−2)−24 >2n2

Таким образом, необходимо проверить выполнение исходного равенства для $n ≤5.$ Имеем

L1 = 1= 1!, L2 = 6= 3!, 5!< L3 = 168 <6!, 7!< L4 = 20160< 8! и 10!< L5 = 9999360< 11!

Наконец, уравнение имеет два решения

(m,n)∈ {(1,1),(3,2)}

Ответ:

$(1,1),(3,2)$

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

Задача 20#91081

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

Источники: Олимпиада Эйлера, 2019, дистанционный тур

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

Подсказка 1

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

Подсказка 2

Верно! Число 97 входит только в 4 факториала. Тогда, чтобы создать куб, один из них нужно вычеркнуть. А можно ли посмотреть теперь на какое-то другое простое число?

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

Если произведение оставшихся факториалов — куб натурального числа, то для любого простого числа степень, в которой оно входит в это произведение, должна делиться на $3.$ Простое число $97$ входит ровно в четыре факториала: от $97!$ до $100!,$ и в каждый — в первой степени. Поэтому вычеркнут должен быть один из этих четырех факториалов. Но тогда простое число $89$ будет входить ровно в $11$ факториалов: от $89!$ до $100!,$ исключая вычеркнутый. Противоречие.

Ответ:

нельзя

Предыдущий раздел

Следующий раздел