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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

Ответ:

нет

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

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

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

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

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

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

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

Найдите все такие натуральные числа $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$ нет

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

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

Найдите все такие простые числа $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$

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

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

Докажите, что ни при каком целом $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,$ пришли к противоречию.

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

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

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

Курсы

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

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

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

Про простые числа $p$ и $q$ известно, что

2 q 2 p p+ p +...p =q +q + ...q.

Докажите, что $p= q.$

Источники: Изумруд - 2020, 11.4 (см. izumrud.urfu.ru)

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

Подсказка 1

Давайте попробуем решать задачу от противного и предположим, что p > q. На что похожи обе части равенства? Быть может, было какое-то разложение или формула? ;)

Подсказка 2

Левая часть выражения очень похожа на p^(q+1) - 1. А что нужно сделать, чтобы привести её к такому виду?)

Подсказка 3

Давайте домножим обе части равенства на (p-1)(q-1).

Подсказка 4

Как воспользоваться тем, что p и q различные простые?

Подсказка 5

Обратите внимание на делимость обеих частей на p.

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

Предположим, что $p⁄= q$ и без ограничения общности будем считать, что $p>q.$ Добавим к обеим частям равенства $1,$ после чего умножим обе части на $(p− 1)⋅(q− 1).$ Тогда по формуле разности степеней получим

( q+1 ) ( p+1 ) p − 1(q− 1)= q − 1 (p− 1).

Раскрыв скобки, получаем

q+1 q+1 p+1 p+1 p q− p − q =q p− q − p,

что, в свою очередь, равносильно равенству

pq+1q− pq+1− qp+1p+ p=q − qp+1.

Поскольку левая часть равенства делится на $p,$ то и выражение

q− qp+1 =q(1− qp)

делится на $p.$ Поскольку $p$ и $q$ являются простыми числами и $p> q,$ то НОД $(p,q)= 1,$ а значит $. (qp− 1)..p.$ Но из малой теоремы Ферма следует, что

qp− 1≡ p− 1 ≡− 1, p p

поэтому $− 1...p,$ что невозможно. Следовательно, наше предположение ошибочно и $p =q.$

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

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

В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа $a$ и простого натурального числа $p$ справедливо соотношение:

$p a− a$ делится на $p$ без остатка.

Итак, $p >2$ — простое число. Маша должна понять, есть ли среди чисел

a1+b1,a2+b2,...,ap−1+ bp−1

значения, дающие одинаковые остатки от деления на $p$ .

1. Пусть $a= 4,b= 9$ . Докажите, что искомая пара найдётся.

2. Пусть $a= 4,b= 3$ . Докажите, что найдётся искомая пара, содержащая одно из крайних чисел.

3. Докажите, что искомая пара найдётся при $a= 4,b= 7$ .

4. Докажите, что искомая пара найдётся, если $a= 2,b= 3$ , а $p−1 -2-$ - простое.

Источники: ЮМШ-2020, сюжет 3 (см. yumsh.ru)

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

Подсказка 1

Для первых трёх пунктов достаточно использовать малую теорему Ферма с тем лишь дополнением, что во втором и третьем пункте нужно разобрать отдельно случаи с малыми значениями p, а вот в 4 пункте всё интереснее!

Подсказка 2

Перейдём к последнему пункту. Докажем методом "от противного". Будем рассматривать порядки 2 и 3 по модулю p. Чему они могут быть равны?

Подсказка 3

Действительно, варианты: 1, 2, q, 2q = p - 1. Неразобранный случай остался 2q. В нашем предположении в последовательности должны встретиться по разу все ненулевые остатки. Вот бы теперь какое-нибудь утверждение про остатки придумать. Пусть у нас есть два числа меньших q (q > 2), числа x и k. При этом x и остаток kx от деления на q имеют разную чётность. Можем ли мы тогда определить k относительно q? Какое можем получить отсюда следствие?

Подсказка 4

Действительно, k = q-1. Осталось подумать над следствием, и мы уже близки к финалу!

Подсказка 5

Для простого q, нечётного k такого, что 2q не делится на (k+1) найдется l, что остатки чисел l, kl по модулю 2q лежат строго между 0 и q. Во-первых, это не всем известный факт и по-хорошему требует доказательства. Во-вторых, применим это следствие, а дальше изучим сумму по k от 1 до (p - 1) чисел (2^k + 3^k)^(l+r) по модулю p.

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

1. По МТФ $4p−1+ 9p−1 ≡2$ , но в то же время и $p−1 p−-1 4 2 + 9 2 = 2p−1+ 3p−1 ≡ 2$ .

_________________________________________________________________________________________________________________________________________________________________________________

2. Если $p= 3$ , то всё ясно. Если $3(p−1)∕2 ≡ 1$ , то остальное как в предыдущем пункте. Иначе же $3(p−1)∕2 ≡ −1$ . Например, потому что из МТФ $3p− 1 ≡ 1$ , значит,

(3p−21− 1) (3 p−21-+1):p

Тогда

p−21+2 p−21 +2 1 1 4 + 3 ≡16− 9≡ 7= 4 + 3.

______________________________________________________________________________________________________________________________________________________

3. Случаи $p≤7$ разбираются руками. Дальше, аналогично предыдущим пунктам, если $7(p−1)∕2 ≡ 1$ , то всё ясно. Иначе $7(p−1)∕2 ≡− 1$ , а тогда для $k =1,...,p−1 2$

k k p−1+k p−1+k k p−1+k k 4 + 7 + 4 2 +7 2 ≡ 4 + 4 2 ≡2 ⋅4 .

Если бы остатки не повторялись, каждый бы встречался по разу, и тогда их сумма была бы равна 0 . Но тут, как мы видим, их сумма равна

p+1 2(4+ 42+ ...+4p−21) =2⋅ 4-2-− 4 ≡ 4⋅(4p−21− 2) ≡ 4⋅−1⁄≡ 0 4− 1 3 3

_________________________________________________________________________________________________________________________________________________________________________________

4. Предположим, что все остатки различны. Посмотрим на порядки 2 и 3 по модулю $p$ . (Порядок $a$ по модулю $p$ - минимальное натуральное $k$ такое, что $ak− 1$ (или числитель соответствующей несократимой дроби,если $a$ - дробь) кратно $p$ ; это $k$ мы будем обозначать $ordp(a)$ .) По МТФ они могут быть равны лишь $1,2,q,2q =p− 1$ . Первые два случая проигнорируем, а случаи, когда хотя бы один из порядков равен $q$ , идентичны разобранным в пунктах 1 и 3 . Пусть порядки $2q$ , в частности все остатки $2,22,...,2p−1$ , различны (иначе, если $2a$ и $2b$ дают одинаковые остатки, то $2a− 2b$ , а значит и $2a−b− 1$ , кратно $p$ , но $a− b< p− 1$ ) и найдётся такое $m$ , что $2m = 3$ . Отметим также, что в этом случае $2q =3q =−1$ , так что если при некотором $k$ имеем $2k +3k = 0$ , то и $( ) 2k±q +3±q = − 2k+ 3k = 0$ , так что нарушается условие различности остатков. Поэтому в нашей последовательности встречаются по разу все ненулевые остатки.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Пусть $q >2$ простое и $k <q$ таково, что для любого $x= 1,2,...,q − 1$ число $x$ и остаток $kx$ от деления на $q$ имеют разную чётность. Тогда $k= q− 1$ .

Следствие 1. Пусть $q$ простое, $k$ нечётное, $k +1$ не кратно $2q$ . Тогда найдется $l$ такое, что $y$ обоих чисел $l,kl$ остатки по модулю $2q$ заключены строго между $0$ и $q$ .

Доказательство. Действительно, попробуем в качестве $l$ все числа от 1 до $q − 1$ . Пусть все пары $l,kl$ не подошли, т.е. все $kl$ имеют остатки по модулю $2q$ , большие $q$ . Это значит, что чётность остатка $kl$ по модулю $q$ противоположна четности остатка $kl$ по модулю $2q$ ( $q$ - нечётно), а она совпадает с четностью $l$ (т.к. $k$ нечётно), и мы попадаем в условия леммы.

