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

Малая теорема Ферма

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

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

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

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

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

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

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

Задача 1#118946

Докажите, что для любого простого $p> 3$ существует бесконечно много натуральных $n$ таких, что $2n+ 3n +6n − 1$ делится на $p.$

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

По малой теореме Ферма: если $a⁄≡ 0⇒ ap−1 ≡ 1. p p$ Тогда $2n+p−1 ≡ 2n,3n+p−1 ≡ 3n,6n+p−1 ≡ 6n, p p p$ то есть

n n n n+p−1 n+p− 1 n+p−1 2 +3 + 6 − 1≡p 2 + 3 +6 − 1

значит, надо найти одно $n$ такое, что $2n+ 3n +6n − 1≡p 0.$

Рассмотрим $n= −1,$ пусть оно и ненатуральное, последующие будут натуральными:

−1 −1 −1 3+-2+1- 2 + 3 +6 − 1≡p 6 − 1≡p 0

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

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

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

Задача 2#83138

Малая теорема Ферма. Для любого простого $p$ и взаимно простого с $p$ числа $a$ верно, что $ap−1 ≡ 1$ (mod $p$ )

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

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

Давайте возьмем две разные ПрСВ по одному модулю $p$ и перемножим в каждой все числа. Так как наборы остатков одинаковые, то получившиеся произведения будут сравнимы по модулю $p$ .

Тогда рассмотрим две такие ПрСВ: [1, 2, ..., $p− 1$ ] и [ $a$ , $2a$ , ..., $(p− 1)a$ ] (То, что написано справа - это $a⋅$ ПрСВ) и перемножим в каждой все числа.

Получаем, что $1⋅2⋅....⋅(p − 1)≡ a⋅2a⋅....⋅(p− 1)a$ (mod $p$ ) или $p−1 (p− 1)!≡ (p− 1)!a$ (mod $p$ ). Теперь перепишем это через разность, то есть $p−1 p−1 a (p− 1)!− (p− 1)!= (a − 1)(p− 1)!$ делится на $p$ . Из-за того, что НОД( $(p− 1)!$ , $p$ ) = 1 следует, что $p−1 a − 1$ делится на $p$ или $ap−1 ≡ 1$ (mod $p$ )

_________________________________________________________________________________________________________________________________________________________________________________

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

Зафиксируем простое число $p.$ Проверим базу индукции: $a= 1.$ Тогда действительно $1p − 1 =0$ — делится на $p.$ Пусть $ap− a$ делится на $p.$ Докажем, что $(a+1)p− (a+ 1).$ делится на $p.$ Докажем, что для $0 <k < p$ число $Ckp$ делится на $p.$ Действительно, $Ckp = k!(pp−!k)!.$ В каждом из факториалов $k!$ и $(p− k)!$ все сомножители меньше $p,$ а потому взаимно просты с $p.$ Тогда, поскольку $p!$ делится на $p,$ то и $Ckp$ делится на $p.$ Благодаря этому утверждению и биному Ньютона, получаем

(a+ 1)p =∑p Ckak ≡ ap+ 1 k=0 p p

По предположению индукции $ap+ 1≡p a+ 1,$ чтд.

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

Задача 3#89727

Пусть $p =4k+ 1$ — простое число. Сколько существует перестановок $a,a ,...,a 1 2 p−1$ чисел $1,2,3,...,p− 1$ таких, что числа $a1 a2 ap−1 1 ,2 ,...,(p− 1)$ дают различные остатки по модулю $p?$

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

Покажем, что таких перестановок не существует. Предположим противное. Тогда множество $S = {1a1,...,(p − 1)ap−1}$ образуют приведённую систему вычетов по модулю $p.$

$1.$ Найдем индекс $l$ такой, что $al = p− 1.$ Тогда, по малой теореме Ферма, для любого $a$ верно, что

a l l ≡1 (mod p)

Если $l⁄=1,$ то, поскольку $1a1 ≡ 1 (mod p),$ в $S$ встретится две $1,$ что невозможно, следовательно, $a = p− 1. 1$

$2.$ Как следствие, $(p− 1)ap−1$ не может быть сравнимо с $1,$ а поскольку

ap−1 ap−1 (p− 1) ≡ (− 1) (mod p)

верно, что $(p − 1)ap−1 ≡ −1 (mod p)$ и $ap−1$ нечетно.

