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

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

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

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

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

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

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

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

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

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

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

Рассмотрим произвольный простой делитель $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$ различных натуральных чисел, взаимно простых в совокупности, что сумма четвертых степеней любых четырех чисел из этого набора делится на произведение этих четырех чисел?

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

Предположим, что в наборе существует число $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)

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

Ответ:

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

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

Задача 5#100477

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

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

Пусть ряд состоит из чисел $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.$ А существуют ли “неквадратные” числа, все делители которых можно разбить на тройки так, чтобы произведения делителей в каждой тройке были равными?

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

Предположим, что существует такое не являющееся точным квадратом натуральное число $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$ является квадратом натурального числа.

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

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

Заметим, что все слагаемые кроме первого делятся на $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$ — точный куб.

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

Приведём дроби к одному знаменателю: $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#94019

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

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

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

Предположим, что такое $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 ,$ что неверно.

Ответ:

Нет

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

Задача 14#35518

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

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

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

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

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

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

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

Задача 16#94020

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

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

Будем рассуждать от противного. Тогда одно из чисел $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.$

Ответ:

Нет, не может

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

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

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

Задача 17#89085

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

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

Рассмотрим набор из $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$ подряд идущих чисел нельзя.

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

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

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

Задача 19#91081

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

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

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

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

Ответ:

нельзя

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

Задача 20#75971

Тройка целых чисел $(x,y,z),$ наибольший общий делитель которых равен $1,$ является решением уравнения

2 2 3 2 2 y z+ yz =x + x z− 2xz

Докажите, что $z$ является кубом целого числа.

Источники: Высшая проба - 2017, 11.4(см. olymp.hse.ru)

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

Запишем равенство в следующем виде: $z(y2+ yz− x2 +2xz)= x3.$ Если мы докажем, что НОД $z$ и $y2+yz− x2+ 2xz$ равен $1,$ то тогда $z$ будет кубом. Предположим, что $z$ в этой ситуации не является кубом. Тогда в разложение $z$ входит какое-то простое число $p$ в степени, не кратной $3.$ Скобка $2 2 y + yz− x +2xz$ на $p$ не делится, значит $p$ входит в $3 x$ в степени, не кратной $3,$ чего быть не может.

Итак, докажем взаимною простоту $z$ и $2 2 y + yz− x + 2xz.$ Ясно, что НОД этих чисел равен НОДу $z$ и $2 2 y − x .$ предположим, что этот НОД равен $t> 1.$ Тогда $3 x$ делится на $t.$ Пусть $t$ делится на некоторое простое число $q,$ тогда на $q$ делится $x$ и $2 2 y − x .$ Значит, $y$ также делится на $q.$ Также $z$ делится на $t,$ а значит и на $q.$ Получается, что НОД $x,y$ и $z$ больше $1,$ противоречие. Значит, НОД $z$ и $2 2 y − x$ равен $1,$ что и требовалось.