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

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

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

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

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

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

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

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

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

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

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

Источники: Росатом - 2020, 11.4 (см. olymp.mephi.ru)

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

Подсказка 1

Так-с, кажется эта задача на вероятности. А точно ли на вероятности? Понятно, что всего возможных исходов ровно 1000. Давайте тогда будем считать благоприятные исходы, а результат потом поделим на 1000.

Подсказка 2

Кажется, что данное условие про делимость мы можем записать в виде уравнения. Немного порешав уравнение в целых числах, мы поймём какие x нам будут подходить. Осталось посчитать количество подходящих чисел!

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

Можно считать, что мы получаем на столе равновероятно любое число от $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$

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

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

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

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

Докажите, что найдутся 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$ подойдет.

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

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

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

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

Подсказка 1

Не будем сразу строить всю перестановку. Будем поэтапно добавлять все числа 1, 2, 3, … в последовательность, при необходимости оставляя места для будущих вставок. Подумайте, как при таком подходе поддерживать требуемую делимость на каждом шаге.

Подсказка 2

Попробуем начать строить последовательность с самого начала и подумаем, как можно поддерживать условие делимости на каждом шаге. Что произойдёт, если рассмотреть добавление сразу двух чисел подряд?

Подсказка 3

Для аккуратных рассуждений введём обозначения: пусть после n шагов сумма равна S, и мы хотим добавить числа k и m. Как можно записать условия делимости на n+1 и n+2 в виде сравнения? Какие значения n обращают это сравнение в верное?

Подсказка 4

Система сравнений для k и m решается благодаря китайской теореме об остатках. Проверим, почему решение всегда можно найти, и как при этом можно гарантировать, что все натуральные числа в итоге будут использованы.

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

Начнём с числа $1.$ Пусть после некоторого шага поставлено первые $n$ чисел, их сумма равна $S,$ и среди непоставленных чисел минимальное равно $m.$ Добавим ещё два числа: сначала некоторое $k,$ затем $m.$ Хотим добиться

({ S+ k≡ 0 (mod n+1), ( S+ k+ m ≡0 (mod n+ 2).

Это равносильно системе

( {k≡ −S (mod n +1), . (k≡ −S − m (mod n+ 2).

Так как $Н ОД(n+ 1,n+ 2)=1,$ то по китайской теореме об остатках такая $k$ существует и задаётся единственным классом вычетов по модулю $(n +1)(n +2).$ Следовательно, подходящих $k$ бесконечно много, и мы можем выбрать представителя этого класса настолько большим, чтобы он ещё не встречался в последовательности и не равнялся $m.$

После добавления $k$ сумма первых $n+ 1$ членов делится на $n +1,$ а после последующего добавления $m$ сумма первых $n+ 2$ членов делится на $n+ 2.$ Число $m$ по построению минимально отсутствующее, значит, в последовательности встретится каждое натуральное число и никакое не встретится дважды.

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

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

Существует ли такое целое $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 попарно взаимно просты.

Ответ: да

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

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

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

3 5 10n − 3n +7an

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

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

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

Подсказка 1

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

Подсказка 2

Верно, есть малая теорема Ферма (она утверждает, что n^p сравнимо с n по модулю p), к тому же здесь удачно совпали степени. Попробуйте упростить теперь наше выражение по модулю 3 и 5. Как же можно в лоб найти остаток a?

Подсказка 3

Ага, мы нашли, что остаток при делении на 3 и 5 число -1. Теперь можно просто перебрать числа дающие остаток -1 по модулю 3, чтобы какой-то из них совпал по модулю 5. Китайская теорема об остатках утверждает, что такое число существует и единственное. Несложным перебором получается ответ, победа!

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

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

По малой теореме Ферма $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$

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

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

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

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

Подсказка 1

Разность квадратов делится на составное число. Какие делимости на меньшие числа тогда можно рассмотреть?

Подсказка 2

Рассмотрим делимость на 89. (k-1)(k+1) делится на 89, что это может значить? Разберем случаи!

Подсказка 3

Ровно одна из скобок делится на 89. Пусть, например, k+1. Как тогда можно записаться k?

Подсказка 4

k = 89p + 88, p — целое. Отлично, с делимостью на 89 разобрались, но ведь нам нужна делимость на 445...

Подсказка 5

Получаем, что (89p + 87)(p+1) делится на 5. Тогда можно найти вид p ;) Аналогично нужно разобраться со случаем, когда на 89 делится другая скобка!

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

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

Разложив делимое и делитель на множители, получаем условие $.. (k− 1)(k +1).(5⋅89)$ . Значит, одно из чисел $(k +1)$ или $(k− 1)$ делится на 89 . Рассмотрим два случая.

a) $.. (k+ 1).89$ , т.е. $k= 89p+ 88,p∈ ℤ$ . Тогда получаем $.. .. (89p +87)(89p+ 89).(5⋅89) ⇐⇒ (89p+ 87)(p+ 1).5$ . Первый множитель делится на 5 при $p =5q+ 2,q ∈ℤ$ , а второй — при $p =5q+ 4,q ∈ℤ$ , откуда получаем, что $k= 445q +266,k =445q+ 444,q ∈ℤ$ .

б) $.. (k− 1).89$ , т.е. $k= 89p+ 1,p∈ ℤ$ . Тогда получаем $.. .. 89p(89p+ 2).(5⋅89) ⇐ ⇒ (89p+ 2)p.5$ . Первый множитель делится на 5 при $p =5q+ 2,q ∈ℤ$ , а второй — при $p= 5q,q ∈ℤ$ , откуда получаем, что $k= 445q +179$ , $k= 445q+ 1,q ∈ℤ$ .

Итак, условию задачи удовлетворяют числа, дающие остатки $266,444,179,1$ при делении на 445, то есть подходят каждые 4 из 445 подряд идущих чисел. Так как $445000= 445⋅1000$ , получаем $4 ⋅1000= 4000$ чисел.

_________________________________________________________________________________________________________________________________________________________________________________

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

$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$ (по КТО), так как если бы существовала $k1$ и $k2$ для, например, третьего случая, то $. k1− k2..(5⋅89),$ и значит, $− 444≤k1− k2 ≤ 444$ и делится на 445, то есть $k1− k2 = 0$ .

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

Ответ: 4000

Курсы

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

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

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

Найдите наименьшее натуральное число, дающее остаток 2 при делении на 3, остаток 3 при делении на 4, остаток 4 при делении на 5, остаток 5 при делении на 6 и остаток 6 при делении на 7.

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

Нам дано:
$x ≡2$ (mod 3);
$x ≡3$ (mod 4);
$x ≡4$ (mod 5);
$x ≡5$ (mod 6);
$x ≡5$ (mod 7)
Это можно переписать, как
$x ≡− 1$ (mod 3);
$x ≡− 1$ (mod 4);
$x ≡− 1$ (mod 5);
$x ≡− 1$ (mod 6);
$x ≡− 1$ (mod 7)
Тогда $x+ 1$ делится на 3, 4, 5, 6, 7 и на их НОК(3, 4, 5, 6, 7) = 420. Тогда минимальное подходящее $x$ равно 419.

Ответ: 419

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

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

Китайская теорема об остатках, частный случай Пусть есть два взаимно простых модуля $a$ и $b$ (НОД( $a$ , $b$ ) = 1) и есть два остатка $x$ и $y$ . Тогда существует такое число $N$ , что
$N ≡ x$ (mod $a$ );
$N ≡ y$ (mod $b$ ).

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

Давайте рассмотрим $b$ чисел, которые дают остаток $x$ при деление на $a$ .

x,a+ x,2a +x,...,(b− 1)a+ x

Если мы докажем, что тут все остатки разные по модулю, то среди них точно будет число с остатком $y$ по модулю $b$ , то есть мы хотим доказать, что наш набор чисел - это ПСВ по модулю $b$ (набор из $b$ чисел с разными остатками по модулю $b$ ).

Это так, потому что набор $x$ , $a+ x$ , $2a +x$ , ..., $(b− 1)a+ x$ можно получить из ПСВ $0,1,2,...,b− 1$ , если сначала домножить на $a$ (так можно делать, так как НОД( $a$ , $b$ ) = 1), а затем прибавив $x$ к каждому.

Что же делать, если у нас есть еще условие $N ≡z$ (mod $c$ ) и НОД( $a$ , $c$ ) = НОД( $b$ , $c$ ) = 1? Давайте тогда сначала найдем по только что доказанной теореме такое $H$ , что $H ≡ x$ (mod $a$ ); $H ≡ y$ (mod $b$ ). Так как НОД( $a$ , $c$ ) = НОД( $b$ , $c$ ) = 1, то и НОД( $ab$ , $c$ ) = 1, поэтому давайте еще раз используем КТО и найдем такое число $N ≡ H$ (mod $ab$ ) и $N ≡ z$ (mod $c$ ). Тогда $N − H$ делится и на $a$ , и на $b$ и
$N ≡ H ≡x$ (mod $a$ );
$N ≡ H ≡y$ (mod $b$ ),
$N ≡ z$ (mod $c$ )
то есть мы опять нашли подходящее $N$ .

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

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

Китайская теорема об остатках Пусть числа $m 1$ , $m 2$ , . . . , $m n$ попарно взаимно просты. Тогда для любых целых $a 1$ , $a 2$ , . . . , $a n$ найдется целое число $x$ такое, что $x ≡ai$ (mod $mi$ ) для всех $i$ . Более того, $x$ определен однозначно с точностью до прибавления кратного $M =m1m2...mn$ .

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

Давайте каждому числу от 1 до $m m ...m 1 2 n$ сопоставим набор из остатков по модулям $m 1$ , $m 2$ , . . . , $m n$ ( $α 1$ , $α 2$ , ..., $αn$ ).

Сколько максимум может существовать различных наборов остатков? Для $α1$ у нас $m1$ вариантов, для $α2$ у нас $m2$ вариантов и т. д., то есть всего $m1m2...mn$ остатков.

Могут ли у двух чисел совпадать наборы остатков? Пусть могут и у $X$ и $Y$ наборы остатков одинаковые. Тогда для любого $i$ $X − Y$ делится на $mi$ , то есть $X − Y$ делится на $m1m2...mn$ , так как числа попарно взаимно просты, но $X$ и $Y$ от 1 до $m1m2...mn$ . Противоречие, то есть все наборы разные.

Так как наборов у нас всего $m1m2...mn$ и все они разные, то каждый набор остатков встречается и ровно 1 раз.