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

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

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

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

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

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

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

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

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

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

Дано натуральное число $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Максимум баллов за задание: 7

Степень вхождения простого числа $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Максимум баллов за задание: 7

Найдите все натуральные $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#128852Максимум баллов за задание: 7

Натуральные числа $a$ и $b$ таковы, что сумма $a2+ b2 b a$ целая. Докажите, что оба слагаемых целые.

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

Возьмём произвольное простое число $p.$ Пусть $v(a)=α, p$ $v(b) =β. p$ По условию число

a2 b2 a3+-b3- b + a = ab

является целым. Значит,

vp(a3+ b3)≥ vp(ab)= α+ β.

Возникает два случая, которые нужно рассмотреть: если $α= β$ и если $α⁄= β.$ В случае равенства мы не сможем вычислить $3 3 vp(a +b ),$ зато можно сразу сказать, что тогда $2α≥ β$ и $2β ≥ α,$ что в силу произвольности выбора $p$ даёт требуемое. Пусть теперь $α ⁄=β.$ Условие инвариантно относительно перестановки $a$ и $b.$ Значит, можно, не умаляя общности предположить, что $α <β.$ Тогда

vp(a3+ b3)= min(3α,3β)= 3α.

Следовательно, $3α ≥ α+ β,$ или же $2α ≥β.$ Это даёт делимость $2 a$ на $b,$ а делимость $2 b$ на $a$ вытекает из $β > α.$

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

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

Формула Лежандра. Пусть $p$ — простое число, $n$ — произвольное натуральное число. Тогда

∑ [ n-] vp(n!)= α≥1 pα .

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

Покажем, что это выражение равно сумме степеней вхождения $p$ в каждое из чисел от $1$ до $n.$ Заметим, что слагаемое $[ n-] pα$ равно количеству чисел, кратных $α p$ и не превосходящих $n.$ Отсюда следует, что число со степенью вхождения $p,$ равной $m,$ было посчитано по $1$ разу в каждом из слагаемых

[n] [ n] [ n] p , p2 ,..., pm-.

То есть оно было посчитано ровно $m$ раз. Получили требуемое.

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

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

Найдите все натуральные числа $m,n$ и простые числа $p,$ удовлетворяющие уравнению $mnnp = pm.$

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

В правой части стоит степень простого числа, поэтому в левой части единственным простым делителем является $p,$ то есть $m = pa,$ $b n =p .$ Подставим эти выражения в исходное равенство:

apb bp pa (p ) ⋅(p) = p

Степень вхождения $p$ с обеих сторон должна быть одинаковой:

b a ap + bp= p

Рассмотрим случай $b=0.$ Тогда $a =pa,$ но $a< 2a ≤ pa,$ так что это невозможно. Теперь вернёмся к равенству степеней вхождения $p.$ Поскольку в правой части стоит степень $p,$ степени вхождения $p$ в $apb$ и $pb$ должны быть равны. Значит, $pb−1|b$ и

b≥pb−1 ≥ 2b−1

Пусть $b≥3.$ Тогда $2b−1 > b,$ так что решений нет. При $b= 2$ получаем $p= 2$ и

4(a+ 1)= 2a

Это уравнение не имеет решений в целых числах. Теперь остался случай $b= 1.$ Равенство на степени вхождения превращается в

ap+ p= pa

Снова сделаем оценку $pa−1 ≥2a−1,$ то есть $a +1 ≥2a−1.$ Такое неравенство выполняется при $a ≤3.$ При $a= 0$ решений нет, при $a= 1$ решений тоже нет. При $a = 2$ получаем $p= 3, m = 9, n= 3.$ При $a= 3$ получаем $p= 2,$ $m =8,$ $n =2.$

Ответ:

$(m,n,p)=(8,2,2)$ или $(9,3,3)$

Курсы

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

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

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

Даны натуральные числа $m,n,k.$ Оказалось, что $mk + nk+m$ делится на $mn.$ Докажите, что $m$ — точная $k$ -я степень натурального числа.

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

Будем считать $k≥ 2,$ иначе утверждение очевидно. Пусть $p$ — простой делитель $m$ и $a$ — его степень вхождения. Пусть $b$ — степень вхождения $p$ в $n.$ Предположим, что $b= 0.$ Тогда выражение из условия не делится на $p,$ то есть не делится и на $mn.$ Итак, $b≥1.$ Посчитаем степень вхождения $p$ в $k k m + n +m.$ В $mn$ это $a+b >a.$ Значит, в $k k m + n + m$ степень вхождения $p$ строго больше, чем $a.$ Рассмотрим это выражение по модулю $a+1 p ,$ оно даёт остаток 0. Так как $ak ≥2a ≥a+ 1,$ то $k m$ делится на $a+1 p ,$ следовательно, $k n + m$ тоже. Но $m$ имеет степень вхождения $p$ в точности $a,$ поэтому такую же степень вхождения должно иметь и $k n.$ Значит, $a= kb,$ то есть степень вхождения $p$ в $m$ делится на $k,$ что и требовалось доказать.

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

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

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

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

Предположим противное. Пусть $d = a2, s$ $d = b2, s+1$ причем $a <b.$ Рассмотрим число $ab.$ Заметим, что $a2 <ab< b2,$ то есть $ds < ab< ds+1.$ В частности, число $ab$ не может являться делителем $n.$ Зафиксируем произвольное простое число $p.$ Обозначим через $α$ степень вхождения $p$ в $a,$ через $β$ — степень вхождения $p$ в $b.$ Тогда степень вхождения $p$ в число $ab$ равна $α+ β,$ что точно не превосходит большего из чисел $2α$ и $2β.$ Значит, число $ab$ также является натуральным делителем $n$ — противоречие.

Ответ:

не могло

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

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

Найдите все такие составные числа $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$

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

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

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

Предположим, что такой набор существует, $λ$ — наибольший общий делитель чисел этого набора. Тогда для любой четверки чисел $4 {λai}i=1$

4∏ ∑4 4∏ ∑4 λai | (λai)4, а значит, ai | a4i, i=1 i=1 i=1 i=1

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

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

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

Ответ:

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

Интенсивы

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

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

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

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

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

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

У натурального числа ровно 50 делителей. Может ли оказаться, что никакая разность двух различных его делителей не делится на 100?

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

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

Подсказка 1:

Ясно, что нужно смотреть на последние две цифры всех чисел. Если у каких-то двух они совпадают, то их разность будет делиться на 100.

Подсказка 2:

Давайте назовём последние две цифры числа "хвостом". Заметим, что хвост числа n даёт такие же остатки при делении на некоторые числа, что и само n.

Подсказка 3:

Если число делится на 5, может ли оно обладать таким свойством? Сколько у него будет делителей, кратных 5? А сколько всего существует "хвостов", кратных 5?

Подсказка 4:

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

Подсказка 5:

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

Подсказка 6:

Докажите, что количество делителей кратно r + 1. Для этого достаточно разбить делители некоторым образом на цепочки по r + 1 делителю в каждой.

Подсказка 7:

Используя всю информацию, попробуйте оценить количество нечётных делителей, делителей, кратных 2, но не 4, и кратных 4.

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

Предположим, что такое число $n$ существует. Условие равносильно тому, что все числа, образованные последними двумя цифрами делителей, различны (мы считаем, что к однозначным числам спереди приписаны нули). Назовём такую пару последних цифр хвостом числа. Заметим, что хвост числа имеет те же остатки от деления на $4$ и на $5,$ что и исходное число.

Предположим, что $n$ делится на 5. Тогда для любого его делителя $d,$ не кратного $5,$ существует и делитель $5d,$ кратный $5.$ При этом для разных делителей $d$ мы получаем разные делители $5d;$ поэтому количество кратных $5$ делителей не меньше половины, то есть не меньше $25.$ Но такие делители имеют хвосты, оканчивающиеся либо на $0,$ либо на $5.$ Таких возможных хвостов не больше $20,$ поэтому два из них совпадают. Это противоречие показывает, что $n$ не делится на $5,$ и хвосты его делителей не могут оканчиваться на $0$ или $5.$

Если число $n$ нечётно, то все его делители также нечётны. Однако существует всего $50$ возможных нечётных хвостов, и $10$ из них оканчиваются на $5,$ то есть не могут появиться. Поэтому и в этом случае найдутся два одинаковых хвоста.

Если число $n$ делится на $2,$ но не на $4,$ то все его делители разбиваются на пары $(d,2d),$ где $d$ — нечётный делитель $n.$ При этом все числа вида $2d$ имеют хвосты, не делящиеся на $4,$ а таких хвостов (при этом не делящихся на $5$ ) всего $20.$ Значит, два из этих хвостов одинаковы.

Наконец, пусть наибольшая степень двойки, на которую делится $n,$ равна $2r,$ где $r≥ 2.$ Тогда, если $d$ — нечётный делитель $n,$ то числа $d,$ $2d,$ $22d,$ …, $2rd$ также будут делителями $n,$ и этим исчерпываются все делители $n.$ Поэтому общее число делителей $n$ будет кратно $r+1.$ Таким образом, $50$ делится на $r+ 1$ и, значит, $r ≥4.$

Тогда $n$ имеет

-50-≤ 10 r+ 1

нечётных делителей и столько же делителей, которые чётны и не делятся на четыре. Стало быть, оставшиеся делители (которых не меньше $30$ ) кратны $4$ и, значит, их хвосты также кратны четырём. Но таких хвостов возможно лишь $20,$ поэтому опять два из них совпадут.

Ответ:

нет

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

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

Известно, что делители всякого “неквадратного” (не является точным квадратом) числа можно разбить на пары (у “квадратного” числа нечётное количество делителей, в связи с чем разбить на пары невозможно) так, чтобы произведения делителей в каждой паре были равными. Например, $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$ (в левой части равенства все простые делители должны быть в чётной степени, а справа есть делитель в нечётной степени).

Ответ:

нет

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

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

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

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

Подсказка 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.$ То есть такой последовательности нет.

Ответ:

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

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

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

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

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

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

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

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

Решите в целых числах уравнение $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)$

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

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

Натуральные числа $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$ получаем требуемое.

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

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

Найдите все натуральные $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)$

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

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

Натуральное число $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,$ принадлежит одному из следующих непересекающихся классов: