Тема Остатки и сравнения по модулю

Китайская теорема об остатках

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

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

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

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

Подтемы раздела остатки и сравнения по модулю

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

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

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

Пусть числа $a$ и $b$ взаимно просты. Докажите, что при делении чисел от 1 до $ab$ на $a$ и на $b$ получаются все возможные пары остатков.

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

Рассмотрим произвольную пару остатков $(n,k),$ где $0 ≤n <a$ и $0 ≤k <b.$ По китайской теореме об остатках для взаимно простых $a$ и $b,$ существует единственное число $c$ такое, что:

c≡ n (mod a) c≡ k (mod b),

причём $0 ≤c <ab.$

Таким образом, для каждой пары остатков $(n,k)$ найдётся ровно одно число $c$ в промежутке от $0$ до $ab− 1,$ дающее при делении на $a$ остаток $n,$ а при делении на $b$ — остаток $k.$

Всего возможных пар остатков $(n,k)$ ровно $a⋅b,$ так как $n$ может принимать $a$ различных значений, а $k$ — $b$ различных значений. Поскольку числа $a$ и $b$ взаимно просты, все эти пары различны и покрывают все числа от $0$ до $ab− 1$ без повторений.

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

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

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

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

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

При каких целых $n$ число $n2+ 3n+ 1$ делится на $55?$

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

Чтобы число $n2 +3n+ 1$ делилось на $55,$ оно должно делиться и на $5,$ и на $11.$

Сначала рассмотрим делимость на $5$ :

2 2 n + 3n+1 ≡(n− 1) ≡0 (mod 5).

Отсюда $n≡ 1 (mod 5).$

Для делимости на $11$ :

2 2 n + 3n+ 1≡ n − 8n +12≡ (n− 2)(n− 6) (mod 11).

Отсюда $n≡ 2 (mod 11)$ или $n≡ 6 (mod 11).$

Для $n ≡1 (mod 5)$ и $n≡ 2 (mod 11)$ по китайской теореме об остатках существует единственное решение при $n <55,$ не трудно заметить, что это 46.

Для $n ≡1 (mod 5)$ и $n≡ 6 (mod 11)$ по китайской теореме об остатках существует единственное решение при $n <55,$ не трудно заметить, что это 6.

Ответ:

$n =55k+ 6$ или $n= 55k +46,$ где $k∈ ℤ.$

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

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

Докажите, что для каждого натурального $n$ существуют натуральные $a$ и $b$ такие, что $4a2+9b2− 1$ делится на $n.$

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

Заметим, что достаточно доказать утверждение для случая, когда $n$ — степень простого числа. Тогда для произвольного $n$ с разложением

k1k2 k n= p1 p2 ...prr

можно решить задачу по каждому модулю $pki, i$ а затем по китайской теореме об остатках совместить решения в одно по модулю $n.$ После этого легко подобрать натуральные $a$ и $b,$ прибавив к ним по необходимости кратные $n.$

Таким образом, остаётся рассмотреть случаи $k n= p ,$ где $p$ — простое.

Рассмотрим сначала модуль $k 2 .$ Число $3$ взаимно просто с $k 2,$ то есть $k (3,2 )= 1,$ а значит, существует обратный к $3$ по модулю $k 2 .$ Возьмём $k a≡ 0 (mod 2),$ $1 k b≡ 3 (mod 2 ).$ Тогда

( 1)2 4a2+ 9b2 ≡ 0+9⋅ 3 ≡ 1 (mod 2k).

Аналогично в модуле $3k$ число $2$ обратимо, поскольку $(2,3k)= 1.$ Возьмём $a ≡ 12 (mod 3k)$ и $b≡ 0 (mod 3k).$ Тогда

( ) 4a2+ 9b2 ≡ 4⋅ 1 2+ 0≡ 1 (mod 3k). 2

Если $p⁄= 2,3,$ то также $k (3,p)= 1,$ и можно взять $k a ≡0 (mod p ),$ $1 k b≡ 3 (mod p),$ что снова даёт

2 2 ( 1)2 k 4a + 9b ≡ 0+9⋅ 3 = 1 (mod p).

Для каждого простого делителя $pi$ числа $n$ мы построили пару $(ai,bi),$ таких что

4a2i +9b2i ≡ 1 (mod pkii).

По китайской теореме об остатках существует пара $(a,b),$ такая что

a ≡ai (mod pkii), b≡ bi (mod pkii )

для всех $i,$ и при этом

4a2+ 9b2 ≡ 1 (mod n).

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

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

Полезное следствие из КТО. Докажите, что для любых попарно взаимно простых чисел $m ,m ,...,m 1 2 n$ и остатков $r,r,...,r 1 2 n$ по модулям $m1,m2,...,mn$ найдутся $n$ последовательных чисел $a+ 1,a+ 2,...,a +n$ таких, что $a+ i≡ ri (mod mi).$

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

Потребуем, чтобы для некоторых подряд идущих $n$ чисел $a+1,...,a+ n$ выполнялось $a +i≡ r (mod m ) i i$ при всех $i= 1,...,n.$

Это равносильно системе сравнений для одного числа $a$ :

a≡ − ri− i (mod mi), i= 1,...,n.

Модули попарно взаимно просты, значит, по Китайской теореме об остатках система имеет решение $a.$ Тогда числа $a+1,$ …, $a+ n$ дают нужные остатки.

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

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

Докажите, что найдутся $2020$ последовательных натуральных чисел, каждое из которых имеет по меньшей мере три различных простых делителя.

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

Возьмём первые $6060$ простых чисел $p , 1$ $p, 2$ …, $p . 6060$ Потребуем, чтобы каждое из чисел $a+1,$ $a+ 2,$ …, $a+ 2020$ делилось хотя бы на три различных простых числа. Зададим систему сравнений:

(| ||||| a≡ −1 (mod pi) (i= 1,2,3) ||||| a≡ −2 (mod pi) (i= 4,5,6) |||{ ... | ||||| a≡ −k (mod pi) (i= 3k− 2, 3k− 1, 3k) ||||| ... |||( a≡ −2020 (mod pi) (i=6058, 6059, 6060)

Модули попарно просты, поэтому по следствию из КТО существует решение $a,$ причём $a$ можно взять натуральным. Тогда для каждого $k= 1,$ …, $2020$ число $a +k$ кратно трём попарно различным простым числам $p3k−2,$ $p3k−1,$ $p3k,$ следовательно, имеет по меньшей мере три различных простых делителя.

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

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

Докажите, что

(a) множество простых делителей чисел вида $t2+ t+ 1$ бесконечно;

(b) существует $t$ такое, что $t2+ t+1$ имеет хотя бы $2020$ различных простых делителей.

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

(a) Пусть $f(t)= t2+t+ 1.$ Предположим, что существует лишь конечное множество простых чисел, которые делят хотя бы одно значение $f(t).$ Обозначим их $p1,$ $p2,$ …, $ps.$ Рассмотрим произведение

ˆt= p1p2...ps.

Тогда $ˆ t ≡0 (mod pi)$ для любого $i=1,...,s,$ и потому

f(ˆt)= ˆt2+ ˆt+ 1≡ 0+0+ 1≡ 1 (mod pi).

Значит, ни одно из простых $p , 1$ …, $p s$ не делит $f(ˆt).$ Следовательно, у $f(ˆt)$ найдётся простой делитель, отличный от $p1,$ …, $ps.$ Получили противоречие. Таким образом, простых, которые встречаются в значениях $ˆ f(t),$ бесконечно много.

(b) Из пункта (a) мы знаем, что таких простых бесконечно много. Выберем любые $2020$ различных простых $p1,$ $p2,$ …, $p2020,$ для которых $f(ti)≡ 0 (mod pi)$ при некоторых $ti.$ Заметим, что для любого целого $n:$

f(ti+ npi)≡ f(ti)≡ 0 (mod pi).

Потребуем следующую систему сравнений:

(||t≡ t (mod p ) |||||- 1 1 {t≡ t2 (mod p2) |||| ... |||(- t≡ t2020 (mod p2020)

Так как простые $p, 1$ …, $p 2020$ попарно различны, система имеет решение по Китайской теореме об остатках. Для такого $t$ имеем

- f(t)≡ 0 (mod pi), i= 1,...,2020,

и значит, $f(t)$ делится как минимум на $2020$ различных простых чисел.

Курсы

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

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

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

Дано $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$ по китайской теореме об остатках.

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

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

Дано конечное множество $A$ натуральных чисел. Докажите, что существует натуральное число $b$ такое, что для каждого $a∈A$ число $ab$ будет степенью (выше первой) натурального числа.

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

Подсказка 1

Ясно, что рассуждать нужно о степенях вхождения простых чисел. Пусть a — элемент множества A, в которое простое число p входит в степени n. Предположим, что ab должно стать k-ой степенью простого числа. В какой степени должно входить простое число p в b?

Подсказка 2

Верно! В степени, сравнимой с -n по модулю k. Если p делит другие элементы A, то может оказаться так, что в эти элементы оно входит в степенях, не сравнимых с -n, и сделать их k-ой степенью не получится. Попробуем сделать их различными степенями натуральных чисел. Как этого можно добиться?

Подсказка 3

Верно! Заведомо выберем для каждого элемента множества A, какой степенью оно должно стать, после домножения на b. Попробуем теперь выбрать степень для простого числа p, в которой оно должно входить в b. Для этого придется посмотреть на степени вхождения p во все элементы A. Какое условие будет достаточным, чтобы при умножении на b получились степени натуральных чисел?

Подсказка 4

Как мы уже поняли, чтобы сделать k-ую степень натурального числа, нужно сделать так, чтобы p входило в b в степени, сравнимой с -l, если l — степень вхождения p в элемент множества A. Тогда выходит много сравнений для степени вхождения p в b. Как гарантировать существование такой степени вхождения!

Подсказка 5

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

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

Пусть $A = {a ,a,...,a }. 1 2 n$ Выберем любые различные простые числа $p,p ,...,p 1 2 n$ так, что каждое из них больше степени вхождения любого простого числа в любой элемент множества $A.$ Теперь покажем, что можно выбрать $b$ так, чтобы $a1b,$ $a2b,$ …, $anb$ были соответственно $p1,p2,...,pn$ степенями натурального числа. Для этого рассмотрим простое число $p,$ которое входит хотя бы в один из элементов множества $A.$ Пусть $k1 k2 kn a1 = p s1,a2 = p s2,...,an = p sn,$ где $k1,k2,...,kn ∈ℕ0$ и $s1,s2,...,sn$ — числа, не делящиеся на $p.$ Выберем число $α∈ ℕ$ так, чтобы для каждого $i= 1,2,...,n$ выполнялось сравнение $α ≡− ki (mod pi)$ (это возможно по китайской теореме об остатках). Тогда $p$ входит в число $α p ai$ в степени, делящейся на $pi,$ поскольку $α +ki ≡ 0 (mod pi).$ Аналогичное действие выполним для всех простых чисел $r1,r2,...,rm,$ делящих хотя бы один из элементов множества $A$ и определим для них числа $α1,α2,...,αm.$ Положим $α1 α2 αm b= r1 r2 ...rm$ и задача решена.

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

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

Даны натуральные $a$ и $b.$ Известно, что для любого натурального $n$ число $an+ n$ делится на $bn+ n.$ Докажите, что $a =b.$

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

Подсказка 1

Попробуем доказать, что разность a и b сравнима с нулем по модулю какого-нибудь очень большого числа. Как от исходного условия перейти к исследованию разности?

Подсказка 2

Верно! Легко видеть с помощью простого вычитания делителя, что условие задачи эквивалентно тому, что разность n-ых степеней a и b делится на сумму n-ой степени b и n. Попробуем для произвольного простого числа p изготовить такое n, чтобы эта сумма на него делилась. Как это сделать?

Подсказка 3

Точно! Просто берем n, имеющее остаток -b по модулю p и остаток 1 по модулю p-1. Тогда легко показать по малой теореме Ферма, что сумма n-ой степени b и b делится на p. А что это означает для разности n-ый степеней a и b?

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

Ясно, что если $an+n$ делится на $bn +n,$ то и $(an +n)− (bn +n)= an− bn$ также делится на $bn +n.$ Рассмотрим произвольное простое число $p.$ Возьмём такое $n,$ что $n ≡ −b (mod p)$ и $n≡ 1 (mod p− 1).$ Благо, КТО позволит выбрать такое $n.$ Заметим, что в этом случае $n n n−1 b +n ≡b − b≡ b(b − 1)≡0 (mod p),$ так как либо $p$ делит $b,$ либо они взаимно просты и $n − 1$ делится на $p − 1,$ тогда вторая скобка по МТФ сравнима с $0.$ Отсюда $n n a − b$ кратно $p,$ то есть $n n a ≡ b (mod p).$ В силу выбора $n$ имеем $n n a ≡a ≡b ≡ b (mod p).$ То есть $a ≡b (mod p)$ для любого простого числа $p.$ Отсюда нетрудно показать равенство $a$ и $b.$ Возьмём такое простое число, которое больше разности $a$ и $b.$ Ясно, что в этом случае $a− b$ на него поделится лишь когда $a= b.$ Что и требовалось.

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

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

Два различных простых числа $p$ и $q$ отличаются менее чем в два раза. Докажите, что существуют такие два последовательных натуральных числа, что у одного из них наибольший простой делитель равен $p,$ а у другого — $q.$

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

Первое решение. Без ограничения общности будем считать, что $p< q <2p.p,q$ взаимно просты, по малой теореме Ферма

q−1 p ≡ 1 (mod q),

а значит существует некоторый остаток

q−2 r≡ p (mod q)

такой, что $r∈ {0,1,2,...,q− 1}$ и

pr− 1 ≡0 (mod q).

В силу того, что $q < 2p$ либо $0< r≤ p,$ либо $q > r> p$ и тогда $0< q− r< q− p <2p− p= p.$ При этом $p(q− r)+ 1≡ −1+ 1≡ 0 (mod q).$

Если $0< r≤ p,$ можно взять два последовательных натуральных числа числа $pr− 1$ и $pr.$ У числа $pr ≤p2$ — наибольший простой делитель $p,$ а у числа $pr− 1 ≤p2− 1$ наибольший простой делитель равен $q$ ( $p,q$ — наибольшие простые делители, иначе бы числа $pr,pr− 1$ были бы больше $p2,q2$ соответственно).

Если же $q >r> p,$ то возьмем последовательные натуральные числа $p(q− r),$ $p(q− r)+ 1.$ Тогда у числа

p(q− r)< p(2p− r)< p(2p− p)= p2

— опять-таки $p$ наибольший простой делитель, а у числа

p(q− r)+ 1< q⋅q+ 1

наибольший простой делитель равен $q,$ иначе бы

q2+ 1> p(q− r)+1≥ q⋅(q+1)= q2+ q,

то есть $1 >q,$ что не выполняется.

Следовательно, существуют такие два последовательных натуральных числа, что у одного из них наибольший простой делитель равен $p,$ а у другого — $q.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Пусть $p> q.$ По китайской теореме об остатках существует такое $n < pq,$ что $n ≡ 0 (mod p)$ и $n +1≡ 0 (mod q).$

Число $n$ делится на $p,$ и поскольку $p2 > pq > n,$ у него не может быть простого делителя больше $p,$ значит, $p$ — наибольший простой делитель $n.$

Число $n+ 1$ делится на $q.$ Если бы у него был больший простой делитель $r> q,$ то

n+ 1≥ rq >q2.

Тогда $n +1 >q2.$

Рассмотрим теперь числа $pq− n$ и $pq− n − 1.$ Первое делится на $p,$ второе — на $q.$

Число $pq − n <p2,$ так как $p2 > pq,$ поэтому $p$ — наибольший простой делитель.

Число $pq − n − 1< q2,$ поэтому $q$ — наибольший простой делитель.

Значит, мы нашли нужную пару чисел.

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

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

Сколько существует натуральных чисел $n$ , меньших $10000$ , для которых $2n− n2$ делится на $7?$

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

Заметим, что $2n$ даёт только остатки $1,2,4$ по модулю $7$ для $n = 3k,3k+ 1,3k+ 2,k ∈ℕ ∪{0}$ соответственно.

Для $2 n$ имеем

2 n ≡7 1 при n ≡7 ±1

n2 ≡7 2 при n ≡7 ±3

n2 ≡ 4 при n ≡±2 7 7

По условию нам нужно $2n ≡ n2 7$

В качестве примера рассмотрим $2n ≡ n2 ≡ 1 7 7$ . Здесь накладываются два условия $n≡ 0,n≡ ±1 3 7$ . Уместно воспользоваться Китайской теоремой об остатках, которая говорит нам, что таких чисел будет ровно два в наборе ${1,2...21= 3⋅7}$ , но можно и явно найти эти числа — $15,6$ . Здесь легко видеть, что от сдвига набора ничего не поменяется, поскольку нам важно только наличие всех остатков по модулю $21$ ровно по одному разу.

Абсолютно аналогично по два числа в каждом наборе из $21$ подряд идущего подойдут для остатков $2$ и $4$ , то есть в итоге из каждых $21$ нам подойдут $6$ чисел.

Поскольку $10000= 476⋅21+4$ , то из первых $476$ групп подойдут $476⋅6$ . Остаются числа чисел $9997,9998,9999$ , из которых подходит $9998≡7 2$ . Получаем ответ

6⋅476+ 1= 2857

Ответ: 2857

Интенсивы

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

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

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

Генерал построил солдат в колонну по $4,$ но при этом солдат Иванов остался лишним. Тогда генерал построил солдат в колонну по $5.$ И снова Иванов остался лишним. Когда же и в колонне по $6$ Иванов оказался лишним, генерал посулил ему наряд вне очереди, после чего в колонне по $7$ Иванов нашел себе место и никого лишнего не осталось. Какое наименьшее число солдат могло быть у генерала?

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

Подсказка 1

Предположим, что всего солдат n. Тогда по условию n = 7t и n имеет остаток 1 при делении на 4, 5 и 6. Можно ли вместо условий на n получить условия на t?

Подсказка 2

Верно! Например, 7t имеет остаток 1 при делении на 5, что означает t = 5k - 2. Можно ли продолжать аналогичные действия, пока все данные сравнения не будут использованы?

Подсказка 3

Можно! В конце получаем, что n = 420r - 119. Тогда чему равно наименьшее значение n?

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

Пусть всего $n$ солдат, тогда имеют место следующие сравнения: $n≡ 1 (mod 4),n≡ 1 (mod 5),n≡ 1 (mod 6)$ и $n ≡0 (mod 7).$ Из последнего сравнения следует, что $n= 7t,t∈ℕ.$ Также необходимо, чтобы $7t≡1 (mod 5),$ а это происходит лишь когда $t= 5k− 2,k ∈ℕ.$ Таким образом, $n= 35k − 14≡ 1 (mod 4),$ откуда $k= 4m − 3,m ∈ℕ.$ Следовательно, $n = 140m − 119.$ Осталось заметить, что при $m =3r,r∈ℕ$ выполняется третье сравнение. Наконец, $n =420r− 119.$ Теперь видно, что $n ≥301.$

Ответ:

$301$

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

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

Сколько четырёхзначных чисел подходит под условие $x2 ≡x (mod 10000)?$

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

Подсказка 1

Условие означает, что x(x-1) делится на 10000. Может ли x или x-1 делится на 10000?

Подсказка 2

Верно, не может, поскольку x — четырехзначное число. Тогда x делится на 2⁴ и x - 1 делится на 5⁴ или наоборот. Тогда в качестве x или x - 1 нужно подобрать четырехзначное число, делящееся на 625. Как это сделать?

Подсказка 3

Верно! Можно перебрать все числа, делящиеся на 625, начиная с 1250 и заканчивая 9375, попутно проверяя условие делимости одного из чисел x или x-1 на 16.

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

Нетрудно понять, что если $x2− x ≡0 (mod 10000),$ то $x(x− 1)$ должно делиться на $24$ и $54.$ Очевидно, что $x$ и $x − 1$ взаимно просты. Также понятно, что ни $x,$ ни $x − 1$ не могут делиться одновременно на $4 2$ и $4 5 ,$ потому что $x$ — четырёхзначное число. Поэтому возможны два случая:

$1)$ $x$ делится на $4 2$ и $x − 1$ делится на $4 5 .$

$2)$ $x− 1$ делится на $4 2$ и $x$ делится на $4 5 .$

Попробуем подобрать на место $x$ или $x− 1$ четырёхзначное число, кратное $625.$ Понятно, что оно не меньше $1250$ и не больше $9375.$ Также оно должно быть нечётным. Из оставшихся вариантов перебором понимаем, что можно только поставить $625⋅15$ на место $x − 1.$

Ответ:

$1$

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

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

Диме выдали натуральное число $N.$ Он разделил его на 101 и получил в остатке $m > 0.$ Затем Дима разделил $N$ на $m$ и получил в остатке $p.$ Найдите наибольшее значение $p,$ которое могло получиться, а затем — наименьшее $N,$ при котором это значение $p$ достигается.

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

Подсказка 1

По условию p — остаток от деления на m, а m — остаток от деления на 101. Какие наибольшие значения могут принимать p и m?

Подсказка 2

Верно! p не превосходит m - 1, а m не превосходит 100. Тогда p не больше 99. По условию N = 101t - 1. Мы хотим найти наименьшее N, имеющее остаток 99 при делении на 100. Какое условие получается на t?

Подсказка 3

Верно! Получается, что t делится на 100. Тогда N = 10100s - 1. Каково наименьшее значение N?

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

Понятно, что $p≤ m− 1,$ так как $p$ — остаток при делении на $m.$ Также ясно, что $m≤ 100,$ так как это остаток при делении на $101.$ Таким образом, имеем $p≤ m− 1≤ 99.$ То есть максимальное значение $p$ равно $99.$ Оно реализуется при $m = 100.$ Теперь найдём наименьшее $N.N ≡ 100 (mod 101),$ а значит $N = 101t− 1.$ Заметим, что для справедливости сравнения $N ≡ 99 (mod 100)$ необходимо и достаточно, чтобы $t$ делилось на $100,$ то есть $N =10100s − 1.$ Таким образом, минимальное $N$ — $10099.$

Ответ:

$p = 99,N = 10099 max min$

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

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

Докажите, что натуральные $n,$ для которых $nn+ 1$ делится на $30,$ образуют арифметическую прогрессию.

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

Подсказка 1

Разбираться сразу с делимостью на 30 сложно, поэтому попробуйте рассмотреть по отдельности простые делители: 2, 3 и 5. Какие значения n обращают nⁿ + 1 ≡ 0 (mod p) в верное для каждого из них? Как можно объединить результат?

Подсказка 2

Показательные и степенные функции по модулю часто становятся периодическими. Попробуйте рассмотреть nⁿ + 1 по модулю 10 и выяснить, повторяются ли остатки. Как можно это проверить?

Подсказка 3

Попробуйте доказать, что нужные n обязаны быть одновременно вида 10k – 1 и 3m – 1. Какие n этому удовлетворяют? Что можно сказать про арифметическую прогрессию, которую они образуют? Почему выходит именно арифметическая прогрессия?

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

Покажем, что остатки $nn+ 1$ по модулю $10$ зацикливаются. Нетрудно убедиться в том, что $n5 ≡ n (mod 10),$ а значит, $k k+4 n ≡n (mod 10),$ из чего следует, что $n n+20 n+20 n ≡ n ≡ (n+ 20) (mod 10).$ Осталось вручную посчитать остатки в цикле и понять, что $n n +1$ делится на $10$ лишь при $n =10t− 1.$

Теперь разберёмся с делимостью на $3.$ Понятно, что $n$ не может делиться на $3.$ Если $n ≡ 1 (mod 3),$ то $n n + 1≡ 2 (mod 3).$ Если же $n≡ 2 (mod 3),$ то $n n +1 ≡0 (mod 3).$

Таким образом, $n= 30s− 1,$ то есть все нужные $n$ образуют арифметическую прогрессию, что и требовалось.

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

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

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

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

Подсказка 1

Могут ли подойти четные числа?

Подсказка 2

Верно, не могут, поскольку каждое нечетное число представимо в виде суммы четного и нечетного. Попробуем доказать, что все нечетные числа подходят. Для этого выберем любое натуральное число x и попробуем разложить его в сумму a + b. Как удобно выбрать a + b?

Подсказка 3

Понятно, что нужно думать об остатках при делении на простые числа, входящие в n. Пусть p — простое число, делящее n, а r — остаток x при делении на p. Как выбрать остатки чисел a и b?

Подсказка 4

Верно! Можно просто положить, что a сравнимо с 1, а b сравнимо с r-1 по модулю p, если, конечно, r не равно 1. Тогда по КТО все получится. А что делать, если r сравнимо с 1?

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

Заметим, что чётные числа не подходят, так как всякое нечётное всегда представимо в виде суммы чётного и нечётного.

Покажем, что все нечётные числа подходят. Рассмотрим произвольное нечётное $n$ и разложим его по ОТА: $α1 αk n= p1 ...pk .$ Теперь рассмотрим произвольное число $x.$ Пусть $x= a+ b.$ Попробуем для каждого $pi$ из разложения $n$ подобрать ненулевые остатки для $a$ и $b$ по модулю $pi.$ Пусть $x$ даёт остаток $rpi$ при делении на $pi.$ Тогда для $a$ можно взять остаток $1,$ а для $b$ — остаток $rpi − 1,$ если $rpi ⁄= 1.$ В противном случае для $a$ возьмём остаток $2,$ а для $b$ — $− 1.$ И так подберём остатки для каждого простого числа из разложения. Осталось заметить, что по КТО существуют такие числа $a$ и $b,$ дающие подобранные остатки при делении на простые числа из разложения.

Ответ:

Все нечётные числа

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

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

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

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

Назовем число хорошим, если оно делится на квадрат натурального числа большего $1.$ При каких $N$ найдется $N$ последовательных хороших чисел? (Пример для $N =3 :48,49,50$ ).

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

Подсказка 1

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

Подсказка 2

Мы можем взять число x так, чтобы оно делилось на квадрат какого-то простого числа. А можно ли взять x + 1 так, чтобы оно делилось на квадрат другого простого числа?

Подсказка 3

Верно! По КТО это вполне возможно. А можно ли взять большее количество простых чисел?

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

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

Давайте возьмем $N$ различных попарно взаимно простых чисел (например, $N$ простых чисел) $p1$ , $p2$ , ..., $pN$ и захотим, чтобы для какого-то $x$ число $x+ 1$ делилось на $2 p1$ , $x +2$ делилось на $2 p2$ , $x+ 3$ делилось на $2 p3$ и т. д. Такие числа существуют, так как по КТО существует такое $x$ , что:
$x ≡− 1$ (mod $2 p1$ )
$x ≡− 2$ (mod $2 p2$ )
...
$x ≡− N$ (mod $2 pN$ )

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

Рассмотрим $N$ чисел: $p21,...,p2N,$ где $pi$ — $i$ -е простое число. Попробуем найти такое число $x,$ что $x$ делится на $p21,x+ 1$ делится на $p22,...,x+ N − 1$ делится на $p2N.$ Нетрудно понять, что это равносильно тому, что $x≡ 1− i (mod p2i),i∈ 1,2,...,N.$ Теперь видно, что по КТО такое число существует, поскольку модули всех сравнений взаимно просты.

Ответ: при любых

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

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

Дано натуральное $n$ и различные целые числа $a,a ,...,a (k≥2) 1 2 k$ от $1$ до $n.$ Известно, что $n$ делит $a(a − 1) i i+1$ для всех $i= 1,2,...,k− 1.$ Докажите, что $n$ не делит $ak(a1− 1).$

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

Подсказка 1

Для каждого i рассмотрим наибольший общий делитель числа aᵢ и числа n. Что можно сказать про эти НОДы, если предположить, что n ∣ aₖ(a₁−1)?

Подсказка 2

Подумайте, как условие n ∣ aᵢ(aᵢ₊₁−1) связывает делимость каждого aᵢ с делимостью aᵢ₊₁−1. Можно ли «передавать» это условие вдоль всей последовательности?

Подсказка 3

Если из рассуждений получится, что все числа aᵢ делятся на одно и то же d, а все aᵢ−1 сравнимы с 1 по модулю d, то сколько различных таких чисел может уместиться в отрезке от 1 до n? Попробуем дойти до противоречия.

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

Пойдём от противного, пусть $n$ делит $a (a − 1). k 1$ Для каждого $a i$ посчитаем НОД $(a,n) i$ и рассмотрим такое $a , t$ у которого получился наибольший НОД. Пусть полученный НОД $(at,n)$ равен $d$ ( $d≤ n$ ). По условию $at− 1(at− 1)$ делится на $n,$ однако $(at− 1)$ не может делиться на $d,$ значит $d$ делит $at−1.$ Но по условию и $at− 2(at−1 − 1)$ делится на $d,$ а значит, что $at−2$ также делится на $d.$ Аналогичными рассуждениями получаем, что все $ai$ при $1 ≤i≤ t− 1$ делятся на $d.$ Далее с помощью предположения, что $ak(a1− 1)$ делится на $d,$ понимаем, что $ak$ кратно $d.$ Следовательно, $d$ делит и $ak−1,$ поскольку $ak−1(ak− 1)$ кратно $n.$ Далее, продолжая цепочку рассуждений, приходим к выводу, что все $ai$ от при $t+ 1≤ i≤k$ также кратны $d.$ Поскольку $d$ — наибольший НОД среди всех вида $(ai,n),$ получаем, что $(ai,n)=d$ для любого $i∈ {1,2,...,k}.$

Пусть $n= dd1.$ По условию $ai(ai+1− 1)$ кратно $n,$ а значит необходимо, чтобы $ai+1 ≡1 (mod d1).$ В силу произвольности $i$ получаем, что $ai ≡ 1 (mod d1)$ при всех $i$ от $1$ до $k.$

Заметим, что $d$ и $d1$ взаимно просты, в противном случае пусть их НОД равен $x.$ Выше мы доказали, что $ai$ кратно $d,$ а $ai− 1$ кратно $d1$ и получается, что оба числа кратны $x.$ Тогда $ai− (ai− 1) =1$ также должно делиться на $x,$ противоречие.

Итак, у нас есть $k$ чисел, каждое из которых делится на $d$ и сравнимо с $1$ по модулю $d1.$ В силу взаимной простоты $d$ и $d1$ из КТО получаем, что такие числа должны иметь вид $sdd1+ 1=sn +1$ , где $s∈ ℕ.$ Но чисел такого вида лежащих в промежутке от $1$ до $n$ может быть только одно, а по условию их $k≥ 2.$ Противоречие.

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

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

Пусть $n$ — натуральное число, а $p <p < ...< p 1 2 n$ — простые числа. Обозначим через $P m$ произведение первых $m$ из них. Докажите, что существует натуральное число $k$ такое, что для каждого $i$ от $1$ до $n$ числа $Pn$ и $k+ Pi$ взаимно просты.

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

Подсказка 1

Рассмотрим одно фиксированное простое pᵢ. Какой остаток по модулю pᵢ нужно избежать, чтобы числа Pₙ и k+pᵢ не имели общих делителей?

Подсказка 2

Все числа Pₙ дают при делении на pᵢ не так уж много разных остатков. Посчитаем, сколько именно, и почему этого недостаточно, чтобы покрыть все возможные остатки.

Подсказка 3

Если некоторый остаток по модулю pᵢ никогда не встречается, то можно выбрать k так, чтобы именно он появился. Как совместить такие условия сразу для всех простых p₁, …, pₙ?

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

Рассмотрим произвольное число $p i$ из набора. Попробуем подобрать для $k$ такой остаток по модулю $p, i$ чтобы $p i$ никогда не входило в $(Pn,k+Pm ).$ Понятно, что $r⁄= 0,$ иначе при $m≥ i$ условие нарушится. Числа $p1,p1p2,...,p1p2p3...pi−1$ суммарно дают не более $i− 1$ остатка при делении на $pi.$ Таким образом мы поняли, что числа $Pm$ имеют не более $i$ различных остатков по модулю $pi.$ Нетрудно понять, что $pi > i,$ потому что $pi$ не меньше $i$ -го простого числа из натурального ряда, которое, в свою очередь, больше $i.$ Но тогда существует такой остаток $rpi,$ который не встречается среди остатков чисел $Pm$ при делении $pi.$ Таким образом, можно взять $r= pi− rpi.$ Осталось заметить, что по КТО существует такое $k,$ что $k ≡pi− rpi (mod pi)$ при $i∈1,2,...,n,$ что и требовалось.

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

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

В ряд выписано $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$ простых.