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

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

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

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

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

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

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

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

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

Задача 1#83138

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

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

Подсказка 1

Попробуем доказать по индукции, что a^p - a делится на р. База a=1 очевидна. Как сделать переход от а к а+1?

Подсказка 2

Что мы можем сказать про делимость на p для биномиальных коэффициентов в выражении (а+1)^p?

Подсказка 3

p!/(k!(p-k)!) делится на р для всех k кроме 0 и р, поскольку числитель делится на р, а знаменатель - нет. Что тогда останется, если смотреть на выражение по модулю 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,$ чтд.

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

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

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

Задача 2#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?$

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

Подсказка 1

Покажем, что таких перестановок не существует (иначе их количество считать сложно, потому что мы не понимаем как устроены остатки произвольных чисел, по произвольному модулю). Остается надеяться, что мы сможем найти какое-либо противоречие, смотря на те степени, с которыми мы умеем работать.

Подсказка 2

Одним из таких является модуль p-1. Ясно, что существует число r такое, что a_r=p-1. Чему равно r^{a_r}?

Подсказка 3

По малой теореме Ферма r^{a_r}=r^{p-1} дает остаток 1 по модулю p. Чему может быть равно r?

Подсказка 4

Назовем S множество остатков чисел i^{a_i} для всех i от 1 до n-1. Предположим, что r не равно 1, но тогда 1^{a_1} сравнимо 1 и тогда в S нашлось сразу 2 единички. Теперь давайте посмотрим на то, чему может быть равен остаток числа (p-1)^{p-1}.

Подсказка 5

(p-1)^{a_{p-1}} сравнимо с (-1)^{a_{p-1}}, следовательно остаток равен числу 1 или -1. Первое из них уже занято, следовательно, остаток равен -1. Что это говорит о числе a_{p-1}?

Подсказка 6

Оно нечетное. Теперь мы поняли, что остатки 1 и -1 соответствуют числам 1 и p-1 в S. Если бы нам удалось найти четную степень, по которому все числа давали остатки равные 1 или -1, то мы бы нашли противоречие. Что это за остаток?

Подсказка 7

Это (p-1)/2. Докажите, что для любого a, не кратного p, число a^{(p-1)/2} сравнимо с 1 или -1.

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

Покажем, что таких перестановок не существует. Предположим противное. Тогда множество $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),$ тем самым получено противоречие.

Ответ:

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

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

Задача 3#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ᵖ⁻¹ ≡ 1 (mod p) в нужные степени, и, совместив два сравнения, получите искомое.

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

Мы знаем сравнение из пункта a, тогда хочется, чтобы 21240913 было равно φ(N) / 2 + 1. Давайте предположим это и найдём такие p и q, нужно только решить систему от двух переменных.

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

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)$

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

Задача 4#96952

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

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

Подсказка 1

Чтобы доказать, что одно из чисел делится на простое число 17, давайте покажем, что произведение данных чисел делится на 17.

Подсказка 2

Чему будет равно произведение всех этих чисел? Как нам это посчитать?

Подсказка 3

Давайте свернём произведение чисел в разность квадратов. Тогда какое число получится в итоге?

Подсказка 4

Получится (а¹⁶-1). Осталось лишь воспользоваться малой теоремой Ферма!

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

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

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

Задача 5#97582

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

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

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

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

Подсказка 1

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

Подсказка 2

Можно ли здесь применить малую теорему Ферма?

Подсказка 3

По малой теореме Ферма a^(p-1) ≡ 1 (mod p). Аналогично, (a^(p-1))^k ≡ 1 (mod p).

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

Заметим, что $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$

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

Задача 6#97583

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

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

Подсказка 1

561 не является простым числом, а как можно доказать делимость, зная разложение на простые множители?

Подсказка 2

Заметим, что 561 = 3*11*17. Достаточно доказать делимость a⁵⁶¹ - 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.$

Курсы

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

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

Задача 7#97584

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

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

Подсказка 1

Если произведение a*b делится на простое p, то что можно сказать про делимость на р по отдельности?

Подсказка 2

Или а делится на р, или b делится на р. Как можно применить такое свойство делимости произведения в задаче?

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

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

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

Задача 8#97585

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

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

Подсказка 1

Какой способ позволяет нам доказывать делимость на произведение?

Подсказка 2

Достаточно доказать делимость отдельно на p и на q.

Подсказка 3

Что будет, если рассмотреть выражение по модулю р?

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

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

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

Задача 9#68879

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

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

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

Подсказка 1

Сложно анализировать число только из единиц, т.к. сложно разобрать даже его делители...тогда было бы по хорошему его как-то преобразовать в более приятный вид. И подумаем над вопросом: "А откуда тут вообще 41? Почему не 42, например?"

Подсказка 2

Число, состоящее из единиц, можно записать как (10^n - 1)/9. А использовать 41 хочется только как простое число... Выходит, что (10^n - 1)/9 должно делиться на 41. Когда это возможно?

Подсказка 3

Когда 10^n - 1 делится на 41. Хмм, 41 простое... Какая известная теорема может помочь нам в нахождении хотя бы одного n, удовлетворяющему предыдущему предложению?

Подсказка 4

Малая теорема Ферма утверждает, что при n = 40 10^40 - 1 делится на 41. Теперь хочется как-то найти k из условия... а на что должно делиться n, чтобы 10^n - 1 делилось на 41? Мы не можем найти все такие случаи, но может попробовать найти хотя бы одного такое k и доказать, что утверждение работает в обе стороны.

Подсказка 5

Рассмотрим все такие d, что 10^d - 1 делится на 41 и выберем среди них наименьшее m. Докажем, что если n делится на m, то 10^n - 1 делится на 10^m - 1, а, значит, и на 41. Если это получится, то у нас найдено k, но условие "тогда и только тогда" пока не доказано. Теперь попробуем доказать, что если 10^n - 1 кратно 41, то n кратно m.

Подсказка 6

Мы взяли m наименьшим, т.к. обычно это помогает в поиске противоречий. Для того чтобы доказать утверждение из подсказки 5, попробуем найти НОД(10^n - 1, 10^m - 1).

Подсказка 7

В процессе поиска c помощью алгоритма Евклида можно заметить, что у нас в конце концов появится 10^(НОД(m, n)) - 1. Предположим, что n не делится на m, тогда НОД(n, m) < m. Осталось лишь найти противоречие с тем, что m - наименьшее взятое число из набора.

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

Заметим, что

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

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

Задача 10#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.$

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

Задача 11#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.$

Интенсивы

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

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

Задача 12#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.$

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

Задача 13#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.$ Что и требовалось.

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

Задача 14#90967

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

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

Подсказка 1

Вообще не понятно, как доказывать простоту числа. Может, мы сможем придумать конкретное простое, на которое поделится данное выражение?

Подсказка 2

Малая теорема Ферма позволяет легко находить остаток по простому модулю. Может, стоит использовать какое-то простое, остаток по которому можно будет найти через МТФ?

Подсказка 3

Достаточно рассмотреть число 31.

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

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

Ответ:

нет

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

Задача 15#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.$ Что и требовалось.

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

Задача 16#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$ нет

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

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

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

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

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

Задача 18#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,$ пришли к противоречию.

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

Задача 19#90979

Пусть $a ,...,a 1 p$ — $p$ ( $p> 2$ – простое число) подряд идущих чётных чисел. Докажите, что:

(a) существует некоторый член последовательности $am,$ делящийся на $p;$

(b) существует некоторый член $ak,$ такой что $ak+ a1⋅a2⋅...ap$ делится на $p;$

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

(a) Поделим все числа на $2$ и получим $p$ последовательных натуральных чисел, среди которых, очевидно, найдётся число, кратное $p.$

(b) В прошлом пункте мы поняли, что в последовательности есть член, кратный $p.$ Следовательно, произведение всех чисел также кратно $p.$ Тогда в качестве $ak$ можно взять тот самый член, который делится на $p.$

(c) Ясно, что нужно взять тот единственный член, который делится на $p,$ в противном случае выражение $ak+ a1⋅a2⋅...ap$ не поделится даже на $p.$

Обозначим числа следующим образом: $2t,2(t+1),...,2(t+p− 1).$ Пусть $2(t+ k− 1)$ кратно $p.$ Следовательно,

p p−1 ak+ a1 ⋅a2⋅...ap = 2(t+k− 1)+2 t(t+ 1)...(t+ p− 1)=2(t+k − 1)(1+ 2 t(t+1)...(t+k − 1)...(t+p− 1))

Первая скобка делится на $p.$ Покажем, что то же самое можно сказать про вторую. Заметим, что произведение $t(t+ 1)...(t+ k− 1)...(t+ p− 1)$ представляет из себя произведение всех остатков при делении на $p,$ кроме $0.$ Значит, оно сравнимо с $(p− 1)!$ по модулю $p.$ Также подметим, что МТФ позволяет заменить $2p−1$ на $1.$ Следовательно, вторая скобка сравнима с $1+(p− 1)!$ по модулю $p.$ По теореме Вильсона это выражение кратно $p,$ что и требовалось.

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

Задача 20#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.$ Посмотрим на разность этих двух выражений: