Тема ПитерГор (Санкт-Петербургская олимпиада)

Теория чисел на Питергоре

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

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

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

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

Подтемы раздела питергор (санкт-петербургская олимпиада)

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

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

Задача 1#82679

Дано 101-значное число $a$ и произвольное натуральное число $b$ . Докажите, что найдется такое не более чем 102-значное число натуральное число $c$ , что любое число вида $caaa...ab$ - составное.

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

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

Из признака делимости на $10101+1$ (необходимо рассмотреть знакочередующуюся сумму блоков по 101 цифре с конца) следует, что числа в которых количество $a$ в записи отличается на четное число имеют одинаковые остатки при делении на $101 10 +1$
Заметим, что $101 10 +1 ≡11 0$ , а еще по лемме об уточнении показателя $101 10 +1$ не делится на $2 11$ , поэтому у $101 10 + 1$ есть простой делитель $p$ отличный от 11
Достаточно сделать так, чтобы $cb$ и $cab$ делились на 11 и на $p$ соответственно. Такое $c$ существует и не превосходит $101 11× p≤ 10 + 1$ по китайской теореме об остатках.

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

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

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

Задача 2#89867

Несократимые дроби $a b$ и $c d$ записали в виде чисто периодических десятичных дробей. Оказалось, что любая конечная последовательность подряд стоящих цифр, встречающаяся в первой десятичной дроби после запятой, встречается и во второй (тоже подряд и тоже после запятой). Докажите, что $b= d.$

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

Давайте для удобства считать, что $0≤ a< b$ и $0 ≤c< d$ , иначе вычтем целую часть дробей, не изменив дробную часть, получив $a$ и $c$ в нужном диапазоне (условие на несократимость дробей останется). Скажем, что

a c b = 0,(T1) d = 0,(T2),

(1)

$m1$ — количество цифр в записи $T1$ , $m2$ – количество цифр в записи $T2$ ( $T1$ и $T2$ — периоды наших дробей).

Рассмотрим последовательно написанный $T1$ $m2$ раз (такая последовательность в первой дроби есть), по условию она же есть, и во второй, причём в ней $m1m2$ цифр, значит, во второй дроби эта последовательность является сдвигом $T2$ , записанным $m1$ раз. Тогда скажем, что во второй дроби построенная последовательность перед первым $T2$ имеет кусок $k1$ , оставшийся кусок из $T1$ назовём $k2$ , то есть $---- T1 = k1k2$ . Тогда эта же последовательность во второй дроби выглядит как $k1$ , $T2$ , написанный $m1− 1$ раз, и остаток $k$ , причём $--- T2 =kk1$ . Обозначим рассматриваемую последовательность за $T$ ( $--------- -------- k1k2...k1k2 =T = k1k...k1k$ ), тогда:

a =0,(k1k2)=0,(T) b

(2)

c --- d =0,(kk1)= 0,k(T)

(3)

Скажем, $m$ — количество цифр в $T$ , $n$ —- количество цифр в $k$ . Тогда верно следующее:

a⋅10m =T,(T ) b

(4)

c ⋅10n = k,(T) d

(5)

c --- d ⋅10n+m = kT,(T)

(6)

Вычитая (2) из (4) и (5) из (6) соответственно, получаем:

a ⋅(10m − 1)= T b

(7)

c⋅10n(10m − 1)= T +k(10m − 1) d

(8)

Подставим $T$ из (7) равенства в (8), получим:

c⋅10n(10m − 1)= a ⋅(10m− 1)+k(10m− 1) d b

c n a n d ⋅10 = b +k =⇒ bc⋅10 = ad+ bdk

. . ad..b и bc⋅10n..d

Вспомним, что пары чисел $(a,b)$ и $(c,d)$ взаимно просты. Значит, $d..b .$ и $b⋅10n ..d .$ .

Докажем, что $n 10$ и $d$ взаимно просты. Из (1):

c ⋅(10m2 − 1)=T2 =⇒ c⋅(10m2 − 1)= T2d =⇒ 10m2 − 1...d, d

ибо $c$ и $d$ взаимно просты.

Если НОД $(10n,d)...p$ — простое, то $10m2 − 1$ уж точно на $p$ не делится, но тогда и на $d$ делиться не может, противоречие, тогда рассматриваемый НОД равен 1, что эквивалентно искомой взаимной простоте, откуда следует, что $b⋅10n ...d ⇐ ⇒ b ...d$ . Тогда у нас $d...b$ и $b...d =⇒ b=d$ , что и требовалось.

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

Задача 3#89870

Дано натуральное число $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

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

Задача 4#70483

Будем говорить, что набор чисел $a ,...,a 1 m$ сильнее набора чисел $b,...,b , 1 n$ если среди всех неравенств вида $a > b i j$ количество верных неравенств не менее чем в $2$ раза превосходит количество неверных. Докажите, что не существует трех наборов $A,B,C,$ таких, что $A$ сильнее $B,$ $B$ сильнее $C,$ $C$ сильнее $A.$

Источники: СпбОШ - 2022, задача 11.4(см. www.pdmi.ras.ru)

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

Подсказка 1

Нам дали факт о том, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных» и просят доказать, что какой-то факт не выполнен, скорее всего мы получим противоречие с тем, что какая-то величина будет одновременно больше и меньше какого-то числа или мы сможем показать, что она не меньше и не больше некоторой числа, а значит равна ему и такой случай уже намного проще разобрать.

Подсказка 2

Давайте теперь зафиксируем произвольную тройку (A_i, B_j, C_t) и распишем для неё условие, что A сильнее B, B сильнее C, C сильнее A. А сколько вообще может быть верных неравенств при таком условии? Может попробовать оценить сверху и снизу количество верных неравенств?

Подсказка 3