$3.$ Найдем индекс $r$ такой, что $ar = p−1. 2$ Во-первых, заметим, что $rar$ не может быть сравнимо с $− 1,$ поскольку $ar$ четно и не совпадает c $ap−1.$ Во-вторых, $r$ не может быть сравнимо с $1,$ поскольку $a1 = p− 1.$ Наконец, как известно, $rar ≡ ±1 (mod p),$ тем самым получено противоречие.

Ответ:

таких перестановок не существует

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

Задача 4#90279

В криптосистеме RSA (знания алгоритма шифрования не требуется для решения задачи) элементы надёжности определяются несколькими параметрами. В частности, выбором числа $N =p⋅q$ , где $p,q$ — различные нечётные простые числа, и значением

φ(N)= (p− 1)⋅(q− 1)

Известна следующая теорема (малая теорема Ферма): если $p$ — простое число, $a$ — целое число, не делящееся на $p$ , то

p−1 a ≡1(modp)

Используя это:

a) докажите, что

φ(N2)+1 x ≡x(modN )

для всех $x ∈{1,2,...,N − 1}$ .

b) найдите $p$ и $q$ , если известно, что

N =42494861 и x21240913 ≡x(modN )

для всех $x ∈{1,2,...,N − 1}.$

Источники: Верченко - 2024, 11.4 (см. ikb.mtuci.ru)

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

a) из условия задачи и равенства $ap−1 ≡1 (modp)$ следует

k(p−1)+1 a ≡ a (modp)

для любого натурального $k$ . Тогда при $k = q−1- 2$ получим

φ(N2-)+1 a ≡a (modp)

Аналогично

aφ(N2-)+1 ≡a (modq)

Так как $p,q$ - простые числа, то из этих полученных выше равенств следует

aφ(N2)+1 ≡ a (modN )

b) из доказанного в пункте (а) получим $φ(2N)+ 1= 21240913,$ а отсюда систему

{ p⋅q = 42494861 (p− 1)⋅(q− 1) =(21240913− 1)⋅2

Решением в нечётных простых числах является неупорядоченная пара $(6469,6569).$

Ответ:

b) $(6469,6569)$

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

Задача 5#96952

Пусть $a$ — натуральное число, не делящееся на $17.$ Докажите, что одно из чисел $a8+ 1,$ $a4 +1,$ $a2+ 1,$ $a+1,$ $a − 1$ делится на $17.$

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

По малой теореме Ферма $a16− 1$ делится на $17,$ то есть

16 8 8 8 4 4 a − 1= (a +1)(a − 1)= (a + 1)(a +1)(a − 1)=

8 4 2 2 8 4 2 =(a + 1)(a +1)(a + 1)(a − 1)=(a + 1)(a +1)(a + 1)(a+ 1)(a− 1)

делится на $17,$ в силу простоты, одна из скобок должна делиться на $17.$

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

Задача 6#97582

Найдите остаток от деления

(a) $2100$ на $101;$

(b) $7102$ на $101;$

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

Заметим, что $101$ — простое число. В пункте (a) по малой теореме Ферма $2100 ≡ 1. 101$ Для пункта (b) по малой теореме Ферма сначала получим, что $101 7 ≡101 7.$ Тогда $102 7 ≡101 49.$ Чтобы решить пункт (c), сначала отметим, что из малой теоремы Ферма следует, что $28 8 ≡29 1.$ Заметим, что $900= 28⋅32 +4.$ Тогда $900 32⋅28+4 4 28 32 8 =8 =8 ⋅(8 ) .$ Таким образом, имеем

4 2832 4 8 ⋅(8 ) ≡29 8 ≡29 7

Ответ:

(a) $1;$ (b) $49;$ (c) $7$

Курсы

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

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

Задача 7#97583

Число Кармайкла. Докажите, что $a561− a$ делится на $561$ для любого целого $a.$

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

Разложим $561$ на множители: $561= 3⋅11⋅17.$ Необходимо и достаточно доказать делимость $a561 − a$ на $3,7,11.$ Делимость на $3:$ по малой теореме Ферма $2 a ≡3 1,$ но тогда $561 2 280 a = (a ) ⋅a≡3 a.$ Делимость на $11 :$ по малой теореме Ферма $10 a ≡11 1.$ Тогда аналогичным образом случаю делимости на $3$ легко получить, что $561 a ≡11 a.$ Теперь снова по малой теореме Ферма получаем, что $16 a ≡17 1.$ Аналогично случаю делимости на $3$ легко проверить, что $561 a ≡17 a,$ так как $561 1635 a =(a ) ⋅a.$

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

Задача 8#97584

Натуральное число $n$ не делится на $17.$ Докажите, что либо $n8+1,$ либо $n8− 1$ делится на $17.$

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

По малой теореме Ферма $n16− 1$ делится на $17.$ Поскольку $n16− 1 =(n8− 1)(n8+ 1)$ и в силу простоты числа $17,$ получаем, что одно из чисел $8 n − 1$ или $8 n +1$ делится на $17.$

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

Задача 9#97585

Пусть $p$ и $q$ — различные простые числа. Докажите, что $pq+ qp ≡ p+q (mod pq).$

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

Докажем, что $pq+ qp− p − q$ делится на $p$ и $q,$ тогда задача будет решена. Поскольку $pq− p≡ 0 p$ и в силу малой теоремы Ферма $p q − q ≡p 0,$ имеем $q p p− p+ q − q ≡p 0.$ Аналогично доказывается делимость на $q.$

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

Задача 10#68879

Натуральные числа вида $11 ...1 ◟ ◝◜n-◞$ (десятичная запись состоит из $n$ единиц) будем обозначать $R . n$ Докажите, что существует такое натуральное число $k,$ что $Rn$ делится на 41 тогда и только тогда, когда $n$ делится на $k.$

Источники: Иннополис-2023, 10-12 (см. dovuz.innopolis.university)

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

Заметим, что

10n−-1 Rn = 9

Так как числа $9$ и $41$ взаимно просты, то $Rn$ кратно $41$ тогда и только тогда, когда $n 10 − 1$ кратно $41.$ Поскольку $41$ — простое, согласно малой теореме Ферма

1040− 1 ... 41

Рассмотрим все натуральные $d,$ при которых $10d − 1$ кратно $41;$ наименьшее такое $d$ обозначим за $m.$

Если $n$ делится на $m,$ то

10n− 1= 10tm − 1= (10m − 1)(10(t− 1)m +10(t−2)m + ⋅⋅⋅+10m +1)

Значит, $n 10 − 1$ делится на $m 10 − 1,$ а значит, и на $41,$ что и требовалось.

В обратную сторону: если $n 10 − 1$ кратно $41,$ то рассмотрим $n m НО Д(10 − 1,10 − 1).$ Воспользуемся алгоритмом Евклида, т.е. свойством НОД

НО Д(a,b)= НОД(a− kb,b),где a,b,k∈ ℕ

Теперь

НОД(10n− 1,10m− 1)= НОД(10n− 1− 10n−m(10m− 1),10m− 1)

НОД(10n− 1− 10n+ 10n− m,10m − 1)= НО Д(10n−m − 1,10m− 1)

Повторяя эти действия, убеждаемся, что в конце получается число $НОД(n,m) 10 − 1.$

Если $n$ не делится на $m,$ то

НОД(n,m)< m

Значит, $m$ — не минимальное натуральное число, при котором $m 10 − 1$ кратно $41$ — противоречие. Значит, $n$ кратно $m,$ что и требовалось доказать.

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

Задача 11#75628

Пусть $p$ — простое число. Доказать, что для любого целого $m,$ не кратного $p − 1,$ существует $n⁄≡ 0 (mod p)$ такое, что $m n ⁄≡ 1 (mod p).$

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

Рассмотрим сначала $1≤ m ≤p − 2.$ Тогда сравнение $xm − 1≡ 0$ имеет не более $m ≤p − 2$ решений, а, значит, найдется $x ⁄≡ 0, 0$ которое решением не является. Для $m ≥ p$ заметим, что $m r x ≡ x ,$ где $r$ — остаток $m$ от деления на $(p − 1).$ Но тогда $r< p− 1,$ и, по утверждению выше, мы найдем $x0,$ не являющееся решением сравнения $r x − 1 ≡0.$ Тогда $x0$ так же не является решением сравнения $m x − 1 ≡0.$

Интенсивы

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

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

Задача 12#76065

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

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

Без ограничения общности будем считать, что $p <q <2p.p,q$ взаимно просты, по малой теореме Ферма $pq−1 ≡ 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.$ У числа $2 pr ≤p$ — наибольший простой делитель $p,$ а у числа $2 pr− 1 ≤p − 1$ наибольший простой делитель равен $q$ ( $p,q$ — наибольшие простые делители, иначе бы числа $pr,pr− 1$ были бы больше $2 2 p ,q$ соответственно).