_________________________________________________________________________________________________________________________________________________________________________________

Подберём по следствию 1 такое $0< l<q$ , что $− ml$ при делении на $2q$ имеет остаток меньше $q$ , назовём этот остаток $r,r+ ml$ делится на $2q$ .

Теперь изучим сумму $∑p−1(2k+ 3k)r+l k=1$ по модулю $p$ . С одной стороны, выражение в скобках пробегает все ненулевые остатки, а число $r+ l<q +q$ не кратно $p − 1= 2q = ord(2)$ , так что эту сумму можно посчитать как сумму геометрической прогрессии с неединичным знаменателем $r+l 2$ , и она равна нулю.

Посчитаем эту же сумму другим способом. Раскрыв все скобки по биному, перегруппировав слагаемые и переставив множители в показателях степеней, мы получим сумму геометрических прогрессий вида $i ∑ (i r+l−i)k Cr+l 23$ . Докажем, что ровно одна из этих прогрессий постоянна, а значит, ровно одно из указанных выражений ненулевое (тут надо отметить, что $r,l< q$ , так что $r +l< 2q = p− 1$ , поэтому появляющиеся биномиальные коэффициенты не кратны $p$ ). Это даст требуемое противоречие.

Действительно, при $i= r$ получаем, учитывая $m 2 = 3$ , что $rr+l−r r+ml 23 = 2 = 1$ , т.к. $r+ ml$ делится на $2q$ . С другой стороны, если $r+sr+l−r−s 2 3 =1$ , при некотором $s∈ [−r,l]$ то, деля, получаем $s−s 23 = 1$ то есть $s (2∕3) = 1$ . Получаем, что $ordp(2∕3)≤max(r,l)< q$ , значит $ordp(2∕3)$ равен 1 или 2 , что может быть лишь при $p= 5$ ; этот случай проверяется непосредственно.

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

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

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

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

Даны натуральные числа $a$ и $b.$ Докажите, что существует бесконечно много натуральных $n$ таких, что число $an+ 1$ не делится на $b n + 1.$

Источники: Всеросс., 2018, ЗЭ, 10.6(см. olympiads.mccme.ru)

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

Назовём натуральное $n$ плохим, если $an+1$ не делится на $nb+1.$ Наша цель — доказать, что плохих чисел бесконечно много.

Первое решение. Докажем, что при любом чётном $n$ одно из чисел $n$ и $3 n$ плохое; из этого, очевидно, следует требуемое. Предположим противное. Тогда $n .. b a + 1.n + 1$ и $n3 .. 3b .. b a +1.n + 1.n +1.$ Иначе говоря, $n ( b ) a ≡− 1 mod n + 1$ и $n3 ( b ) a ≡ −1 mod n + 1.$ Но отсюда следует, что $n3 nn2 n2 ( b ) − 1 ≡a = (a ) ≡ (−1) ≡1 modn + 1 ;$ это невозможно, ибо $b n +1 >2.$ Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. При $a= 1$ утверждение задачи очевидно, поэтому будем считать, что $a> 1.$

______________________________________________________________________________________________________________________________________________________

Лемма. Пусть $a >1,m$ и $n$ — натуральные числа. Предположим, что $an+ 1$ делится на $am+ 1.$ Тогда $n$ делится на $m.$

Доказательство. Пусть $r$ — остаток от деления $n$ на $m,n− r= qm.$ Тогда

0 ≡an +1= aqm+r+ 1≡ (− 1)qar+ 1=±ar +1(mod am+ 1)

то есть одно из чисел $r a ± 1$ делится на $m a + 1.$ Но это невозможно при $r⁄= 0,$ ибо $r m 0< a ±1 <a + 1.$

______________________________________________________________________________________________________________________________________________________

Докажем, что существует бесконечно много плохих чисел вида $ak.$ Действительно, если $k aa +1$ делится на $akb+ 1,$ то по лемме $ak$ должно делиться на $kb.$ Это невозможно, если, например, $k$ — простое число, большее $a.$ Осталось заметить, что таких простых чисел бесконечно много.

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Мы опять же исследуем лишь случай $a> 1.$

Пусть $p$ — некоторый простой делитель числа $(a(a− 1))b+1.$ Положим $ni = a(a− 1)+ ip;$ тогда при любом $i$ имеем $nbi + 1≡ (a(a− 1))b+ 1≡ 0(mod p),$ то есть $nbi + 1$ делится на $p.$

С другой стороны, покажем, что числа $ani + 1$ и $ani+1 +1 =ani+p+ 1$ не могут одновременно делиться на $p.$ Действительно, иначе на $p$ делилась бы и их разность $ani(ap − 1);$ но это невозможно, ибо $ap− 1≡ a− 1(mod p)$ по малой теореме Ферма, а числа $a$ и $a− 1$ взаимно просты с $p.$

Итак, либо $ani + 1$ не делится на $p$ (и, значит, на $nbi +1$ ), либо $ani+1 +1$ не делится на $p$ (и, значит, на $nbi+1+ 1$ ). Поэтому среди чисел $n1,n2,...$ бесконечно много плохих.

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

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

Натуральные числа $n$ и $k$ удовлетворяют неравенству $1≤ n≤ k.$ Известно, что для любого натурального делителя $d$ числа $n$ число $k d + k$ является простым. Докажите, что число $n +k$ простое.

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

Подсказка 1

Для начала логично подставить в формулу число, которое гарантировано является делителем n, то есть единицу. Так получаем, что 1+k является простым, назовём его p. Как соотносится p и делители числа n?

Подсказка 2

Поскольку 1+k>n, любой делитель d числа n строго меньше p, а значит, взаимно прост с n. Но тогда что можно сказать о делимости d в степени k-ой плюс k на p?

Подсказка 3

Действительно, по малой теореме Ферма d в степени p-1 сравнимо с 1 по модулю p, то есть после прибавления p-1 получится число, делящееся на p, которое должно являться простым, а значит, оно равно p. Осталось сделать выводы о том, чему в таком случае равно n.

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

Подставив в условие $d= 1$ (такой делитель у $n$ точно есть), мы узнаем, что число $p= k+ 1$ — простое. Поскольку $p> k≥ n,$ ни один делитель числа $n$ не кратен $p.$ Следовательно, по малой теореме Ферма простое число $k p− 1 d + k= d +p− 1$ кратно $p$ и, значит, равно $p$ для каждого делителя $d$ числа $n.$ Это значит, что единственный делитель $n$ — это число $1,$ то есть $n= 1$ и $n+ k= 1+ (p− 1)= p,$ что и требовалось доказать.

Интенсивы

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

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

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

Маша, скучая на уроке математики, проделала с некоторым 2015-значным натуральным числом следующую операцию: от десятичной записи этого числа она отбросила последнюю цифру и к умноженному на 3 получившемуся числу прибавила удвоенную отброшенную цифру. С полученным числом она опять проделала ту же операцию и так далее. После многократного применения этой операции получающиеся у Маши числа перестали меняться, и тогда она остановилась.

(a) Какое число оказалось у Маши в конце?

(b) Какое наименьшее число могло быть у Маши в самом начале (укажите две его последние цифры)?

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

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

Нам говорят, что числа у Маши перестали меняться - намекают на уравнение! Попробуйте его составить, грамотно обозначив число, получившееся у Маши.

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

Подумайте, как часто такое уравнение имеет решение, если одна из наших переменных - цифра

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

Изначально у нас было какое-то гигантское число, а стало 17 ⇒ число уменьшилось. Это произошло из-за того, что у Маши было какое-то специальное число? Или так всегда происходит?

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

Верно, большое число всегда уменьшается после применения такой операции. Мы должны получить 17 в какой-то момент, надо бы понять что-то про изначальное число из этого. А какое число могло быть у Маши перед тем, как она получила 17? Видите что-то общее у этих чисел?

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

Давайте попробуем доказать в общем виде, что если получилось число, делящееся на 17, то и до этого число делилось на 17. Попробуйте связать (10x + y) и (3x + 2y) так, чтобы там фигурировало 17.

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

