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

Оценочная теория чисел

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

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

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

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

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

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

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

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

Имеется натуральное число $n > 2015.$ Возьмём остатки от деления числа $2n$ на $2,3,4,...,n.$ Докажите, что сумма этих остатков больше $2n.$

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

Обозначим сумму остатков от деления $2n$ на числа $1,2,...,n$ через $S . n$ Мы докажем, что $S > 3,5n n$ при $n >1000.$

Числа $n 2$ не делится нацело ни на какое нечётное число, отличное от $1,$ значит, остаток от деления $n 2$ на такое число не меньше $1.$ Отсюда легко вывести, что для любого нечётного $k> 1$ остаток от деления $n 2$ на $l 2 k$ не меньше $l 2 .$

Отсюда следует, что

Sn ≥n0 +2n1+ 22n3 +...+ 2mnm

где $n i$ –– количество не превосходящих $n$ чисел вида $2i(2k +1),k > 1,$ а $m$ определяется условиями $32m ≤n ≤ 3⋅2m+1$ (нет смысла брать большее $m,$ так как тогда выражение в скобке будет равно нулю).

Рассмотрим $(i+1)$ -e слагаемое $2in. i$ Число $n i$ равно числу не превосходящих $n$ членов арифметической прогрессии $3⋅2i,5 ⋅2i,7 ⋅2i,...$ Число таких членов не меньше $n−3⋅2i, 2i+1$ и, значит, это слагаемое не меньше $n− 3⋅2i−1. 2$

Заменив сумму в правой части первыми восемью слагаемыми, получим

n −1 2 6 7 n Sn > 82 − 3(2 + 1+ 2+ 2 +...+ 2 )>4n − 3⋅2 = 3,5n +(2 − 384)

При $n >1000$ выражение в скобке положительно, то есть $Sn > 3,5n.$

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

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

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

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

Будем говорить, что мы укоротили число, если стерли его последнюю цифру. Натуральное число, большее миллиона, таково, что если укоротить его, получится квадрат натурального числа, если укоротить этот квадрат, получится куб натурального числа, укоротив этот куб, получим четвёртую степень натурального числа, а, укоротив эту четвёртую степень, получим пятую степень натурального числа. Докажите, что если укоротить эту пятую степень, то получится шестая степень натурального числа.

Источники: Олимпиада Эйлера, 2023, РЭ, 9 задача(см. old.mccme.ru)

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

Подсказка 1

Что можно сказать о числах после первого и третьего укорачиваний?

Подсказка 2

Верно! Они отличаются лишь двумя последними цифрами, и потому 100 ≥ n² - 100m⁴, где n² и m⁴ — соответственно число после первого и третьего укорачиваний. Как тогда связаны m и n?

Подсказка 3

Точно! n = 10m². Что тогда можно сказать о второй и третьей цифрах исходного числа?

Подсказка 4

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

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

Пусть число после первого укорачивания равно $n2,$ а после третьего — $m4.$ Тогда $100m4$ отличается от $n2$ только двумя последними цифрами, то есть $2 22 2 2 100 ≥n − (10m ) = (n− 10m )(n+ 10m )≥0.$ Так как по условию изначальное число больше миллиона, то $4 2 m ≥ 1000,10m > 100,$ что возможно только если $2 n =10m$ (иначе $2 2 (n− 10m )(n+ 10m )> 1⋅100$ ). Значит, вторая и третья цифры исходного числа — нули, и куб $3 k,$ получающийся после второго укорачивания, оканчивается на $0.$ Следовательно, четвертая и пятая цифры исходного числа — тоже нули (куб числа, делящегося на $10,$ делится и на $3 10$ ), и после пятого укорачивания мы получим число $k--3 -n-2 (100) = (100).$ Поскольку в разложение числа, являющегося одновременно точным квадратом и точным кубом, все простые множители входят в степенях, кратных $6,$ это число является точной шестой степенью.

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

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

На доску выписаны числа $1,2,3,...,2 00...0 2 1◟00◝н◜ул ◞ей$ . Можно ли покрасить половину этих чисел в красный цвет, а оставшиеся в синий так, чтобы сумма красных чисел делилась на сумму синих?

Источники: КМО - 2023, третья задача первого дня для 8-9 классов, автор Белов Д.А. (cmo.adygmath.ru)

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

Обозначим самое большое выписанное число через $2n$ . Минимальная сумма синих чисел равна

n(n+-1)- 1+ 2+...+n = 2 .

Максимальная сумма красных чисел равна

(n+ 1)+(n+ 2)+...+ (n+ n)=n ⋅n+ 1+2 +...+ n=

2n2+ n(n+ 1) 3n2+ n = -----2-----= ---2--

Так как $3n(n +1)> 3n2+ n$ , отношение суммы красных чисел к сумме синих меньше трех, значит, если все-таки сумма красных чисел делится на сумму синих, частное равно 1 или 2.

В первом случае мы получаем, что суммы красных чисел и синих чисел должны быть равны, поэтому сумма всех выписанных на доску чисел должна быть четна. При этом половина, а именно $1 0◟0 ◝..◜.0◞ 1 100нулей$ , чисел нечетна. Поэтому сумма всех чисел на самом деле нечетна, и частное не может быть равно 1.

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

2n(2n+-1) 1 +2+ 3+ ...+ 2n = 2

Признак делимости на 3 гласит: натуральное число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Сумма цифр числа $2n= 210◟000.◝◜ну..л0◞ей 2$ равна 4 , а сумма цифр числа $2n+ 1$ равна 5 . Поэтому оба этих числа не делятся на 3 , тогда и сумма всех выписанных чисел на 3 не делится, и второй случай также невозможен.

Ответ: нет

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

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

Дано натуральное число $a> 1.$ Определим функцию