Если же $q > r> p,$ то возьмем последовательные натуральные числа $p(q− r),p(q− r)+1.$ Тогда у числа $2 p(q − r)< p(2p− r)<p(2p− p)= p$ — опять-таки $p$ наибольший простой делитель, а у числа $p(q− r)+ 1< q⋅q+ 1$ наибольший простой делитель равен $q,$ иначе бы $2 2 q + 1> p(q− r)+1 ≥q⋅(q+ 1)= q + q,$ то есть $1 >q,$ что не выполняется.

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

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

Задача 13#119349

Петя выбрал некоторое простое число $p< 1010$ и натуральное число $b.$ Число $b$ он написал на доску и закрыл его карточкой. Первым ходом робот может приписать справа к карточке любую ненулевую цифру и спросить Петю, делится ли написанное на доске число на $p$ (если убрать с числа $b$ карточку). Каждым следующим ходом робот также может приписывать справа любую ненулевую цифру и задавать тот же вопрос Пете. Всегда ли робот сможет определить число $p$ через некоторое количество ходов?

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

Сначала проверим, не может ли $p$ равняться $2$ или $5.$ Припишем к карточке цифру $2,$ если Петя сказал, что не делится, то $p ⁄=2.$ Если же Петя сказал, что делится, повторим эту же операцию ещё раз. Если на доске было написано число $n,$ делящееся на $p,$ то следующим шагом будет написано число $10n+ 2,$ если теперь Петя опять ответит положительно, то $2$ делится на $p,$ откуда $p= 2,$ иначе $p ⁄=2.$ Абсолютно аналогично поступаем с $5$ (только приписывать будем цифру $5).$

Далее считаем, что $p ⁄=2$ и $p ⁄=5.$ Обозначим все простые, меньшие $10 10 ,$ кроме $5$ и $2,$ через $p1,p2,...,pm.$ Рассмотрим

s= (p1 − 1)(p2− 1)...(pm − 1)

По малой теореме Ферма $s 10 − 1$ делится на каждое из чисел $p1,...,pm,$ в частности на $p.$ Будем приписывать справа к числу $s− 1$ раз цифру $9,$ а потом цифру $8.$ Пусть на доске было записано число $n.$ Тогда после всех таких операций будет написано число

s 10s− 1 10 n+ 9--9---− 1 ≡a − 1 (mod p)

То есть мы умеем уменьшать остаток числа при делении на $p$ на $1.$ Рано или поздно мы получим положительный ответ. Далее опять будем уменьшать остаток на $1,$ пока второй раз не получим положительный ответ. Тогда между двумя положительными ответами мы сделали ровно $p$ шагов, откуда найдем наше $p.$

Ответ:

Всегда

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

Задача 14#90962

Найдите остаток от деления

(a) $900 8$ на $29;$

(b) $60 50 2 +6$ на $143.$

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

(a) По МТФ $28 8 ≡ 1 (mod 29).$ Следовательно, $28⋅32 896 8 =8 ≡ 1 (mod 29).$ С помощью последнего сравнения нетрудно посчитать (четыре раза умножить остаток на $8),$ что $900 8 ≡7 (mod 29).$

(b) Заметим, что $143= 11⋅13.$ Посчитаем сначала остаток при делении на $11,$ а потом — при делении на $13.$ По МТФ $10 10 2 ≡6 ≡ 1 (mod 11),$ но тогда $60 50 2 + 6 ≡ 2 (mod 11).$ Также по МТФ $12 12 2 ≡ 6 ≡ 1 (mod 13).$ Отсюда имеем $60 2 ≡ 1 (mod 13)$ и $48 6 ≡1 (mod 13).$ Из последнего сравнения нетрудно посчитать, что $50 6 ≡10 (mod 13).$ Значит, $60 50 2 + 6 ≡ 11 (mod 13).$

Таким образом, число $60 50 2 + 6$ имеет вид $11m + 2$ и $13n +11$ для некоторых целых $m$ и $n.$ То есть $11m + 2= 13n +11,$ что равносильно $11m =13n+ 9.$ Видно, что для выполнения равенства необходимо, чтобы $m$ давало остаток $2$ при делении на $13.$ Значит, $m = 13r+ 2,$ откуда $260+ 650 =143r+24.$ Заметим, что мы нашли остаток при делении на $143.$