Можно заметить, что если к 3х + 2y добавить 17x, получится 2(10x + y). То есть изначальное число должно делиться на 17, надо просто найти наименьшее такое ⇒ надо взять 10²⁰¹⁴ и добавить к нему недостающий остаток

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

17 - простое число. Помните теорему, помогающую найти остаток от деления на простое число?

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

Конечно, это Малая теорема Ферма! Остаётся только представить 2014 в виде 16k + r, и задачка убита!

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

a) Пусть в конце осталось число $n$ , оканчивающееся на цифру $y$ . Тогда $n = 10x +y$ после очередной операции станет равным $3x+ 2y.$

Равенство $10x+ y = 3x+ 2y$ равносильно $y = 7x$ и, так как $y$ – цифра, то $y = 7,x= 1$ . Поэтому $n= 17$ .

b) Заметим, что если число $≥ 20$ , тогда оно обязательно уменьшается: $10x +y >3x+ 2y$ равносильно $7x> y$ . (что для $x> 1$ всегда верно). Из соотношения

2(10x+ y)=17x+ 3x+ 2y

следует, что число $10x +y$ делится на $17$ тогда и только тогда, когда $3x+2y$ делится на $17$ . Поскольку стабилизация операции происходит на числе $17$ , то исходное число также должно делиться на $17.$

Найдём наименьшее $2015$ -значное число, которое делится на $17$ . По малой теореме Ферма $16 10 ≡171,$ поэтому

2014 125⋅16 14 14 7 10 = 10 ⋅10 ≡1710 = (17⋅6− 2) ≡17−16⋅8 ≡178

Тогда число $102014+ 9$ - наименьшее число, которое делится на $17$ нацело, значит, это и будет наименьшее число, которое могла выписать Маша. Его последние две цифры $09$ .

Ответ:

a) $17$

b) $09$ (число $100...0009$ )

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

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

Дано бесконечное множество натуральных чисел $M.$ Известно, что для любых двух различных чисел $a,b ∈M$ в множестве $M$ также содержится хотя бы одно из чисел $b a − 2$ и $b a +2.$ Докажите, что в $M$ содержится хотя бы одно составное число.

Источники: СпбОШ - 2014, задача 11.5(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Да-да, нам нужен тот самый модуль, который нас не раз выручал (модуль 3). Рассмотрим произвольные a и b, a также числа a^b - 2 и a^b + 2. Теперь следует рассмотреть 2 случая:
a даёт остаток 1 при делении на 3 или a даёт остаток 2 при делении на 3. Для каждого из этих случаев можно несложными преобразованиями доказать, что в множестве будет число, которое будет составным.

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

Решение 1.
Предположим, что множество $M$ состоит только из простых чисел. Тогда все числа из множества $M$ нечётные(так как любое число вида $b 2 ± 2$ составное при $b≥ 3$ ). Возьмём в множестве $M$ два произвольных числа $a,b≥3.$ Если $a$ даёт остаток $1$ при делении на $3,$ то $b a$ также даёт остаток $1.$ Тогда $b a + 2$ делится на 3 и по нашему предположению $b a+ 2$ не может принадлежать множеству $M.$ Значит, в этом случае множеству $M$ принадлежит число $b a− 2.$ Аналогично если $a$ даёт остаток $2$ при делении на $3,$ то $b a$ также даёт остаток $b 2,a − 2$ составное и тогда в этом случае множество $M$ должно содержать число $b a+ 2.$
Если множество $M$ содержит хотя бы одно простое число $a,$ дающее остаток $1$ при делении на $3,$ то в множестве $M,$ как мы установили, содержится число вида $b a − 2,$ дающее остаток $2.$ Тогда число $b a (a − 2) +2$ тоже принадлежит $M.$ Заметим, что это число даёт при делении на $a$ тот же остаток, что и число $(− 2)a+ 2= −2a+ 2.$ Но это число делится на $a$ по малой теореме Ферма, значит, оно составное.
Аналогично, если простое число $a∈ M$ даёт остаток $2$ при делении на $3,$ то в множестве $M$ содержится число $(ab+2)a− 2,$ которое по тем же причинам делится на $a.$
Решение 2.
Предположим противное. Как и в первом решении установим, что если $a≡ ±1$ (mod $3$ ) принадлежит $M,$ то $ab∓ 2≡ ∓1 (mod 3)$ также принадлежит $M.$ В частности, в $M$ есть числа, сравнимые как с $1,$ так и с $− 1$ по модулю $3.$
Рассмотрим простые числа $q ≡ 1 (mod 3)$ и $r$ из $M.$ Тогда в $M$ содержится простое число

p =(qr− 2)r+ 2≡ (1− 2)r+2 =1 (mod q− 1).

Следовательно, $p− 1$ делится на $q − 1.$ Пусть $p− 1= k(q− 1).$ Тогда число

a =(qp− 2)p+ 2≡ (− 2)p+ 2= −2p+ 2= −2(2p−1− 1) (mod q)

делится на $q,$ поскольку по малой теореме Ферма $q−1 2 ≡ 1 (mod q)$ и, значит,

k 2p−1 = 2k(q− 1) = (2q−1) ≡ 1k =1 (mod q).

Таким образом, число $a$ принадлежит $M$ и является составным. Противоречие.

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

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

Найдите все натуральные $k$ такие, что произведение первых $k$ нечетных простых чисел, уменьшенное на 1, является точной степенью натурального числа (большей, чем первая).

Источники: ВСОШ, ЗЭ, 2013, 11.3 (см. olympiads.mccme.ru)

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

Подсказка 1

Пусть произведение нечётных простых чисел равно aⁿ + 1. Хотелось бы посмотреть на нечётные делители a. Но существуют ли они?

Подсказка 2

Если показатель степени не простой, можно ли его сделать простым?

Подсказка 3

Можно обратить внимание, что у нас есть нечётные простые из произведения, а также простое n. Давайте рассмотрим простой нечётный делитель числа a. Может их стоит сравнить между собой?

Подсказка 4

В произведении есть все простые вплоть до некого pₖ. Если n меньше pₖ, то оно входит в произведение простых. Что тогда можно сказать о aⁿ при рассмотрении по модулю n?

Подсказка 5

Тогда с одной стороны aⁿ + 1 делится на n, но по малой теореме Ферма и aⁿ − a тоже делится на n. Не противоречат ли эти две делимости друг другу?

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

Пусть $n ≥2,$ и $3= p < ⋅⋅⋅< p 1 k$ — первые $k$ нечётных простых чисел. Предположим, что $p p ...p = an+ 1 (⋆). 1 2 k$

Без ограничения общности можно считать, что $n$ – простое число, ведь если $n= st,$ то можно заменить $n$ на $s,$ а $a$ — на $t a.$ Заметим, что $n> 2,$ поскольку $2 a + 1$ не делится на $3= p1$ при любом $a.$

Пусть у $a$ есть нечетный простой делитель $q.$ Тогда $q > pk,$ иначе левая часть $(⋆)$ делилась бы на $q,$ что не так. Поэтому и $a >pk.$

Покажем, что $n > pk.$ Действительно, в противном случае $n =pi,$ где $i≤ k.$ Тогда $p a i +1$ кратно $pi;$ с другой стороны, по малой теореме Ферма $p a i − a$ кратно $pi.$ Так как

api + 1= (a+1)(api−1− api−2+ ⋅⋅⋅− a+1),

причём $pi pi a +1 =(a +1)− (a − a)$ кратно $pi$ и

p−1 p−2 a i − a i + ⋅⋅⋅− a+ 1= 1+ 1+⋅⋅⋅+1= pi ≡ 0 (mod pi),

то $api + 1$ делится на $p2, i$ что противоречит условию.

Итак, $a >p k$ и $n> p, k$ откуда

n pk a + 1> pk > p1p2...pk

что противоречит $(⋆)$ , значит, $a$ — степень двойки. Степени двойки имеют остатки $1,2,4$ при делении на $7,$ а $an +1$ делится на $7$ при $k > 3.$ Значит, $k≤ 2,$ и возможными значениями для $an$ являются $3− 1= 2$ и $3⋅5− 1= 14.$ Оба варианта не подходят, следовательно, подходящих $k$ нет.

Ответ:

Таких $k$ не существует

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

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