Действительно, количество верных неравенств не больше чем 2, мы показали это для произвольной тройки, а сколько всего троек? Теперь попробуем понять, как ограничить эту величину снизу. Мы не пользовались тем, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных». Как раз «не менее» намекает нам о том, что мы сможем оценить снизу.

Подсказка 4

Можно посмотреть на наборы A, B и поотвечать на вопросы. А сколько можно записать неравенств вида a_i > b_j? А сколько из них должны быть верными? А мы пользовались какими-либо особенностями множеств A и B или это можно сказать для любой пары множеств?

Подсказка 5

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

Подсказка 6

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

Подсказка 7

Верно, для наибольшего из всех чисел или для наименьшего, здесь мы пользовались принципом крайнего, который часто может встречаться в задачках, где что-то сравнивается. Вернёмся к условию, что A сильнее B, B сильнее C, C сильнее A, оно ведь тоже участвовало в оценке, тогда что должно быть верно, чтобы она достигалась? Как нам объединить это с прошлым фактом?

Подсказка 8

Давайте рассмотрим тройку с минимальный (для максимального тоже верно) числом из всех наборов, тогда одно из неравенств очевидно выполнено, а другое - нет. Что можно сказать про оставшееся, а сколько таких неравенств, где в тройке участвует минимальное (максимальное) число? А сколько должно должно быть верных неравенств в паре наборов?

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

Предположим противное. Пусть наборы

A = (a1,...,al),B = (b1,...,bm ),C =(c1,...,cn)

таковы, что $A$ сильнее $B,B$ сильнее $C,C$ сильнее $A.$ Можно считать, что число $a1$ наибольшее среди всех чисел этих трёх наборов. Для каждой тройки индексов $i,j,k(1 ≤i≤ l,1≤ m,1≤ k≤ n)$ посчитаем, сколько верных увтерждений имеется среди неравенств $a > b,b >c ,c >a , i j j k k i$ просуммируем эти числа по всем $i,j,k$ и обозначим полученную сумму через $S.$ Тогда

S ≤ 2lmn, (∗)

поскольку всего имеется $lmn$ троек и в каждой тройке не больше двух верных неравенств. Далее заметим, что каждое неравенство $ai > bj$ присутствует в $n$ таких тройках, поэтому в сумме $S$ оно учтено $n$ раз. По предположению среди неравенств $ai > bj$ не меньше $2lm 3$ верных, поэтому вклад всех неравенств вида $ai >bj$ в сумму $S$ не меньше чем $2lmn. 3$ Аналогично вклад всех неравенств вида $b > c j k$ в сумму $S$ и вклад всех неравенств вида $c > a k i$ в сумму $S$ также не меньше чем $2lmn. 3$ Следовательно, суммарное количество верных неравенств не меньше чем $3⋅ 2lmn ≥S. 3$

Сопоставляя это с неравенством $(∗),$ заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности $2 3mn$ верных неравенств вида $bj > ck,$ а в каждой тройке $ai > bj,bj >ck,ck >ai$ ровно два верных неравенства.

Рассмотрим теперь тройку чисел $a1,bj,ck.$ Среди неравенств $a1 >bj,bj > ck,ck >a1$ должно быть ровно два верных. Поскольку $a1$ — наибольшее число неравенство $ck > a1$ неверно, т.е. выолняется неравенство $bj > ck.$ Значит, все неравенства вида $bj > ck$ верные и всего их $mn$ штук. Но это противоречит тому, что их $2 3mn.$ Стало быть, наше предположение неверно.

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

Задача 5#70485

Найдите все пары ненулевых (не обязательно положительных) рациональных чисел $x,y,$ обладающие следующим свойством: любое положительное рациональное число можно представить в виде ${rx}∕{ry}$ с положительным рациональным $r.$

Источники: СпбОШ - 2022, задача 11.6(см. www.pdmi.ras.ru)

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

Подсказка 1

Давайте для начала причешем задачу. Если r - рациональное и положительное, то x,y - просто целые, так как можно построить явную биекцию между решениями при просто рациональных x,y и целых. Также, можно заметить, что если мы уберем целую часть числа r , то отношение из условия останется таким же, а значит, можно сказать, что 0 < r < 1 . А тогда можно сказать, что {(1 - r)x} = {-rx}, аналогично с y. Значит, можно считать, что y - натуральное, а х - целое. Значит, у нас, существенно, два случая - когда наша дробь - положительное число, и когда отрицательное. Попробуйте теперь найти такую дробь, которая не может быть представлена в таком виде как мы описали, и с теми условиями, которые мы доказали.

Подсказка 2

Сейчас будет приведено совсем не строгое, но тем не менее, наталкивающее на мысли, объяснение, почему нужно брать конкретную дробь, при разборе случая , когда дробь - положительное число. Давайте распишем {rx} как rx - [rx], {ry} как ry - [ry]. Тогда, для некоторого n/k = {rx}/{ry}, выполнено, что n*{ry} = k*{rx}. Значит, nry - n*[ry] = krx + k*[rx]. Что мы из этого можем получить? Если мы хотим прийти к противоречию, то можно попытаться взять какие - то k и n, такие, чтобы что-то в этом равенстве стало плохо. Сейчас целое число слева равно целому справа, а что можно подставить, чтобы слева, после преобразований, стало нецелое, а справа целое?

Подсказка 3

Возьмем n = x + 1, k = y. Тогда, во первых, сократятся rxy и rxy слева и справа, а в итого, останется уравнение {ry} = x * [ry] - y * [rx]. А значит, слева будет что - то между 0 и 1, а справа что-то целое. Пришли к противоречию. То есть, случай, когда дробь больше нуля разобран. Осталось подумать над случаем, когда наша дробь отрицательна. Можно попытаться найти контрпример, однако сразу непонятно как его строить, рассуждения из прошлого пункта непримиримы. Тогда скажем, что наша дробь равна некоторому a/b, где а - отрицательное и попытаемся доказать, что для любых а и b такое r найдется. И кажется, что в такой непонятной конструкции, как дробная часть, могут спасти только оценки значений. Попробуйте их применить(само собой, после избавления от знаменателей).