Ответ:

(a) $7;$

(b) $24.$

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

Задача 15#90965

Известно, что $a12+b12+ c12+ d12+ e12 +f12$ делится на $13.$ Докажите, что $abcdef$ делится на $136.$

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

МТФ утверждает, что если $x$ не делится на $13,$ то $x12 ≡ 1 (mod 13).$ Предположим, что $i$ переменных не делятся на $13,$ а остальные делятся. Следовательно, сумма их двенадцатых степеней сравнима с $i$ по модулю $13.$ Значит, по условию $i≡ 0 (mod 13).$ Заметим, что $0 ≤i< 6.$ Таким образом, $i= 0,$ то есть каждая из шести переменных делится на $13,$ тогда их произведение должно делиться на $6 13.$ Что и требовалось.

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

Задача 16#90967

Является ли простым число $30239+ 23930?$

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

Заметим, что это число делится на $31.$ Действительно, $30239 ≡(−1)239 ≡ −1 (mod 31)$ и по МТФ $23930 ≡1 (mod 31).$ Также заметим, что это число, очевидно, больше чем $31.$ Следовательно, оно составное.

Ответ:

нет

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

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

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

Задача 17#90970

Докажите, что если $p$ — простое число и $p >2,$ то $7p− 5p− 2$ делится на $6p.$

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

По МТФ $7p− 5p− 2≡ 7− 5− 2= 0 (mod p),$ значит, делимость на $p$ доказана. Число $7p− 5p$ чётно как разность нечётных чисел, откуда $p p 7 − 5 − 2$ чётно.

Осталось доказать делимость на $3.$ Заметим, что

p p p p 7 − 5 − 2 ≡1 − 2 − 2= −2 − 1 (mod 3)

Посмотрим на остатки степеней двойки при делении на $3:21 ≡2,22 ≡ 1,23 ≡ 2$ и так дальше. То есть двойка в нечётной степени сравнима с $2$ по модулю $3.$ Следовательно, $2p+1$ кратно $3.$ Что и требовалось.

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

Задача 18#90974

Найдите все такие натуральные числа $p,$ что $p$ и $p6+ 6$ — простые.

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

Заметим, что если $p$ не делится на $7,$ то по МТФ $p6+ 6$ делится на $7.$ Следовательно, в этом случае $p6 +6= 7,$ откуда $p= 1,$ противоречие. Значит, $p$ делится на $7,$ то есть предположительно $p= 7.$ Но заметим, что тогда

6 6 7 + 6≡ 2+ 1≡ 65≡ 0 (mod 5)

Получается таких $p$ не существует.

Ответ:

таких $p$ нет

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

Задача 19#90975

Найдите все такие простые числа $p,$ что $5p2 − 1$ делится на $p?$

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

Ясно, что остатки степеней пятерки по модулю $p$ зацикливаются (потому что количество остатков при делении на $p$ конечно), притом в цикле точно встретится остаток $1,$ так как по МТФ $p−1 5 ≡ 1 (mod p)$ (очевидно, что $p =5$ не походит к условию). Значит, существует наименьшее натуральное $k$ такое, что $k 5 ≡ 1 (mod p)$ (нетрудно понять, что $k 5$ является последней степенью пятёрки в самом первом цикле остатков по модулю $p$ ). Значит, если $t 5 ≡1 (mod p),$ то $k$ делит $t.$

Следовательно, $k$ делит $2 p.$ Если $k= 1,$ то $5− 1 =4$ кратно $p,$ то есть $p= 2.$ Если $k= p$ или $2 p,$ то $k >p − 1,$ но очевидно, что $k ≤p− 1$ в силу МТФ.

Ответ:

$2$

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

Задача 20#90978

Докажите, что ни при каком целом $k$ число $k2+k +1$ не делится на $101.$

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

Предположим, что при некоторых $k$ делимость реализуется. Тогда $k3− 1= (k− 1)(k2+ k+ 1)$ также делится на $101.$ Следовательно, $99 100 99 100 k (k − 1)= k − k ≡k − 1 ≡0 (mod 101)$ (последний переход справедлив по МТФ). Значит, $k$ может давать только лишь остатки $0$ или $1$ при делении на $101,$ но в этих случаях $2 k +k +1$ не поделится на $101,$ пришли к противоречию.