Тема ТЕОРИЯ ЧИСЕЛ

Остатки и сравнения по модулю → .03 Малая теорема Ферма

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

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

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

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

Подтемы раздела теория чисел

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

Базовый аппарат сравнений по модулю

Выбор модуля для доказательства делимости / простоты / степени

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

Функция Эйлера и теорема Эйлера из ТЧ

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

Обратные остатки

Квадратичные вычеты

Показатели и первообразные корни

Лемма об уточнении показателя

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

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

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

Найдите все пары числел $(p,n),$ где $p−$ простое, а $n−$ целое и при этом $p4+ 211= n2+ 5pn.$ В ответе укажите значения $n.$ Если их несколько, перечислите их в любом порядке через запятую.

Источники: ИТМО-2025, 11.6(см. olymp.itmo.ru)

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

Подсказка 1

Хотим использовать малую теорему Ферма (МТФ). Посмотрим на левую часть: по какому модулю удобно рассматривать остаток?

Подсказка 2

Рассматриваем остаток по модулю 5 (тогда возникает требование, что p не равно 5), так как по МТФ p⁴ дает остаток 1 по модулю 5. Вся левая часть, получается, дает остаток 2 по модулю 5. Теперь посмотрим на правую часть. Сразу видно, что второе слагаемое дает остаток 0 по модулю 5 (так как имеет вид 5*q). Что тогда можно сказать о n²?

Подсказка 3

Получается, n² должно давать остаток 2 по модулю 5. Рассмотрим различные случаи остатков. Какой вывод можем сделать?

Подсказка 4

Да, n² не может давать остаток 2 по модулю 5. Тогда у нас остается единственное возможное значение p: p = 5. Тогда наше уравнение превращается в квадратное, которое легко решается!

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

Согласно малой теореме Ферма, если $p⁄= 5,$ число $p4$ даёт остаток 1 при делении на 5. Число 211 также даёт остаток 1 при делении на 5. И $5pn$ делится на $5.$ Значит, если $p⁄= 5,$ мы получаем, что $2 n$ даёт остаток 2 при делении на 5, что невозможно.

Осталось разобрать случай $p =5.$ В этом случае нам надо решить квадратное уравнение

2 n +25n− 625 − 211= 0

−25±-√3125+-4⋅211 n1,2 = 2

Откуда получаем два решения: $(p,n)=(5,−44)$ и $(p,n)= (5,19).$

Ответ:

$− 44,19$

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

Задача 3#127177

Докажите, что для простого $p$ уравнение $ap +bp = cp$ не имеет решений в натуральных числах при $a$ , $b$ , $c≤ p.$

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

Подсказка 1

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

Подсказка 2

Если ни одно из чисел не равно p, то они точно меньше. Может тогда посмотреть на делимость, ведь у нас есть малая теорема Ферма.

Подсказка 3

Из малой теоремы Ферма легко получается, что a + b ≡ c (mod p). Но все числа меньше p, какие есть варианты?

Подсказка 4

Полезно бы сравнить aᵖ + bᵖ и cᵖ при полученных условиях, кажется одна из частей будет намного больше другой.

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

Предположим противное: пусть существуют натуральные числа $a,b,c≤p,$ удовлетворяющие уравнению $ap+bp = cp.$

Рассмотрим случаи, когда одно из чисел $a,$ $b,$ $c$ равно $p.$

Пусть $a= p.$ Тогда $p p p p + b = c.$ Так как $c≤ p,$ то $p p c ≤p .$ Следовательно,

p p p p p p +b ≥ p + 1> p ≥c ,

что невозможно. Аналогично для $b= p.$

Пусть $c=p,a⁄= p,b ⁄=p.$ Тогда

p p p p a +b ≤ 2(p− 1) <p ,

так как

(-p--)p = (1+--1-)p > 1+--p-> 2. p− 1 p− 1 p− 1

Теперь $a,b,c< p$ и $p$ – простое, значит, $a,b,c$ не делятся на $p.$ По малой теореме Ферма:

ap ≡a (mod p), bp ≡b (mod p), cp ≡ c (mod p).

Подставляя в исходное уравнение, получаем:

a +b≡ c (mod p).

Так как $1≤ a,b,c≤ p− 1,$ то $2≤a +b≤ 2(p− 1).$ Возможны два случая:

$a +b= c,$
$a +b= c+ p.$

а) Пусть $a+b= c.$

Тогда $ap +bp = (a +b)p.$ По биному Ньютона:

(a +b)p =ap +bp+ p−∑ 1(p)ap−kbk > ap +bp, k=1 k

так как все дополнительные слагаемые положительны при $a,b> 0$ и $p >1.$

б) Пусть $a+b= c+ p.$

Обозначим $s= a+ b,$ тогда $c =s− p, 2p− 1>s >p.$ Уравнение принимает вид:

p p p a +b = (s− p) .

При фиксированном $s$ минимум $ap+ bp$ достигается при $a =b = s, 2$ и тогда

p p (s)p 1−pp a +b ≥ 2 2 = 2 s .

Рассмотрим убывающую при $x> p$ функцию

( x )p f(x)= x-− p .

Так как функция убывает, то

( )p f(s)> f(2p)= 2p = 2p > 2p− 1 =⇒ p

21−psp > (s− p)p = cp,

что завершает доказательство.

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

Задача 4#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,$ чтд.

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

Задача 5#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),$ тем самым получено противоречие.

Ответ:

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

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

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

Курсы

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

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

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

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

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

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

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

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

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

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

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

Интенсивы

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

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

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

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

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

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

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

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

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

Ответ:

Всегда

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

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

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

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

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

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

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

Задача 18#90967

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

Ответ:

нет

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

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

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

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

Предыдущая подтема

Следующая подтема