√ - f(n)= n +[a{n 2}].

Докажите, что существует такое натуральное $n,$ что $f(f(n))= f(n)$ , но $f(n)⁄= n.$

Напомним, что $[x]$ — целая часть $x,$ то есть наибольшее целое число, не превосходящее $x,$ а ${x} =x − [x]$ — дробная часть $x.$

Источники: СПБГОР - 2023, 11.5 (см.pdmi.ras.ru)

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

Для решения задачи нам понадобится два классических утверждения из теории чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Дирихле. Для любого иррационального числа $𝜃$ и натурального числа $m$ найдется такое число $k$ , $1≤ k≤ m− 1$ , что $1- {k𝜃}< m$ или $1- {k𝜃}> 1− m$ .

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Кронекера. Для любого иррационального числа $𝜃$ и любых чисел $α$ , $β$ , $0 ≤α <β < 1$ , найдется такое натуральное число $n$ , что ${n𝜃}∈ (α,β)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Применим теорему Дирихле для $√ - 1 𝜃 = 2+ a$ и $m =a$ и найдем такое $1≤ k≤ a− 1$ , что

{ √- 1 } 1 { √- 1 } 1 k( 2+ a) < a или k( 2+ a) > 1− a.

______________________________________________________________________________________________________________________________________________________

В первом случае имеем неравенство $a−ak< {k√2}< a+1a−k$ . Применим теорему Кронекера для

𝜃 =√2, α= k и β = a+-1− {k√2}> k, a a a

получим, что найдется такое $n$ , что $k< {n√2}< a+1− {k√2} a a$ . Для этого $n$ имеем

k< a{n√2}< a(a+-1− {k√2})< a( a+1-− a−-k)= k+ 1. a a a

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

k a− k √- √ - a+1- 1= a + a < {n 2}+{k 2} < a ,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1 a$ , поэтому

√- [a{(n +k) 2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

______________________________________________________________________________________________________________________________________________________

В случае ${k(√2 + 1)}> 1− 1 a a$ выполняется неравенство

a-− k √ - a+1-− k a < {k 2} < a .

Применяя теорему Кронекера для

√ - √ - k+ 1 k+ 1 𝜃 = 2, α= 1− {k 2}< -a-- и β =--a-,

получим, что найдется такое $n$ , что $√- k+1 1< {n 2}< -a-$ . Для этого $n$ имеем

k< a{n√2}< k+ 1.

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

√ - √- 1< {n 2}+{k 2} <1− ka + k+a1-= a+a-1,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1a$ , поэтому

[a{(n +k)√2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

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

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

Даны натуральные числа $a,b$ и $c.$ Ни одно из них не кратно другому. Известно, что число $abc+ 1$ делится на $ab− b+1.$ Докажите, что $c≥ b.$

Источники: ВСОШ, РЭ, 2023, 9.4 (см. olympiads.mccme.ru)

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

Подсказка 1:

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

Подсказка 2:

Рассмотрим разность abc + 1 и ab – b + 1, она равна b(ac – a + 1). Она тоже делится на ab – b + 1. Какие выводы можно сделать?

Подсказка 3:

Ясно, что b не имеет общих делителей с ab – b + 1. Значит, ac – a + 1 делится на ab – b + 1.

Подсказка 4:

Вспомним, что задача решается от противного, то есть предполагается, что b ≥ c + 1. Есть ощущение, что при таком раскладе ab – b + 1 редко когда меньше ac – a + 1.

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

Первое решение. Предположим противное: пусть $b ≥c+ 1.$ Из делимости $abc+1$ на $ab− b+ 1$ следует, что число

b(ac− a +1)= (abc+ 1)− (ab− b+ 1)

кратно $ab− b+1.$ Поскольку числа $b$ и

ab− b+ 1= b(a− 1)+1

взаимно просты, получаем, что $ac− a+ 1$ делится на $ab− b+ 1.$ Ясно, что $ac− a+ 1> 0,$ поэтому либо

ac− a+1 =ab− b+ 1,

либо

ac− a+1 ≥2(ab− b+ 1).

В первом случае получаем

b= a(b− c+ 1)

и, значит, $b$ делится на $a,$ что невозможно по условию. Во втором случае имеем

ac− a ≥2b(a − 1)+ 1> 2b(a− 1) >2c(a − 1),

то есть

ac< 2c− a< 2c.

Это значит, что $a< 2,$ то есть $a= 1;$ но это также невозможно по условию, ибо тогда снова $b$ делится на $a.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Опять же предположим противное. Поскольку $abc+ 1$ делится на $ab− b+ 1,$ то и

bc− c+1 =(abc+1)− c(ab− b+1)

тоже кратно $ab− b+ 1,$ то есть

bc− c+1 =k(ab− b +1)

при некотором натуральном $k.$ Иначе говоря,

0= (bc− c+1)− k(ab− b+ 1)= b(c− ka+ k)− (k+ c− 1). (∗)

Значит, $k+ c− 1$ делится на $b.$

По нашему предположению, $c< b.$ С другой стороны, поскольку $a> 1,$ имеем

bc − c+ 1= c(b− 1)+1< b2 < b(b+ 1)≤b(b(a− 1)+1),

откуда $k< b.$ Значит,

0< k+ c− 1 <2b,

и потому

k+ c− 1= b.

Теперь $(∗)$ переписывается в виде

0= b(c− ka+ k)− b,

то есть

c− ka +k− 1= 0.

Но тогда

ka= k+c − 1= b,

то есть $b$ делится на $a.$ Это невозможно.

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

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

Даны натуральные числа $a,b,c$ такие, что $a >1,$ $b> c> 1,$ а число $abc+ 1$ делится на $ab− b+1.$ Докажите, что $b$ делится на $a.$

Источники: ВСОШ, РЭ, 2023, 10.4 (см. olympiads.mccme.ru)

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

Подсказка 1

Попробуйте из условия делимости вычесть делитель из делимого, чтобы получить новый вид выражения.

Подсказка 2

(abc + 1) − (ab − b + 1) = b(ac − a + 1). Обратите внимание, что в разности появляется множитель b.

Подсказка 3

Заметьте, что число b и число ab − b + 1 взаимно просты. Какой из этого вывод можно сделать?

Подсказка 4

Тогда ac − a + 1 делится на ab − b + 1. Сравните их.

Подсказка 5

Если ac − a + 1 < 2(ab − b + 1), то правда ли, что ac − a + 1 = ab − b + 1?

Подсказка 6

Да, так как ab − b + 1 делит ac − a + 1. Что даёт равенство?

Подсказка 7

А если его преобразовать к виду b(a − 1) = a(b − 1), вспомните про делимость.

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

Из условия следует, что

(abc+ 1)− (ab− b+1)= abc− ab+ b= b(ac− a +1)

делится на $ab− b+1.$ Заметим, что $b$ и

ab− b+ 1= (a − 1)b+1

взаимно просты, отсюда получаем, что $ac− a+ 1$ делится на $ab− b+1.$

Далее замечаем, что

0< ac− a+ 1< 2(ab− b+ 1).

Действительно,

2(ab− b+ 1)= (2a− 2)b+ 2> (2a − 2)c+2 =ac+ (a− 2)c+ 2≥ac+ 2> ac− a +1.

Значит, делимость $ac− a +1$ на $ab− b+ 1$ возможна только в случае равенства

ac− a+1 =ab− b+ 1.

Имеем

a(c− 1)= ac− a =ab− b= (a − 1)b.

Видим, что $(a− 1)b$ делится на $a,$ но так как $a− 1$ и $a$ взаимно просты, отсюда следует, что $b$ делится на $a,$ что и требовалось доказать.

Курсы

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

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

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

Можно ли число $2023$ представить в виде суммы трёх натуральных чисел $a,b,c$ таких, что $a$ делится на $b+c$ и $b+ c$ делится на $b− c+ 1$ ?

Источники: ВСОШ, РЭ, 2023, 11.1 (см. olympiads.mccme.ru)

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

Подсказка 1

Сравните чётность b + c и b − c + 1. Если они разной чётности, то может ли b + c быть нечётным?

Подсказка 2

Нет, не может, ведь тогда нечётные числа не делятся на чётные.

Подсказка 3

Если нужные a, b, c нашлись, то что тогда известно про делители 2023 = a + b + c?

Подсказка 4

Среди них есть b + c. Может ли тогда b + c быть чётным?

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

Предположим, такие три числа найдутся. Поскольку $a$ кратно $b+ c,$ сумма

a+ (b+c)= 2023

также кратна $b+ c,$ из чего следует, что $b+c$ нечётно. Значит,

b− c+1= (b+c)− 2c+1

— чётное число, и нечётное число $b+ c$ не может на него делиться.

Ответ:

нельзя

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

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

Натуральное число $A$ назовём интересным, если существует натуральное число $B$ такое, что:

$A > B$ ;
разность чисел $A$ и $B$ — простое число;
произведение чисел $A$ и $B$ — точный квадрат.

Найдите все интересные числа, большие 200 и меньшие 400.

Источники: Курчатов-2022, 11.3 (см. olimpiadakurchatov.ru)

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

Подсказка 1

Заметим сразу, что если A-B = p - простому числу, то НОД(A, B) либо 1, либо p. Попробуйте понять, что случай с НОДом равным p - невозможен из-за второго условия)

Подсказка 2

Окей, теперь у нас НОД = 1. Но тогда раз произведение этих чисел - точный квадрат, то что можно сказать про сами числа?

Подсказка 3

Что они сами являются квадратами! А теперь давайте вернемся к тому, что разность этих чисел - простое число. Эти же числа являются квадратами. А разность квадратов хорошо раскладывается на произведение) Что можно отсюда выяснить?

Подсказка 4

Если разложить разность квадратов как (a-b)(a+b), то станет понятно, что она может быть равна простому числу только если a-b = 1. Получается, A и B - просто последовательные квадраты) Остался небольшой перебор и все значения найдены!

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

Пусть $A − B = p$ — простое число. По условию $AB = B(B +p)= n2$ для некоторого натурального $n.$ Заметим, что НОД чисел $B$ и $B + p$ делит их разность, равную $p,$ поэтому он равен либо $p,$ либо 1. Разберём два случая.

Предположим, $НОД(B,B +p)= p.$ Тогда $B =ps$ и $B+ p= p(s +1)$ для некоторого натурального $s.$ Тогда $2 n =B (B +p)= ps⋅p(s+ 1),$ т.е. $2 2 n = ps(s+ 1).$ Отсюда следует, что $n$ делится на $p,$ поэтому $(n)2 s(s+1)= p$ — точный квадрат. Но $2 2 s <s(s+1)< (s+1) ,$ т. е. число $s(s+ 1)$ находится между двумя последовательными точными квадратами, поэтому само не может быть точным квадратом. Противоречие.
Предположим, $НОД (B,B +p)= 1.$ Произведение взаимно простых чисел $B$ и $B +p$ является точным квадратом тогда и только тогда, когда сами числа $B$ и $B+ p$ являются точными квадратами. Тогда $B =b2$ и $A =B + p= a2$ для некоторых натуральных $a >b,$ откуда следует, что $p =a2− b2 =$ $(a − b)(a+ b).$ Из того, что произведение натуральных чисел $a − b$ и $a+ b$ равно простому числу $p,$ следует, что $a− b=1$ и $a +b= p.$ Тогда $a= p+21$ и $b= p−21,$ поэтому $( )2 B = p−21$ и $( )2 A = p+12- .$ Поскольку число $p$ является простым, получаем несколько случаев:
- Если $p≤ 23,$ то $A≤ 122 < 200$ — не подходит под условие задачи.
- Если $p= 29,$ то $2 A= 15 = 225$ и $2 B = 14 =196$ — подходит под условие задачи.
- Если $p= 31,$ то $A= 162 = 256$ и $B = 152 =225$ — подходит под условие задачи.
- Если $p= 37,$ то $A= 192 = 361$ и $B = 182 =324$ — подходит под условие задачи.
- Если $p≥ 41,$ то $A≥ 212 > 400$ — не подходит под условие задачи.

Ответ: 225, 256, 361

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

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

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

a+1 +√a5-+2a2+-1 -----a2+-1------

также является натуральным.

Источники: Бельчонок-2022, 11.4 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Мы хотим сделать так, чтобы числитель делился на знаменатель. Попробуем сделать замену а+1=b, так же заменим и корень. Что получится?
----—

Подсказка 2

Получается, что знаменатель можно выразить как частное разности квадратов и разности корня и (a+1). Мы понимаем, что разность квадратов корня и (a+1) должна делиться на (a^2+1). Воспользуемся сравнениями по модулю!

Подсказка 3

Может ли -а-1 быть сравнимо с нулем по модулю a^2+1?

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

Обозначим $a+ 1= b,√a5-+2a2+-1= c$ . В числителе записано

c2-− b2 c+ b= c− b

На $a2+ 1$ должно делиться

c2− b2 = a5+ 2a2+ 1− (a +1)2 = a5+a2− 2a≡a2+1 −a − 1

При $a> 1$ модуль остатка меньше $2 a +1,$ поэтому остаток не может делиться на $2 a + 1$ ни при каком $a> 1.$ Уравнению удовлетворяет единственное значение $a= 1.$

Ответ: 1

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

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

Пусть $p ,p,...,p ,... 1 2 n$ — множество всех простых чисел, расположенных в некотором порядке. Может ли случиться так, что для всех натуральных $i$ число $pipi+1−p2i+2- pi+pi+1$ является натуральным?

Источники: Изумруд-2022, 11.5 (см. izumrud.urfu.ru)

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

Подсказка 1

В задачах на делимость (а это по сути она и есть) часто выгодно рассмотреть какое-то красивое число. А поскольку у нас в задаче часто фигурируют простые, рассмотрим p_m = 2. Что тогда хорошего можно сказать про дробь?

Подсказка 2

Тогда, можно сказать, что число меньше 2, а значит равно 1, а значит, p_(m + 1) = p^2_(m + 2) + 2. А мы как-то использовали m? Может ли m быть сильно большим? Как можно ограничить m зная симметричность p_(i + 1) и p_i в нашем числе?

Подсказка 3

Если m > 1, то можно взять рассмотреть (2p_(m - 1) - p^2_(m + 1))/(2 + p_(m - 1)). Тогда, p_(m - 1) = p^2_(m + 1) + 2 = (p^2_(m + 2) + 2)^2 + 2. По какому модулю теперь удобно посмотреть, при наличии тут множественных квадратов?

Подсказка 4

Конечно, mod 3. Ведь тогда, если p_(m + 2) != 3, то p_(m + 1) кратен 3, а значит равен 3. Но тогда p_(m + 2) = 1. А если же p_(m + 2) = 3, то p_(m - 1) = 123. Значит, пришли к общему противоречию с тем, что m > 1, значит, m = 1. При этом, поняли, что mod 3 в этой задаче, как будто, играет важную роль. Давайте тогда , если уж все таки хотим делимость, рассмотрим такие p_k и p_k + 1, что их сумма кратна 3, и при этом они оба отличны от 3. Что это значит тогда для этих двух чисел? А для дроби?

Подсказка 5

Это значит, что остатки mod 3 у этих
чисел - это 1 и 2. А значит, их квадрат сравним с 1, а произведение с двойкой. Но тогда, числитель не делится на 3, а знаменатель делится. Значит, противоречие. Значит, числа с остатками 1 и 2 не стоят рядом. Ммм… Но если у нас сначала стоит число 2, а потом что-то еще, то это что-то еще - это….

Подсказка 6

Это числа, которые сравнимы с 2 mod 3, а после идет сама тройка. Но тогда, если после тройки стоит число = 2 mod 3, то после него идут только числа = 2 mod 3, а значит пришли к противоречию, так как числа = 1 mod 3 существуют. А значит, после 3 идут только числа = 1 mod 3, но тогда перед 3 стоит конечное число простых = 2 mod 3. А то, что таких бесконечно - остаётся вам в качестве упражнения! :)))

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

Предположим, что такое могло случиться. Тогда существует натуральное $m$ такое, что $p = 2. m$ Значит число

2pm+1 − p2m+2 p2m+2 + 4 --2+pm+1---= 2− 2+pm+1-< 2

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

p2m+2-+4 =1 и pm+1 =p2 +2 2+ pm+1 m+2

Случай $m> 1$ невозможен, так как тогда число

2pm− 1− p2 p2 + 4 --2+pm−m1+1-= 2− m2++1pm-−1 < 2

также является натуральным, откуда

p2m+1-+4 =1 и p =p2 +2= (p2 + 2)2 +2 2+ pm−1 m−1 m+1 m+2

Теперь если $pm+2 = 3,$ то $pm−1 =123,$ что невозможно. Если же $pm+2 ⁄= 3,$ то

p2 ≡ 1 и p =p2 +2 ... 3 m+2 3 m+1 m+2

Значит,

pm+1 = 3, pm+2 = 1

Это невозможно. Следовательно, $m =1.$

Предположим теперь, что нашлись числа $pk$ и $pk+1$ с различными ненулевыми остатками при делении на 3, то есть

.. pk+pk+1. 3

Поскольку число

pkpk+1 − p2 --p-+-p-k+2 k k+1

является натуральным, то

. pkpk+1 − p2k+2.. 3

Но тогда

p2k+2 ≡3 pkpk+1 ≡3 2

Это невозможно, так как квадраты имеют остатки 0 или 1 при делении на 3. В итоге мы доказали, что числа с остатками 1 и 2 при делении на 3 не могут быть соседними.

Поскольку $p1 = 2,$ это означает, что после $p1$ стоят несколько чисел с остатком 2 при делении на 3, затем где-то стоит число 3. Если после тройки стоит число с остатком 2 при делении на 3, то все числа далее будут с таким же остатком и в последовательности простых чисел не будет ни одного числа с остатком 1 при делении на 3 (такие есть, например, число 7).

Следовательно, после тройки стоит число с остатком 1 при делении на 3 и все числа за ним имеют такой же остаток. Но тогда до тройки стоит лишь конечное число простых чисел с остатком 2 при делении на 3.

Предположим, что простых чисел вида $3k+ 2$ конечное число. Обозначим все такие числа через $q1,q2,...,ql.$ Число $3q1q2...ql− 1$ не делится на простые числа $q1,q2,...,ql$ и даёт остаток 2 при делении на 3. Значит среди его простых делителей должно быть число вида $3k+ 2$ — противоречие.

Ответ: нет

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

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

Число $a >0$ таково, что неравенства $2≤ an ≤ 4$ выполняются ровно при $5$ натуральных значениях $n.$ При скольких натуральных значениях $n$ могут выполнятся неравенства $n 4≤a ≤8?$

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

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

Подсказка 1

Пользоваться изначальным неравенством, где n стоит в показателе степени, неудобно. Предположим logₐ 2 = 𝜶 и зададим обычные ограничения на n. Если при заданном а значений n ровно 5, то как можно записать это в виде неравенства?

Подсказка 2

Верно, числа от n до n+4 принадлежат промежутку от 𝜶 до 2𝜶, при этом n-1 уже меньше 𝜶, а n+4 больше 2𝜶. Теперь попробуем преобразовать наше неравенство так, чтобы "зажать" и найти количество значений n, лежащих в промежутке от 2𝜶 до 3𝜶.

Подсказка 3

И не забудьте для каждого количества решений привести примеры!

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

Ясно, что $a> 1.$ Полагая $log 2= α, a$ неравенство $2≤an ≤4$ перепишем в виде $α≤ n≤ 2α,$ а неравенства $4≤ an ≤8$ - в виде $2α ≤n ≤3α.$ Согласно условию, для некоторого натурального числа $m$ выполнены неравенства $m − 1 <α ≤ m< m + 4≤2α <m + 5.$ Из них следует, что

2m − 2< 2α ≤2m < 2m +3< 3α< 2m +5.

Таким образом, неравенствам $2α ≤n ≤3α$ обязательно удовлетворяет четвёрка чисел ${2m;2m +1;2m+ 2;2m + 3}$ и, возможно , одно или оба числа пары ${2m − 1;2m +4}.$

Приведём три соответствующих примера. При $α= 4,6$ имеем $m =5$ и

2m − 1 <2α <3α <2m + 4;

при $α= 5,2$ имеем $m =6$ и выполняются неравенства

2α< 2m − 1 <3α <2m + 4;

наконец, если $α =5,4,$ то $m =6$ и

2α< 2m − 1 <2m + 4< 3α.

Ответ: четыре, пять или шесть

Интенсивы

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

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

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

Найдите все пары $(x;y)$ натуральных чисел, для которых оба числа $x2+8y;y2− 8x$ являются точными квадратами.

Источники: Бельчонок - 2022, 11.5 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Давайте внимательно посмотрим на наши выражения. Нельзя ли сразу угадать какую-то пару чисел, удовлетворяющую условиям задачи. Пусть x равен какому-то натуральному n. Тогда какой должен быть y, чтобы первое выражение было квадратом?

Подсказка 2

Верно, тогда y=n+2. Можно проверить, что условие задачи выполняется. Что же делать теперь? Ведь y может быть больше или меньше x+2. Какую идею тогда здесь можно применить для дальнейшей оценки наших выражений, чтобы перебирать другие варианты было проще?

Подсказка 3

Да, можно попробовать зажать наши числа между квадратами. Если y < x+2, то первое выражение будет находиться между x² и (x+4)², и остаётся только вариант для (x+2)² = x² + 8y из-за чётности. Аналогично рассматривается, если y > x+2. Тут уже второе число зажимается между y² и (y-4)². Осталось только технически это всё реализовать и найти оставшиеся решения. Победа!

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

Легко проверить, что пары вида $(n;n +2)$ , где n – натуральное число, удовлетворяют условию задачи. Пусть $(x;y)$ – любая другая пара, удовлетворяющая условию задачи. Рассмотрим два случая.

1) Пусть сначала $y < x+ 2$ . Тогда $2 2 2 2 x <x + 8y < x + 8(x+ 2)= (x+ 4)$ , откуда $2 2 x + 8y =(x+ k)$ , где $k ∈{1;2;3}$ . Очевидно, возможен лишь случай $k= 2$ (по чётности), и тогда $x= 2y − 1$ .

Осталось выяснить, при каких натуральных $y$ число $2 2 y − 8x= y − 16y+ 8$ будет точным квадратом. Пусть $2 2 y − 16y+ 8= a$ , тогда $√-----2 y =8± 56+ a$ . Число под корнем должно быть точным квадратом: $2 2 56+ a = c$ , т. е. $2 2 c− a = 56$ .

Разложим $56$ на множители и рассмотрим системы. Учитывая, что $c− a$ и $c+ a$ имеют одинаковую чётность, отбросим лишние, останутся системы:

{ c− a = 4 c+ a = 14

{ c− a = 2 c+ a = 28

откуда $c= 9,a= 5$ или $c= 15$ , $a= 13$ .

При $a= 5$ значение $y = 8± √56+25$ и подходит $y = 8+9 =17$ . При $a= 13$ значение $y = 8± √56+-169$ и подойдет $y =8+ 15= 23$ . Поскольку $x= 2y− 1$ , получаем пары $(45;23)$ и $(33;17)$ .

2) Пусть теперь $y > x+ 2$ , т. е. $x <y − 2$ . Здесь $y > 4$ , и мы имеем $(y− 4)2 = y2− 8(y− 2)<y2− 8x< y2$ . Значит, $y2− 8x= (y − k)2$ , где $k ∈{1;2;3}$ . Опять возможен только случай $k= 2$ (по чётности), так что $y = 2x +1$ .

Пусть $x2 +16x+ 8= b2$ , тогда $x= −8± √56+-b2$ . Выше показано, что число под корнем является точным квадратом только при $b= 5$ или $b= 13$ . Тогда $x =1$ или $x =7$ . Получаем пары $(1;3)$ и $(7;15)$ , первая из которых входит в множество $(n;n+ 2)$ .

Ответ:

$(7;15),(33;17),(45;23),(n;n+ 2),n∈ ℕ$

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

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

$d ,...,d 1 9$ — различные целые числа. Докажите, что начиная с некоторого $n$ все такие числа $(n− d)...(n− d) 1 9$ будут иметь простой делитель, больший $20.$

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

Подсказка 1

Попробуйте пойти от противного и посмотрите на НОДы каких-нибудь двух скобочек. Что про них можно сказать?

Подсказка 2

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

Подсказка 3

Простое наблюдение - простых чисел до 20 всего 8, а скобочек 9. Вас это ни на что не наталкивает?

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

Предположим противное, пусть найдётся сколь угодно большое $n,$ при котором выражение имеет только простые делители, меньшие $20.$ При огромных $n$ выражение будет принимать огромные значения, а значит какое-то простое число, меньшее $20,$ будет входить в разложение на простые в огромной степени. Заметим, что всего есть $8$ простых чисел, меньших $20,$ а скобочек $9.$ Поэтому всегда какие-то две скобочки имеют НОД, больший единицы. Понятно, что любые две скобки $n− di$ и $n − dj$ имеют ограниченный НОД, не превосходящий $di− dj$ по абсолютной величине. Из этого следует, что в разложение двух и более скобок не может входить одно и то же простое число в огромных степенях, ведь тогда НОД будет слишком большим. Однако, при огромных $n$ каждая скобка принимает огромное значение, а значит включает в себя один из простых множителей в огромной степени. Как известно, скобочек $9,$ а простых чисел, меньших $20$ — $8,$ значит какие-то две скобки включают одно и то же простое число в огромной степени, противоречие.

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

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

Докажите, что для любого натурального $a >1$ существует простое $p$ такое, что $1 +a+ ...+ ap−1$ — составное.

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

Допустим, $a> 2$ . Тогда у числа $a− 1$ найдётся простой делитель $p$ . При делении на него любая степень числа $a$ даёт остаток 1 , поэтому сумма $p$ таких слагаемых делится на $p$ и больше $p$ . При $a =2$ подойдёт $p= 11$ , поскольку $11 2 − 1= 2047 =23⋅89$ .

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

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

Петя выписал на доску все натуральные числа от 1 до 3300 (каждое по одному разу). Может ли Вася стереть 120 чисел так, чтобы из оставшихся нельзя было выбрать арифметическую прогрессию из 41 числа?

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

Сотрём все числа, кратные 41 , а также числа от 1641 до 1680 — как раз 120 штук. Докажем, что из оставшихся чисел нельзя составить арифметическую прогрессию длины 41.

Действительно, если разность этой прогрессии не делится на 41, то в ней должно присутствовать число, кратное 41 . Пусть разность делится на 41. Если она равна 41, то прогрессия состоит из 41 последовательных чисел с некоторым фиксированным ненулевым остатком при делении на 41. Одно из чисел с таким остатком было стерто в ходе уничтожения отрезка от 1641 до 1680, поэтому все члены прогрессии либо одновременно меньше 1641, либо одновременно больше 1680. Но тогда разность ее крайних членов должна быть меньше 1640 , а она равна $41⋅40= 1640$ .

Может случиться, что разность прогрессии равна 82. Но тогда её первый член не больше 20 , ибо иначе её 41 -ый член больше, чем $20+ 40⋅82 =3300$ . Однако, как легко видеть, в этом случае её 21 -ый член попадёт в выброшенный отрезок от 1641 до 1680.

Наконец, если разность прогрессии делится на 41 и больше 82 , то разность крайних членов будет не меньше $40⋅123> 3300$ , что невозможно.

Ответ: да

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

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

Найдите наибольшее натуральное $n$ такое, что для любых положительных чисел $a,b,c$ , удовлетворяющих неравенству $a2 > bc$ , верно

( 2 )2 (2 )(2 ) a − bc > n b− ac c − ab.

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

Положим $b= c$ . Тогда требуемое неравенство приобретает вид

( 2 2)2 2 2 a − b > nb(b− a),

откуда

2 2 (a+ b) > nb.

Поскольку $a b$ можно сделать сколь угодно близким к 1 , при $n> 4$ найдутся такие $a$ и $b$ , для которых неравенство

( a+ 1)2 >n b

не выполнено.

Покажем, что $n= 4$ уже подходит.

( 2 )( 2 ) (2 2 2 (3 3)) 4 b − ac c − ab = 4 bc + abc− a c+ b ≤

( --) -- ≤ 4 b2c2+ a2bc− 2abc√bc = 4bc(a− √bc)2

Из исходного условия $-- 4bc< (a +√ bc)2$ , откуда

4bc(a− √bc)2 < (a2 − bc)2

Ответ: 4

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

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

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

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

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

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

Если $a =1$ или $b= 1$ , то это ни о чем не говорит, поэтому можно думать, что $a$ и $b$ хотя бы 2. Если у числа $n$ не будет 2 взаимно простых делителей, не равных 1, то оно сразу подходит. Значит, все степени простых подходят.

Пусть у $n$ есть хотя бы 2 простых делителя. Рассмотрим минимальный простой делитель $p$ и пусть $a m = p k$ , где $k$ не делится на $p$ . Тогда $k+ p− 1$ делитель $n$ . Если $k= 1$ , то все отлично. Пусть $k >1$ . Тогда $a НОД(k+ p− 1,kp )=k +p− 1$ . Заметим, что если $НОД(k+ p− 1,k)⁄= 1$ , то $.. n. Н ОД(k+ p− 1,k)= НОД(p− 1,k)> 1$ , но у $n$ нет делителей меньше $p$ , кроме 1?! Значит, $a a α НОД(k+ p− 1,kp )=Н ОД(k+ p− 1,p )=k +p− 1= p 1$ .

Так как $k> 1$ , то $α1 ≥ 2$ и $.. 2 n.p$ . Тогда $2 p − 1+ k$ тоже делитель $n$ . Опять если у $k$ и этого числа есть общий простой делитель $d$ , то либо $.. p− 1.d$ , что невозможно, так как $p$ минимальный простой делитель, либо $.. p+ 1.d$ . В этом случаем либо $p+1 d≤ -2-$ , что невозможно, либо $d= 3$ и $p= 2$ .

Если $p= 2$ , то $k+ 3$ и $k +1$ являются делителем $n$ . С другой стороны, одно из них делится только на первую степень 2, поэтому $. k.. k+12-$ или $. k.. k+32-$ . В первом случае $. 2..k +1$ и $k= 1$ . Во втором случае $. 6 ..k+3,$ и значит, $k= 3$ . Значит, $. n..12$ . Вариант $n =12$ нам подходит. Если $n ⁄= 12$ , то $. n ..24,$ и значит, $. n..8+ 3− 1= 10$ ?!

Значит, $k$ и $p2 − 1+ k$ взаимно просты. Тогда $p2− 1+k = pβ =p2− p+ pα1$ . Правая часть хотя бы $p2$ , но не делится на $p2$ , но при этом равна степени $p$ ?!

Ответ: 12 и все степени простых

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

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

По кругу расставлены числа от 1 до 23. Докажите, что сумма некоторых трех подряд стоящих чисел не меньше 36.

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

Пусть сумма любых трех подряд стоящих чисел хотя бы 37. Тогда рассмотрим все возможные тройки подряд стоящих чисел и возьмём их сумму. Всего троек будет 23, и итоговая сумма будет $≥23⋅37$ . С другой стороны, в этой сумме каждое число будет встречаться 3 раза. Значит, эта сумма равна $23⋅24 2 ⋅3= 23⋅36.$ Но это меньше $23⋅37$ . Противоречие.

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

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

Дано натуральное число $n,$ свободное от квадратов. Пусть $D$ — множество всех натуральных делителей $n.$ Подмножества $A,$ $B$ множества $D$ удовлетворяют условию, что для любых $a ∈A$ и $b∈B$ справедливо, что $a$ не делится на $b$ и $b$ не делится на $a.$ Докажите, что $∘--- ∘--- ∘ --- |A|+ |B|≤ |D|.$

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

Запишем неравенство в таком виде:

∘--- ∘ --- ∘ --- |B|≤ |D |− |A |.

Ясно, что мощность $D$ не меньше мощности $A.$ Поэтому возведение в квадрат будет равносильным переходом:

∘----- B ≤D + A− 2 |D||A|.

Давайте определим множества элементов, которые запрещены в множестве $B :$

X = d∈D :∃a∈ A:a | d,

Y =d ∈D :∃a∈ A:d | a.

Заметим, что $|B |+ |X∪ Y|≤ |D|.$ Действительно, потому что множества $B$ и $X∪ Y$ не пересекаются. Запишем $X ∪Y$ по формуле включения-исключения:

|B |+|X|+ |Y|− |X ∩Y |≤|D|.

Давайте заметим, что $A$ является подмножеством $X ∩ Y.$ Тогда давайте будем доказывать более сильное неравенства, дополним $A$ элементами до $X∩ Y.$ Тогда неравенство примет вид:

|B|+ |X |+|Y|− |A|≤ |D|.

Запишем его так:

|B |≤|D|+|A|− |X|− |Y |

Теперь становится ясно, что достаточно доказать неравенство $∘ ----- |X |+ |Y |≥2 |D||A |.$ Оно очень похоже на неравенство о средних, поэтому возникает желание доказать неравенство $|X||Y|≥ |D ||A |.$

Докажем его индукцией по количеству простых делителей $n.$ База при $n = 1$ (нет простых делителей) очевидна. Теперь докажем переход. Пусть $n =p⋅m,$ где $p$ — простое. Тогда для $m$ неравенство является верным и осталось понять, как его использовать.

Как известно, делители числа, свободного от квадратов, можно разбить на пары $(d,pd).$ Отсюда следует, что $|D(n)|= 2|D (m )|.$ Пусть $A = A1∪A2,$ где $A1 = a∈A :(a,p)= 1,$ а я $A2$ дополняет его до $A.$ Аналогично определим $X1,X2$ для $X$ и $Y1,Y2$ для $Y.$ Определим множества $X$ и $Y$ для числа $m.$ В силу определения этих множеств $X (m )$ включает $X1,Y1$ включает $Y (m ).$ Также $|X2|≥|X(m)|,|Y2|≥ |Y (m )|$ (если поделить все элементы $X2$ и $Y2$ на $p,$ то будет такое же включение). Проделаем следующую цепочку равенств и неравенств с помощью предположения индукции:

|A ||D (n)|= (|A1|+|A2|)⋅2|D (M )|= 2|A1||Dm |+2|A2||Dm|≤ 2|X1||Y1|+2|X2 ||Y2|.

Осталось показать, что $2|X1||Y1|+ 2|X2||Y2|≤|X||Y |= (|X1|+ |X2|)(|Y1|+ |Y2|).$ Если привести подобные, получится неравенство $|X ||Y|+ |X ||Y |≤ |X ||Y |+|X ||Y|, 1 1 2 2 1 2 2 2$ которое равносильно неравенству $(|X |− |X |)(|Y |− |Y |)≤0. 1 2 1 2$ В силу определения множеств если $a ∈X1$ , то $pa ∈X2$ и если $y ∈ Y2,$ то $y p ∈Y1.$ То есть первая скобка неположительная, а вторая неотрицательная, это даёт требуемое.

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

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

Для натурального числа $N$ рассмотрим все различные точные квадраты, которые можно получить из $N$ вычёркиванием одной цифры в его десятичной записи. Докажите, что количество этих квадратов не превосходит некоторой величины, не зависящей от $N.$

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

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

Пусть число $N$ состоит из $k+ 1$ цифры. Считаем далее, что $k> 100:$ меньшие числа не влияют на искомую ограниченность.

Для $i= 1,...,k$ обозначим через $ni$ число, получающееся удалением из $N$ $i$ -ой с конца цифры. Обозначим через $f(N )$ количество точных квадратов в множестве ${n1,...,nk}.$ Наша цель — доказать, что $f(N)$ ограничено сверху.

Пусть $t N = 10N1,$ где $N1$ не кратно 10. Если $t$ нечётно, то число $ni$ может быть точным квадратом только при $i≤ t+ 1,$ так что в этом случае $f(N)≤ 2.$ Если $t$ чётно, то заключительные $t$ нулей не влияют на дело, поэтому $f(N )= f(N1).$ Поэтому далее считаем, что $N$ не кратно 10.

Выделим множество $A ⊂ {1,...,k}$ из $f(N)$ номеров $i,$ для которых $2 ni = m i$ — точный квадрат, причём натуральные числа $mi, i∈ A,$ попарно различимы.

Отметим следующее:

1) $ni ≥10k−1,$ следовательно $mi ≥10(k−1)∕2$ при всех $i∈ A;$

2) $|ni− nj|< 10max(i,j);$

3) $N − ni$ кратно $10i− 1.$

Из свойства 1) следует, что для различных номеров $i⁄= j$ из $A$ имеет место оценка

|ni− nj|= |m2i − m2j|≥ mi+ mj ≥ 2⋅10(k−1)∕2.

Сопоставляя это со свойством 2), получаем, что $max(i,j) >(k− 1)∕2.$ Таким образом, все элементы $A,$ кроме, быть может, одного, больше, чем $(k− 1)∕2.$ Обозначим $A1 :=A ∖{min(A )}$ (удалили из $A$ наименьший элемент), тогда $|A1|= f(N)− 1$ и $min(A1)≥ k2.$

Пусть $j >i$ — два элемента множества $A1.$ Тогда по свойствам 1), 2) имеем

10j > |ni− nj|=|m2i − m2j|≥ 2⋅10(k−1)∕2⋅|mi − mj|.

С другой стороны, по свойству 3) число

ni− nj = (mi − mj )(mi+ mj)

кратно $10i−1.$

Положим $r= ⌈(i− 1)∕2⌉$ (где $⌈⋅⌉$ обозначает верхнюю целую часть). Хотя бы одно из чисел $mi − mj,mi +mj$ кратно $2r,$ и хотя бы одно кратно $5r.$ Кроме того, если $N$ нечётно, то нечётны числа $m ,m , i j$ поэтому одно из чисел $m − m ,m +m i j i j$ не кратно $4− a$ другое, соответственно, кратно $i−2 2 .$ Иначе $N$ не кратно 5, и аналогичным образом получаем, что одно из чисел $mi − mj,$ $mi+ mj$ кратно $i−1 5 .$