Подсказка 4

После избавления от знаменателей, у нас получается выражение brx - b*[rx] = ary - a[ry]. А значит, r - одно из решений уравнения r(bx - ay) = n, для некоторого целого n. При этом, мы можем сказать, что (без ограничения общности) х < 0, а значит, по нашим рассуждениям из первой подсказки, {rx} = 1 - {r|x|}. Подставьте это значение в наше уравнение и попробуйте подумать над максимальным и минимальным значением нецелое части.

Подсказка 5

Получим, что b = a{ry} + b{r|x|}. При r бесконечно близком к нулю, получается, что правая часть будет стремиться к нулю, что меньше b. При r бесконечно близким к 1, но меньшим ее, правая часть будет стремиться к a+b, что больше b. Значит, найдется промежуточное значение, при котором в нашем выражении будет достигаться равенство. А значит, для любой пары а и b из второго случая, мы привели пример. Значит, только для xy<0 выполнено требуемое.

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

Первое решение.

Разобьём плоскость на единичные квадраты линиями целочисленной решетки. Проведем прямую $l$ через начало координат $O$ и точку $(x,y).$ Поскольку $x,y ∈ Q.$ она имеет рациональный угловой коэффициент и проходит через какой-то узел решетки. Точка вида $(rx,ry)$ — это любая рациональная точка этой прямой. Проведем прямую через такую точку и левый нижний угол той клетки, в которую попала эта точка. Угловой коэффициент этой прямой равен как раз ${rx}∕{ry}.$

$PIC$

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

Предположим, что $x$ и $y$ одного знака. Тогда полученные отрезки имеют положительный угловой коэффициент. Один из них выходит из левого нижнего узла квадрата. Ясно, что из этого узла можно провести луч с положительным рациональным коэффициентом $λ,$ который пересечет верхнюю или нижнюю сторону квадрата, не встретив по дороге точек ни одного из наших отрезков. Это число $λ$ нельзя представить в нужном виде.

Пусть, наоборот, числа $x$ и $y$ разного знака. Тогда наши отрезки имеют отрицательный угловой коэффициент. Один из них выходит из левого верхнего узла квадрата. Несложно понять, что один из этих отрезков соединяет точку на левой стороне квадрата с точкой на его нижней стороне. На рациональных точках этого отрезка реализуются все возможные положительные рациональные угловые коэффициенты!

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Так как в качестве $r$ можно взять любое положительное рациональное число, можно считать, что числа $x$ и $y$ целые. В этом случае замена числа $r$ на его дробную часть не изменит отношения ${rx} {ry},$ значит, можно дополнительно считать, что $0< r< 1.$ Наконец, замена r на $1− r$ соответствует смене знаков чисел $x$ и $y,$ поскольку

{(1 − r)x} {−rx} {(1-− r)y}-= {−ry}.

Таким образом, достаточно рассмотреть лишь случай, когда $y$ — натуральное число.
Пусть $x$ также является натуральным числом. Покажем, что уравнение

{rx}-= x+1- {ry} y

не имеет решений относительно $r.$ Домножив на знаменатели и выразив дробную часть через целую, получим уравнение

y⋅rx− y⋅[rx]= x⋅ry− x ⋅[ry]+ {ry},

или, что то же самое,

{ry} =x ⋅[ry]− y⋅[rx].

Но это уравнение не может иметь решений, поскольку левая часть положительна и меньше $1,$ а правая часть целая. Следовательно, если числа $x$ и $y$ одного знака, то требуемое $r$ не найдётся.
Пусть $x$ является отрицательным целым числом. Достаточно показать, что уравнение

{rx} a {ry} = b (∗)

для любых натуральных чисел $a$ и $b$ имеет вещественное решение $r.$ Тогда

b⋅rx− b⋅[rx]=a ⋅ry− a⋅[ry]

и, значит, $r$ является решением линейного уравнения

(bx− ay)r= n

для некоторого целого $n$ и, в частности, должно быть рациональным числом. Домножив уравнение $(∗)$ на знаменатели и воспользовавшись тем, что ${rx} =1 − {r|x|},$ получим уравнение

b= a{ry} +b{r|x|}.

При $r= 0$ правая часть равна нулю и поэтому меньше левой. А при $r,$ близких к $1,$ обе дробные части также будут близки к $1,$ поэтому правая часть будет близка к $a+ b$ и, в частности, будет больше левой. Следовательно, при некотором промежуточном $r$ правая часть будет равна левой. Поэтому если числа $x$ и $y$ разных знаков, то требуемое $r$ обязательно найдётся.

Ответ:

подходят все пары, в которых $xy <0$

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

Задача 6#69819

В ряд выписано $2021$ простое натуральное число. Каждое, кроме крайних, отличается от одного из своих соседей на $12,$ а от другого — на $6.$ Докажите, что среди этих чисел есть равные.

Источники: СпбОШ - 2021, задача 10.2 (см. www.pdmi.ras.ru)

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

Подсказка 1

Если мы хотим сказать, что все числа различные, то такая последовательность достаточно быстро, линейно растет. И при этом, почти все идут подряд, если смотреть на целую часть при делении на 6. То есть, число может «прыгать» через 1(после того как нацело поделили всю нашу последовательность на 6), но не больше чем на 1. Вот так «на пальцах», не строго, мы поняли, что было бы очень удачно, если бы мы смогли найти два каких-то соседних числа, которые отличаются на хотя бы 18. А это можно сделать, если мы(допустим) сможем разделить нашу последовательность на что-то большее ,чем некоторое число , и на что-то меньшее , чем некоторое число. И наименьшее и наибольшее из соответствующих групп отличались хотя бы на 18. То есть, иными словами, мы хотим сказать, что какие - то два подряд идущих числа, отличающиеся на 6, не могут быть в последовательности. Попробуйте придумать, как к такой конструкции прийти.

Подсказка 2

Одна из таких конструкций - остатки. По китайской теореме об остатках найдется такое k, что p + 6k делится на 5,а p + 6(k+1) на 7, при этом p - наименьшее простое число, большее 7(чтобы существовало число перед ним, которое входит в последовательность), входящее в последовательность. При этом 0 < k <= 5*7(по КТО найдется такое k). Теперь подумайте, откуда здесь возникает противоречие.

Подсказка 3

А возникает оно из - за того, что оба этих числа не простые, при этом они идут через одно. То есть, как раз мы получили конструкцию, в которой все разделилось на две кучи, в одной из которых числа которые хотя бы p+6(k+2), а в другой p+6(k-1). То есть разность хотя бы 18. Что теперь это значит? Какие теперь числа точно не могут быть в последовательности? А сколько теперь может быть чисел максимум в последовательности?

Подсказка 4

Верно, числа больше или равные p + 6(k+2), поскольку множество «меньших» непустое. Значит, чисел в наборе останется не больше чем 36(самое p и всевозможные 0 < k <= 5*7) и 2,3,5,7 - то есть не более 40 чисел. Но у нас 2021 число. Противоречие.

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

Способ 1

Предположим, что все числа в ряду различны. Выберем в нашем ряду число $p,$ у которого с каждой стороны не меньше пяти соседей, причём среди них нет числа $5.$ Такое $p$ найдётся, так как число $2021$ достаточно большое, а число $5$ в нашем ряду встречается не более одного раза. Если $p≡ ±1 (mod 5),$ рассмотрим соседа числа $p,$ отличающегося от него на $6.$ А если $p≡ ±2 (mod 5),$ рассмотрим его соседа, отличающегося на $12.$ Не умаляя общности, будем считать, что этот сосед находится справа от $p.$ На приведённой ниже схеме выберем среди первых четырёх чисел то, которое равно остатку числа $p$ при делении на $5.$ Число над стрелкой показывает, на сколько должен отличаться его правый сосед, а число после стрелки — какой остаток при делении на $5$ этот сосед будет иметь. Все числа над стрелками однозначно определяются условиями, что разности $± 6$ и $±12$ чередуются и в ряду нет остатка $0 :$

+6 +12 − 6 −12 +6 +12 −6 1−−→ 2 −−−→ 4−−→ 3 −−−→ 1−−→ 2 −−−→ 4−−→ 3

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

Способ 2

Пусть $p$ — наименьшее простое число в этом ряду большее $7.$ По китайской теореме об остатках существует такое число $k$ ( $0< k≤ 35$ ), что

p+ 6k≡ 0 (mod 5)

p+ 6(k+ 1)≡ 0 (mod 7).

Тогда числа $p+ 6k$ и $p+ 6(k+ 1)$ не простые, поэтому в нашем ряду они не встречаются. Но тогда в нашем ряду не может быть и чисел, больших $p+ 6(k+1),$ так как иначе нашлось бы два соседних числа, одно из которых не превосходит $p+ 6(k− 1),$ а второе не меньше числа $p+ 6(k +2),$ что невозможно. Следовательно, в ряду может встретиться не более $40$ различных простых чисел: $2,3,5,7$ и $p,p+ 6,...,p+ 6⋅35.$ Но в ряду $2021$ число, значит, среди чисел есть равные.

Способ 3

Пусть $p$ — наименьшее просто число в этом ряду. Тогда все числа в ряду не превосходят $p +18⋅1010,$ так как если идти по ряду от $p$ до какого-то числа, то за каждые два шага число будет увеличиваться не более чем на $18.$ Докажем, что среди чисел

p,p+6,p+ 12,...,p+ 18⋅1010(∗)

количество простых меньше $2021.$ Из этого будет следовать, что в ряду обязательно найдутся равные числа. Пусть $dn$ — количество чисел в этом ряду, кратных $n.$ Подсчитаем количество чисел в ряду (*), кратных $5,7$ и $11.$ По формуле включений-исключений это количество равно

N =d5+ d7+ d11− d35 − d55− d77+ d385.

Если $(6,n)= 1,$ то на $n$ делится каждое $n$ -ое число в ряду (*) и $[3031] dn = n$ или $[3031] dn = n + 1.$ Следовательно,

[ ] [ ] [ ] [ ] [ ] [ ] [ ] N ≥ 3031- + 3031 + 3031-− 3031- − 1− 3031 − 1 − 3031 − 1+ 3031-= 606+433+ 275 − 87− 56− 40+ 7= 1129. 5 7 11 35 55 77 385

Итого, в ряду (*) не менее $1129$ чисел, кратных $5,7$ и $11.$ Из этих $1129$ чисел не более трёх являются простыми — это сами числа $5,7$ и $11,$ если они там есть. Поэтому в ряду (*) не более $3031− 1129+ 3= 1905$ простых.

Курсы

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

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

Задача 7#71954

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

