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

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

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

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

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

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

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

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

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

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

Дано конечное множество $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$ и задача решена.

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

Задача 3#74252

Даны натуральные $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.$ Что и требовалось.

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

Задача 4#37808

Сколько существует натуральных чисел $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

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

Задача 5#51001

Петя, Вася и Иван каждый на своей карточке написал наугад по одной цифре и передали карточки Маше так, чтобы она не видела написанных цифр. Маша случайным образом перемешала карточки и выложила их в ряд на стол. Найти вероятность того, что на столе можно увидеть трехзначное число, кратное $5$ и имеющее при делении на $7$ остаток $3.$

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

Можно считать, что мы получаем на столе равновероятно любое число от $0$ (на трёх карточках могут быть нули) до $999$ . Тогда для вычисления вероятности нужно число благоприятных исходов поделить на число возможных исходов — на $1000.$

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

Используя Китайскую теорему об остатках, получаем, что среди любых $35$ подряд идущих чисел нам подходит ровно одно с остатком $10$ по модулю $35$ . Первое такое трёхзначное число — $115$ , затем идут $150,185,...115+ 35 ⋅25= 990$ : всего чисел $26$ . Осталось поделить на $1000$ и получить ответ.

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

По условию искомое трёхзначное число $x$ кратно $5$ и при делении на $7$ даёт остаток $3$ , то есть

x= 7n+ 3= 5n+ 5+(2n− 2),n∈ ℤ

С учётом этих условий получаем

2n− 2= 5k,k∈ ℤ =⇒ k= 2t,t∈ℤ =⇒ n= 5t+ 1 =⇒ x= 7(5t+ 1)+3 =35t+ 10

Осталось учесть условие на трёхзначность:

90 989- 100 ≤35t+ 10 <999 ⇐⇒ 2< 35 < 3≤ t≤ 28 < 35 <29

Подходят $28− 3+ 1= 26$ значений $t$ .

Ответ:

$0,026$

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

Задача 6#80909

Генерал построил солдат в колонну по $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$

Курсы

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

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

Задача 7#80910

Сколько четырёхзначных чисел подходит под условие $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$

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

Задача 8#80911

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

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

Задача 9#80912

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

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

Покажем, что остатки $nn+ 1$ по модулю $10$ зацикливаются. Нетрудно убедиться в том, что $n5 ≡ n (mod 1)0,$ а значит $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$ образуют арифметическую прогрессию, что и требовалось.

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

Задача 10#80913

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

Ответ:

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

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

Задача 11#80914

Назовем число хорошим, если оно делится на квадрат натурального числа большего $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.$ Теперь видно, что по КТО такое число существует, поскольку модули всех сравнений взаимно просты.

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

Интенсивы

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

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

Задача 12#80915

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

(a) простым числом или степенью простого числа;

(b) степенью (не ниже второй) натурального числа.

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

(a) Для того, чтобы число не являлось степенью простого, достаточно, чтобы в его разложение входило хотя бы два простых числа. Рассмотрим $2000$ простых чисел $p1,p2,...,p2000.$ По КТО существует такое число $a,$ что $a ≡0 (mod p1p2),a≡ −1 (mod p3p4),...,a≡ −999 (mod p1999p2000).$ Осталось заметить, что это равносильно тому, что каждое из чисел $x,x+1,...,x+ 999$ имеет хотя бы по два простых делителя, а значит не является степенью простого числа, что и требовалось.

(b) Для того, чтобы число не являлось квадратом, достаточно, чтобы оно делилось на некоторое простое число $p,$ но не делилось на $p2.$ Рассмотрим $1000$ простых чисел $p1,p2,...,p1000$ и заметим, что по КТО существует такое число $b,$ что $b≡ p1 (mod p21),b≡ p2− 1 (mod p22),...,b≡ p1000 − 999 (mod p21000).$ Нетрудно понять, что числа $b,b+ 1,...,b+ 999$ подходят.

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

Задача 13#80916

Дано натуральное $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).$

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

Пойдём от противного, пусть $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.$ Противоречие.

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

Задача 14#80917

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

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

Рассмотрим произвольное число $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,$ что и требовалось.

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

Задача 15#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$ простых.

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

Задача 16#83148

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

(a) простым числом или степенью простого числа;

(b) степенью (не ниже второй) натурального числа.

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

Подсказка 1, пункт а

Если число не является простым, то у него есть хотя бы два простых делителя. Число x можно выбрать так, чтобы оно делилось на 2 × 3 = 6. А какими свойствами удобно было бы наделить число x + 1?

Подсказка 2, пункт а)

Верно! Удобно сделать так, чтобы x + 1 делилось на 5 × 7. Подходящее x существует по китайской теореме об остатках. А можно ли аналогичным образом построить x + 2, ..., x + 999?

Подсказка 1, пункт б)

Если число делится на простое p, но не делится на p², то оно нам подходит. Можно ли, пользуясь этим замечанием, построить подходящую последовательность?

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

Чтобы число не было степенью никакого простого числа, то у него должно быть хотя бы 2 простых делителя. Давайте с помощью КТО найдем такое $x$ , что
$x ≡− 1$ (mod $2⋅3$ )
$x ≡− 2$ (mod $5⋅7$ )
...
$x ≡− 1000$ (mod $p1999⋅p2000$ )
Тогда такой ряд $x+ 1$ , ...., $x+ 1000$ подойдет.

Во втором пункте, заметим, что если у числа есть простой делитель ровно в первой степени, то оно точно не степень, то есть если число $A ≡ p$ (mod $p2$ ), где $p$ — простое, то $A$ делится на $p$ и не делится на $p2$ и тогда $A$ - хорошее

Опять же по КТО найдем такое $x$ , что:
$x +1≡ p1$ (mod $p21$ )
$x +2≡ p2$ (mod $p22$ )
...
$x +1000≡ p1000$ (mod $p21000$ )

Тогда ряд $x+ 1$ , ...., $x +1000$ подойдет.

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

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

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

Задача 17#83149

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

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

Давайте для начала рассмотрим ряд

2,4,6,8,10,12...

Сумма первых $n$ будет равна

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

, но этот ряд нам не подходит, потому что в этом ряду у числа 1 не будет места. То есть важно помнить, что в нашем ряду должны быть все числа.

Давайте так и будем составлять наш ряд.
Начнем с 1, 3, 2. Теперь хотелось бы поставить дальше 4, чтобы она не потерялась и была в нашем ряду, но на четвертое место она не подходит, поэтому давайте продлим наш ряд так: 1, 3, 2, $x$ , 4, чтобы $x+ 6$ делилось на 4 и $x +10$ делилось на 5. По КТО такое $x$ (например, $x =10$ ) существует и их бесконечно много (так как $x+20$ , $x+ 40$ , ... нам подойдут). Теперь продолжаем наш ряд 1, 3, 2, 10, 4, $y$ , 5. Хотим, чтобы $y+ 20$ делится на 6 и $y+25$ делится на 7 и по КТО таких чисел очень много.

Теперь давайте сформулируем в общем виде. Пусть у нас есть уже ряд $x1$ , $x2$ , ..., $xn$ . Мы хотим добавить на $n+ 2$ место минимальное еще неиспользованное число $b$ . Тогда по КТО мы можем найти такое $z$ , что:
$x1+ x2+ ...+ xn+ z$ делиться на $n+ 1$
$x1+ x2+ ...+ xn+ z+ b$ делиться на $n +2$
Теперь $x1$ , $x2$ , ..., $xn$ , $z$ , $b$ ряд подходит под условие и минимальное неиспользованное число теперь больше, поэтому найдется момент для любого числа, когда мы его добавим в наш ряд.

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

Задача 18#83147

Существует ли такое целое $n,$ кратное 4, что $n +4$ кратно 9, а $n+ 9$ кратно 25?

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

Подсказка

Попробуем применить Китайскую теорему об остатках. Что для этого нужно понять?

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

Нас спрашивают существует ли такое $n$ , что $n≡ 0$ (mod $4$ ); $n ≡− 4$ (mod $9$ ); $N ≡− 9$ (mod $25$ ). По КТО такой $x$ существует, так как 4, 9, 25 попарно взаимно просты.

Ответ: да

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

Задача 19#49060

Вася хочет найти все целые числа $a$ такие, что выражение

3 5 10n − 3n +7an

делится на $15$ для всех целых $n$ . Какие остатки может давать число $a$ при делении на $15?$ Укажите все возможные ответы или докажите, что таких целых чисел $a$ нет.

Источники: ОММО-2018, номер 3, (см. olympiads.mccme.ru)

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

Подсказка 1

В задачах на делимость мы что делаем в первую очередь? Конечно, сравниваем выражение по модулю того числа, на которое оно должно делиться. Но 15 - число составное, с ним работать будет неудобно. Давайте перейдём для начала к сравнениям по модулю 3 и 5. Потом мы справимся найти остаток и по модулю 15. Нужно упростить наше выражение. Какую теорему можно вспомнить, чтобы это сделать?

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

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

По малой теореме Ферма $3 n ≡3 n$ и $5 n ≡5 n.$

Теперь взглянем на исходное выражение по модулю $3 :$

10n− 3n+7an ≡3 7n(a+ 1)≡3 0 =⇒ a≡3 −1

Теперь взглянем на исходное выражение по модулю $5 :$

10n3− 3n5+ 7an ≡5 − 3n +7an ≡5 7n+ 7an≡5 7n(a+ 1) =⇒ a ≡5 − 1

Итак, $a ≡3 − 1$ и $a ≡5 − 1$ . По Китайской теореме об остатках решение такой системы сравнений по модулю, равном произведению модулей, существует и единственно, легко находим, что это $a ≡15−1 ≡1514.$

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

Подставим $n =1$ и получим, что если такое $a$ и существует, то $7+ 7a$ должно делится на $15,$ то есть $a$ должно давать остаток $14$ при делении на $15.$ Осталось проверить, что если $a ≡ 14 15$ , то указанное выражение делится на $15$ для любого натурального $n.$

Докажем это утверждение индукцией по $n$ (для $n= 0$ делимость очевидна, для отрицательных $n$ доказывается аналогично или сводится к случаю положительного $n$ заменой $n → −n)$ . Если $n= 1$ , утверждение уже проверено. Предположим теперь, что мы уже доказали, что $10n3− 3n5+ 7an$ делится на $15$ и докажем, что $10(n +1)3− 3(n+ 1)5+ 7a(n +1)$ также делится на $15.$ Посмотрим на разность этих двух выражений:

10((n+ 1)3− n3)− 3((n +1)5− n5)+ 7a((n+ 1)− n)= 10(3n2 +3n+ 1)− 3(5n4+ 10n3+10n2+ 5n +1)+ 7a.

После раскрытия скобок все слагаемые в правой части, кроме $10− 3+ 7a$ , делятся на $15,$ но $10− 3+7a$ делится на $15,$ поскольку $a ≡14 15$

Ответ:

$14$

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

Задача 20#80049

Найдите количество натуральных чисел $k,$ не превосходящих $445000$ и таких, что $k2− 1$ делится нацело на $445$ .

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

$445= 5⋅89$ . $k2 − 1= (k− 1)(k+ 1)..5..89 . .$ . Числа 5 и 89 простые, поэтому существует 4 случая:

$.. .. ∙ k− 1 .5.89$

$.. .. ∙ k+1 .5.89$

$.. .. ∙ k− 1 .5 k+ 1.89$

$.. .. ∙ k+1 .5 k− 1.89$

Для каждого такого случая существует ровно одно решение по модулю $5 ⋅89 =445$ или другими словами от 1 до 445 (по КТО), так как если бы существовала $k1$ и $k2$ для, например, третьего случая, то $.. .. k1− k2.5.89$ и значит $− 444≤ k1− k2 ≤444$ и делится на 445, то есть $k1− k2 =0$ . Решение существует по КТО или его можно найти руками.

Отсюда все числа от 1 до 445000 разбиваются на группы по 445 в каждой, из которых есть ровно 4 решения.

Ответ: 4000

Предыдущий раздел

Следующий раздел