Рассмотрим пятиэлементное подмножество $ˆ A ⊂ A1,$ наименьший элемент $ˆ A$ обозначим $u,$ а наибольший $v.$ Обозначим $r= ⌈(u− 1)∕2⌉.$ Если $N$ нечётно, положим $α = u− 2,$ $β = r;$ иначе положим $α= r,β = u− 1.$ Из доказанного следует, что элементы множества $ˆ {ms :s∈ A}$ дают не более двух различных остатков по модулю $α 2$ и не более двух различных остатков по модулю $β 5.$ Значит, в $ˆA$ найдутся два различных элемента $i< j$ такие, что $mj − mi$ кратно $α β 2 5 .$ Тогда по (1) получаем

10v ≥ 10j ≥ 2⋅10(k−1)∕22α5β ≥ 10(k−1)∕2+(u−1)∕22(u−1)∕2 > 10u−12u∕2,

откуда следует что $v u > 1,01.$ Таким образом, если разбить отрезок $[k∕2,k]$ на группы подряд идущих чисел, в каждой из которых отношение любых двух элементов меньше чем $1,01$ (количество таких групп меньше, например, миллиона), то любая из этих групп содержит не более 4 элементов множества $A1.$ Отсюда вытекает ограниченность числа $|A1|= f(N )− 1.$