Источники: СпбОШ - 2021, задача 11.1(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Сумма ряда равна p(p+1)/2. Значит, либо кол-во блоков, либо сумма чисел в блоке делится на p. Что сразу можно сказать про первый случай?

Подсказка 3

Верно! Он просто невозможен. Ведь тогда у нас p блоков, в каждом только по одному числу. Значит, суммы везде разные. Тогда верен второй вариант. Попробуйте рассмотреть первый блок и понять, когда возможно то, чтобы сумма чисел в нём делилась на p.

Подсказка 4

Если в первом блоке k чисел, то сумма чисел в блоке равна k(k+1)/2. Значит, k+1 = p. Тогда у нас второй блок - это только число p. Попробуйте записать равенство сумм первого и второго блоков.

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

Очевидно, $p =2$ не подходит, поэтому $p$ нечётно. Поскольку сумма всех чисел равна $p⋅ p+1, 2$ она делится на $p.$ Значит, либо количество блоков делится на $p,$ либо сумма чисел в каждом блоке делится на $p.$ Первый случай невозможен, поскольку тогда блоков ровно $p$ и они все состоят из одиночных чисел, а значит, во всех блоках разные суммы. Следовательно, сумма чисел в каждом блоке делится на $p.$ Рассмотрим первый блок, пусть последнее число в нём равно $k <p,$ тогда сумма чисел в этом блоке равна $k(k+1)- 2$ и она делится на $p.$ Это возможно, только если $k+ 1= p.$ Тогда второй блок состоит лишь из числа $p$ и должно выполняться равенство $(p−1)p- 2 =p,$ поэтому $p =3.$ Это возможно: $1+2 =3.$

Ответ:

$p =3$

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

Задача 8#71958

Дано натуральное число $n.$ Для каждого простого числа $p$ из промежутка $[n,n2]$ посчитали число $1, p$ и все полученные числа сложили. Докажите, их сумма меньше $2.$

Источники: СпбОШ - 2021, задача 11.5(см. www.pdmi.ras.ru)

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

Подсказка 1

Давайте попробуем посчитать количество чисел от n до n², которые делятся на простое p(тоже из этого отрезка). Как можно оценить это число?

Подсказка 2

Мы знаем, что таких чисел ровно [n²/p]. Но с целой частью работать не очень удобно, поэтому снизу можно поджать выражением n²/p - 1. А что можно сказать про разные p? Существуют ли числа из [n, n²], которые делятся на p₁ и p₂, если p₁ и p₂ из отрезка [n, n²]?

Подсказка 3

Все такие числа уникальны(то есть, для каждого p свой набор чисел, который делятся на p и пересечений по этим наборам нет). В таком случае, как можно оценить количество чисел из [n, n²], которые делятся на какое-то простое из [n, n²]?

Подсказка 4

Количество всех чисел — это Σ(n²/p - 1) по всем простым из нашего отрезка. А как её можно оценить сверху(помните, что мы смотрим на Количество чисел) и снизу?

Подсказка 5

Очевидно, что n² больше чем наша сумма, так как на рассматриваемом отрезке чисел: n² - n + 1. Оценку снизу получить сложнее, давайте посмотрим на Σ(n²/p), что из неё надо вычесть, чтобы получить сумму меньше, чем наша?

Подсказка 6

Если из Σ(n²/p) вычесть n², то мы получим сумму меньше чем наша, ведь количество слагаемых в сумме не больше n². Какие оценки мы получили и как из них получить оценку на Σ(1/p)?

Подсказка 7

Финальные оценки — это n² > Σ(n²/p - 1) > Σ(n²/p) - n². Остаётся сократить всё неравенство на n² и тогда получим, что сумма, которая нам нужна не превосходит 2.

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

Выпишем числа от $1$ до $n2$ и для каждого простого числа $p$ из отрезка $[n,n2]$ подчеркнём те числа, которые делятся на $p.$ Для каждого $p$ будет подчёркнуто в точности $[n2] n2 p > p − 1$ чисел, причём каждое число будет подчёркнуто не больше одного раза. Действительно, если число $k$ подчеркнули как делящееся на простые числа $p$ и $q,$ то $k$ делится и на $2 pq > n ,$ что невозможно. Таким образом, всего подчёркнуто не менее чем $∑ (n2 ) p − 1$ чисел(суммирование ведётся по всем простым числам от $n$ до $2 n$ ). Количество слагаемых в сумме не превосходит $2 n ,$ поэтому вычитается не более $2 n$ единиц. Поскольку количество чисел не меньше $2 n$ и каждое подчёркнуто не более одного раза, всего подчёркиваний меньше, чем $2 n.$ Следовательно,

∑ (n2 ) ∑ n2 n2 > -p − 1 > -p − n2

откуда после сокращения на $n2$ получаем требуемое неравенство $∑ 1p <2.$

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

Задача 9#71931

Сумму

2 2 ⋅5 2 ⋅5 ⋅...⋅2015 3⋅6 +3-⋅6-⋅9 +...+3-⋅6-⋅...⋅2019

записали в виде десятичной дроби. Найдите первую цифру после запятой.

Источники: СпбОШ - 2020, задача 11.4(см. www.pdmi.ras.ru)

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

Для начала упростим данную сумму. Каждое слагаемое запишем в виде разности

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

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

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

Тогда вся сумма телескопически сократится до разности крайних слагаемых

2 2⋅5⋅...⋅2018 3 − 3⋅6⋅...⋅2019

Решение 1.

Оценим вычитаемое. Заведем переменные

A = 1⋅3⋅6⋅...⋅2016, B = 1⋅4⋅7⋅...⋅2017 21⋅⋅54⋅⋅87⋅⋅......⋅⋅22001178 23⋅5⋅6⋅⋅89⋅⋅.....⋅.2⋅2001189 C = 3-⋅6-⋅9-⋅...⋅2019, D = 4⋅7⋅10⋅...⋅2020 4⋅7⋅10-⋅...⋅2020- E = 5⋅8⋅11 ⋅...⋅2022

Мы хотим оценить величину числа $C.$

Поскольку $a−1 -a- a <a+1$ при натуральных $a,$ выполняются неравенства $A < B < C <D < E,$ откуда

ABC <C3 < CDE

Подставив в эти неравенства формулы для наших чисел и сократив дроби, получим

-1-- 3 -2-- 2019 <C < 2022

Тогда

1 ∘--1- ∘--2- 1 15-< 3 2019-<C < 3 2022-< 6

и значит,

1 < 2− 2⋅5⋅...⋅2018-< 3 2 3 3⋅6⋅...⋅2019 5

Таким образом, первая цифра после запятой исходного числа равна $5.$

Решение 2.

Оценим с двух сторон выражение

( )( ) ( ) C = 2⋅5⋅8⋅...⋅2018-= 1− 1 1 − 1 ... 1− --1- (∗) 3⋅6⋅9⋅...⋅2019 3 6 2019

Для этого заметим, что

k − 1 1 ( 1 )3 1 k --k- =1 −k < 1− 3k < 1− k+-1 = k-+1 (∗∗)

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

( ) 1− -1 3 =1− 1 + 1--−--1- 3k k 3k2 27k3

поэтому левое неравенство очевидно. Для проверки правого достаточно установить, что

-12-− -13-= 9k-− 13-<--1---= 1 −--1- 3k 27k 27k k(k+ 1) k k +1

последнее сразу видно после умножения на $27k3$ и раскрытия скобок.

Неравенства $(∗∗)$ позволяют оценить произведение $(∗)$ сверху и снизу. Действительно,

(( 1 )( 1) ( 1) ( -1-))3 1 2 3 673 -1- 1 −3 1− 6 1− 9 ... 1− 2019 < 2 ⋅3 ⋅4 ⋅...⋅674 = 674

поэтому

C <-3√1--< √31--= 1< 1 674 512 8 6

Аналогично

(( 1) ( 1)( -1) ( -1--))3 1 2 3 672- 1-- 1− 6 1− 9 1 −12 ... 1− 2019 > 2 ⋅3 ⋅4 ⋅...⋅673 = 673

Поэтому

C > 2 ⋅3√1-> 2 ⋅3√1--= 2 ⋅ 1=-2 >-1 3 673 3 729 3 9 27 15

Итак, $1-<C < 1 15 6$ и, значит, $1= 2− 1< 2 − C < 2− 1-= 3. 2 3 6 3 3 15 5$

Ответ:

первая цифра после запятой равна $5$

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

Задача 10#71933

Последовательность $(a ) n$ задана условиями

a1 = 1, a2 = 2 и an+2 = an(an+1 +1) при n ≥1.

Докажите, что $aa n$ делится на $(an)n$ при $n ≥100.$

Источники: СпбОШ - 2020, задача 11.6(см. www.pdmi.ras.ru)

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

Пусть простое число $p$ входит в $a n$ в $k$ -й степени. Докажем, что $a an$ делится на $pkn.$ Тогда утверждение задачи будет выполнено.

Пусть $ai$ — первое число в нашей последовательности, кратное $p.$ Если $p⁄= 2,$ то $i> 2$ и $ai = ai−2(ai−1+ 1).$ Следовательно,

ai−1 ≡ −1 (modp)

Заметим, что для $p= 2$ будет $i= 2,$ и выведенное сравнение тоже выполнено.

Итак, $ai−1 ≡ −1,ai ≡ 0,$ а тогда дальше в последовательности чередуются остатки $− 1$ и $0$ от деления на $p:$

a = a (a + 1)≡ −1 ⋅(0+ 1)=− 1 (modp) i+1 i−1 i ai+2 = ai(ai+1+ 1)≡ 0⋅(−1+ 1)=0 (modp) и т.д.

Более того, как видно из последнего вычисления, степени числа $p,$ на которые делятся члены последователыности, растут: если $ai$ делилось на $p,$ то $ai+2$ делится на $2 p$ и т. д. Отсюда следует, что если $an$ делится на $k p,$ то $an+2t$ делится на $k+t p .$ Кроме того, учтем, что числа $an$ и $n$ одинаковой четности, поскольку $a1 =1,$ $a2 = 2$ и остатки по модулю $2$ чередуются. Следовательно, $aan$ делится на $k+(a −n)∕2 p n .$ Остается заметить, что $n an > 2$ при $n≥ 5$ (это значит, что $an$ существенно крупнее $n$ ) и $k an ≥2 ,$ так как делится на $k p$ (это значит, что $an$ существенно крупнее $k$ ), поэтому $an− n >2kn$ , откуда следует требуемое.

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

Задача 11#71908

На доске написано $100$ различных натуральных чисел. К каждому из этих чисел прибавили НОД всех остальных. Могло ли среди $100$ чисел, полученных в результате этих действий, оказаться три одинаковых?

Источники: СпбОШ - 2019, задача 11.2(см. www.pdmi.ras.ru)

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

Предположим, что числа $a< b<c,$ написанные изначально на доске, превратились в три одинаковых числа. Заметим, что НОД, прибавленный к числу $a$ , является делителем чисел $b$ и $c,$ а значит, и их разности $c− b.$ Следовательно, он не превосходит $c− b,$ а значит, заведомо меньше разности $c− a.$ После прибавления этого НОДа к $a$ получилось число, меньшее $c,$ и оно не могло совпасть с числом, полученным из $c.$

Ответ: нет

Интенсивы

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

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

Задача 12#80968

Даны два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $bk− a2$ и $k 2 a − b$ делится на $2018 2 .$

Источники: СпбОШ - 2019, задача 9.6(см. www.pdmi.ras.ru)

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

Будем решать обобщенную задачу. Дано натуральное число $n$ и два нечетных натуральных числа $a$ и $b.$ Докажите, что существует такое натуральное $k,$ что хотя бы одно из чисел $2k 2 b − a$ и $2k 2 a − b$ делится на $n 2 .$

Воспользуемся следующим известным утверждением: пусть число $c− 1$ дает остаток $k 2$ при делении на $k+1 2 ,$ где $k ≥2.$ Тогда $2 c − 1$ дает остаток $k+1 2$ при делении на $k+2 2 .$

Пусть $2 a − 1$ делится на $α 2$ и не делится на $α+1 2 ,$ а $2 b − 1$ делится на $β 2$ и не делится на $β+1 2 .$ Очевидно, что при этом $α,β ≥ 2.$ Тогда $2 a − 1$ дает остаток $α 2$ при делении на $α+1 2 ,$ а $2 b− 1$ дает остаток $β 2$ при делении на $β+1 2 .$ Пусть $α ≤β,$ положим для краткости $β−α 2 = m.$ По лемме число $2m 22 2 a − 1= (((a) )...)− 1$ даёт остаток $β 2$ при делении на $β+1 2 .$

Будем решать задачу индукцией по $n.$ Если $n≤ β+ 1,$ то нам подойдет $k= m,$ поскольку $2m a$ и $2 b$ дают равные остатки при делении на $2β.$ Сделаем переход от $n$ к $n+ 1.$ По индукционному предположению при некотором $k$ число $a2k− b2$ делится на $2n.$ Если оно делится и на $2n+1,$ то переход сделан. Иначе оно дает остаток $2n$ при делении на $2n+1.$ Пусть $r= 2n−β + 1.$ Тогда по лемме $b2(r−1)− 1$ дает остаток $2n$ при делении на $2n+1.$ Следовательно, $b2r− b2$ дает остаток $2n$ при делении на $2n+1.$ Воспользуемся формулой разности степеней:

a2kr− b2r = (a2k− b2)(a2k(r−1)+ a2k(r−2)b2+ ...+ b2(r−1))

Первая скобка дает остаток $2n$ при делении на $2n+1,$ вторая состоит из $r$ нечетных слагаемых и, значит, нечётна. Стало быть, разность $a2kr− b2r$ дает остаток $2n$ при делении на $2n+1.$ Но тогда $a2kr − b2 = (a2kr− b2r)− (b2r − b2)$ делится на $2n+1,$ поскольку выражения в скобках дают одинаковые остатки при делении на $2n+1.$

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

Задача 13#71294

Натуральное число $n$ назовём почти квадратом, если $n$ можно представить в виде $n =ab,$ где $a$ и $b$ — натуральные числа, причем $a ≤b≤ 1,01a.$ Докажите, что для бесконечно многих натуральных $m$ среди чисел $m,m + 1,m + 2,...,m + 198$ нет почти квадратов.

Источники: СпбОШ - 2017, задача 11.4(см. www.pdmi.ras.ru)

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

Предположим противное. Разобьем натуральный ряд на отрезки по $199$ чисел. Тогда во всех отрезках, кроме, быть может, конечного количества $c,$ имеется почти квадрат. Отсюда следует, что среди чисел от $1$ до $2 n$ количество почти квадратов не меньше чем $n2- 199 − c,$ где $c$ — некоторая константа. С другой стороны, каждый такой почти квадрат имеет вид $ab,$ где $a≤n,$ $[ a-] b∈ a,a + 100 ,$ поэтому их количество не больше чем

n∑ ( ) 2 a100-+1 = n + n(n2+001)< n199 − c a=1

при достаточно большом $n.$ Противоречие.

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

Задача 14#70499

В последовательности целых чисел $(a ) n$ сумма $a + a m n$ делится на $m +n$ при любых различных $m$ и $n.$ Докажите, что $a n$ кратно $n$ при любом $n.$

Источники: СпбОШ - 2016, задача 11.1(см. www.pdmi.ras.ru)

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

Распишем $a n$ в хорошем для нас виде

(a3n +an)+ (a5n+ an)− (a5n +a3n)= 2an.

Тогда видим, что каждая скобка в левой части делится на $2n,$ поэтому и правая часть делится, то есть $an$ кратно $n.$

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

Задача 15#80976

Саша перемножил все делители натурального числа $n.$ Федя увеличил каждый делитель на $1,$ а потом перемножил результаты. Федино произведение нацело делится на Сашино. Чему может быть равно $n?$

Источники: СпбОШ - 2016, задача 10.1(см. www.pdmi.ras.ru)

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

Пусть Сашино число имеет делители $1 =d < d < ...<< d = n. 0 1 k$ Заметим, что число $n +1$ взаимно просто со всеми этими делителями, поэтому число $(d0+ 1)(d2+1)...(dk−1+1)$ должно делиться на $d0⋅d1⋅...⋅dk.$ При этом $d1 ≤ d0+1,d2 ≤ d1+1$ и так далее $dk ≤ dk−1+ 1.$ Перемножив эти неравенства, получим, что делимое не превосходит своего делителя, а это возможно только в том случае, когда все неравенства обращаются в равенства. Но тогда $n = dk =dk−1+ 1,$ т. е. $n$ делится на $dk−1 = n− 1.$ Значит, либо $n= 2,$ либо числа $dk−1$ не существует и $n= 1.$

Ответ:

$n =1$ или $n= 2$

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

Задача 16#70349

Натуральные числа $a$ и $b$ больше $1.$ Известно, что числа $a2+ b$ и $a +b2$ простые. Докажите, что числа $ab+ 1$ и $a+ b$ взаимно простые.

Источники: СпбОШ - 2015, задача 11.3(см. www.pdmi.ras.ru)

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

Пусть они не простые. Тогда $ab+ 1$ и $a+ b$ имеют общий простой делитель $p.$ Рассмотрим произведение чисел $a2+ b$ и $a+ b2$ и преобразуем

2 2 22 3 3 2 2 (a + b)(a+ b)= a b +ab+ a +b = ab(ab+ 1)+ (a+ b)(a − ab+ b).

Тогда произведение тоже делится на $p.$ Но поскольку $p ≤a+ b< min(a2+ b,b2+ a),$ число $p$ является собственным делителем какого-то из чисел $a2+b$ или $a+ b2,$ что противоречит их простоте.

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

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

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

Задача 17#70201

Назовём натуральное число почтенным, если сумма всех его делителей, включая $1,$ но не включая само число, на $1$ меньше этого числа. Найдите все почтенные числа, некоторая точная степень которых тоже почтенно.

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

Пусть $n$ — почтенное число. Тогда сумма $d +d + ...+ d 1 2 k$ его делителей, отличных от $n,$ равна $n− 1.$ У числа $nk$ заведомо есть делители

k−1 k−1 d1, d1n,..., d1n , d2, d2n,..., dk, dkn,..., dkn .

Все они различны и отличны от $nk,$ а их сумма равна

2 k−1 (1+ n+ n + ...+n )(d1+ d2+ ...+dk)=

= (1+n +n2 +...+ nk−1)(n− 1)= nk− 1.

Следовательно, у числа $nk$ нет делителей(так как оно тоже должно быть почтенным), отличных от вышеперечисленных. Это означает, что $n$ является степенью простого числа. В противном случае, если $n$ делится на $pt$ (и не делится на $pt+1$ ), то в приведённом выше списке делителей числа $nk$ отсутствует делитель $pt+1.$
Итак, пусть $n= pm.$ Тогда сумма отличных от $n$ делителей числа $n$ равна $1+p +p2+ ...+ pm −1,$ что по условию равно $pm − 1.$ Но

1+ p+ p2 +...+ pm−1 = pm-−1− 1, p− 1

что меньше $pm −1− 1$ при $p⁄= 2$ и равно $pm−1− 1$ при $p =2.$ Таким образом, числа $n =2m$ удовлетворяют условию задачи, а остальные числа не удовлетворяют условию.

Ответ:

все степени двойки, включая нулевую

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

Задача 18#70862

Дано натуральное число $N.$ На доске написаны числа от $N3$ до $N3 +N.$ Среди них $a$ чисел покрасили в красный цвет, а какие-то $b$ из остальных — в синий. Оказалось, что сумма красных чисел делится на сумму синих. Докажите, что $a$ делится на $b.$

Источники: СпбОШ - 2014, задача 11.3(см. www.pdmi.ras.ru)

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

Если $b =1,$ то $a$ делится на $b.$ Поэтому можно считать, что $b≥ 2,$ тогда $a≤N − 1.$
Пусть сумма $a$ чисел равна $3 sa = aN + a1,$ а сумма $b$ чисел равна $3 3 sb =bN +b1 ≥ N .$ По условию $sa$ делится на $sb.$ Обозначим их отношение через $k.$ покажем, что $k≤ N.$ Действительно,

3 3 3 3 sa = aN +a1 ≤ (N − 1)N + a1 ≤(N − 1)(N + N)< (N + 1)N

(последний переход несложно проверить), и значит, $k= s∕s < (N + 1)N3 ∕N3 = N +1. a b$ Поскольку $s =ks , a b$ получим равенство $aN3 +a = k(bN3 + b), 1 1$ или, что то же самое,

3 (a− kb)N =kb1− a1.

Если $a$ не делится на $b$ , т.е. $a ⁄=kb,$ то $|(a − kb)N3 |≥N3,$ и значит, $|kb1− a1|≥ N3.$ Проверим, что на самом деле выполнено неравенство $kb1− a1 ≥ N3,$ т.е. что число $kb1 − a1$ не может быть слишком крупным отрицательным числом. Действительно, $0 ≤a1 ≤ aN$ и $0 ≤b1 < bN,$ и поэтому $kb1 − a1 ≥ −a1 ≥ −aN ≥ −N2.$ Тогда

3 2 3 N ≤ kb1 − a1 ≤ kb1 < kbN ≤ bN ≤ N .

Здесь как раз применяем, что $k ≤N.$ В итоге, противоречие.

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

Задача 19#71157

Дано бесконечное множество натуральных чисел $M.$ Известно, что для любых двух различных чисел $a,b ∈M$ в множестве $M$ также содержится хотя бы одно из чисел $b a − 2$ и $b a +2.$ Докажите, что в $M$ содержится хотя бы одно составное число.

Источники: СпбОШ - 2014, задача 11.5(см. www.pdmi.ras.ru)

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

Решение 1.
Предположим, что множество $M$ состоит только из простых чисел. Тогда все числа из множества $M$ нечётные(так как любое число вида $b 2 ± 2$ составное при $b≥ 3$ ). Возьмём в множестве $M$ два произвольных числа $a,b≥3.$ Если $a$ даёт остаток $1$ при делении на $3,$ то $b a$ также даёт остаток $1.$ Тогда $b a + 2$ делится на 3 и по нашему предположению $b a+ 2$ не может принадлежать множеству $M.$ Значит, в этом случае множеству $M$ принадлежит число $b a− 2.$ Аналогично если $a$ даёт остаток $2$ при делении на $3,$ то $b a$ также даёт остаток $b 2,a − 2$ составное и тогда в этом случае множество $M$ должно содержать число $b a+ 2.$
Если множество $M$ содержит хотя бы одно простое число $a,$ дающее остаток $1$ при делении на $3,$ то в множестве $M,$ как мы установили, содержится число вида $b a − 2,$ дающее остаток $2.$ Тогда число $b a (a − 2) +2$ тоже принадлежит $M.$ Заметим, что это число даёт при делении на $a$ тот же остаток, что и число $(− 2)a+ 2= −2a+ 2.$ Но это число делится на $a$ по малой теореме Ферма, значит, оно составное.
Аналогично, если простое число $a∈ M$ даёт остаток $2$ при делении на $3,$ то в множестве $M$ содержится число $(ab+2)a− 2,$ которое по тем же причинам делится на $a.$
Решение 2.
Предположим противное. Как и в первом решении установим, что если $a≡ ±1$ (mod $3$ ) принадлежит $M,$ то $ab∓ 2≡ ∓1 (mod 3)$ также принадлежит $M.$ В частности, в $M$ есть числа, сравнимые как с $1,$ так и с $− 1$ по модулю $3.$
Рассмотрим простые числа $q ≡ 1 (mod 3)$ и $r$ из $M.$ Тогда в $M$ содержится простое число