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

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

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

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

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

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

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

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

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

Задача 1#78919

Даны взаимно простые числа $a$ и $b.$ Докажите, что для любого нечетного делителя $d$ числа $a2n + b2n$ число $d− 1$ делится на $n+1 2 .$

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

Пусть $d$ — нечетный делитель числа $a2n +b2n.$ В силу взаимной простоты чисел $a$ и $b$ будет также верно, что $d$ взаимно просто с $a$ и $b.$ Тогда по модулю числа $d$ остатки $a,b$ будут обратимы.

Пусть $c$ — такое число, что $c⋅b ≡1 (mod d).$ Тогда

2n 2n 2n a +b ≡ 0 =⇒ (ac) ≡ (− 1) (mod d)

Тогда $(ac)2n+1 ≡ 1,$ то есть число $ac$ имеет показатель по модулю $d$ равный $2n+1$ (так как $(ac)2n+1 ≡1$ означает, что $2n+1$ делится на показатель, но $(ac)2n ≡ −1$ говорит о том, что меньшие степени двойки не будут показателем)

Если $d$ — простое, то $(ac)d−1 ≡1$ и тогда $(d − 1)..2n+1 .$ делится на показатель. Если $d$ составное, то оно раскладывается, как $α1 αk d =p1 ...pk$ при этом предыдущие равенства можно рассмотреть по модулю $pi,$ тогда $n+1 pi ≡1 (mod 2 )$ для всех простых делителей числа $d.$ Тогда $n+1 d≡ 1 (mod 2 ),$ то есть $.. n+1 (d− 1).2 .$

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

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

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

Задача 2#83156

Докажите, что натуральные числа $1,2,...,238$ можно расставить по кругу так, чтобы для любых трех подряд идущих по часовой стрелке чисел $a,$ $b,$ $c$ число $2 b − ac$ делилось на $239.$

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

Подсказка 1

Условие задачи напоминает геометрическую прогрессию. А можно ли как-то представить остатки в виде геометрической прогрессии?

Подсказка 2

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

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

Будем воспринимать наши числа $1,2,...,238,$ как $g,g2,...,gp−1,$ где $g$ — первообразный корень и будем их расставлять по кругу, так как нас интересует значения чисел лишь по модулю $239.$ Расставим их по кругу так $2 p−1 g,g ,...,g .$ Для чисел $i− 1 g ,$ $i g ,$ $i+1 g$ очевидно, что $2i i−1i+1 g − g g$ делится на $239,$ поэтому наша конструкция подходит для всех чисел не на стыке. На стыке все тоже хорошо, так как числа $g$ и $2 g$ можно представить, как $p g$ и $p+1 g .$

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

Задача 3#83959

Докажите, что для любого натурального $n$ существует натуральное $k$ такое, что $51k− 17$ делится на $2n.$

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

Решение 1.

Лемма. Для любого натурального $n ≥3$ найдётся натуральное $l,$ такое что $( l ) v251 − 1 =n.$

Доказательство. Индукция по $n.$ База индукции: $n =3.$ Годится $l= 2.$ Переход индукции. Если $( l ) v2 51 − 1 = n,$ то

( 2l ) ( l ) ( l ) v2 51 − 1 = v2 51 − 1 +v2 51 +1 =n +1

Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение задачи тоже доказываем индукцией по $n.$ База: $512− 17$ делится на $23 = 8$ . Переход. Пусть $51k− 17$ делится на $2n.$ Хотим добиться делимости на $2n+1.$ Пусть $l$ таково, что $( ) v251l− 1 =n.$ Можем считать, что $51k− 17$ не делится на $17,$ а также что $k >l.$ Тогда рассмотрим разность

( ) ( ) 51k− 17 − 51k−l⋅ 51l− 1 = 51k−l− 17

Так как оба числа $( ) 51k− 17$ и $( ) 51k−l⋅ 51l− 1$ делятся на $2n$ и не делятся на $2n+1,$ то $51k−l− 17$ делится на $2n+1.$

______________________________________________________________________________________________________________________________________________________

Решение 2.

Покажем, что $2n−2$ является показателем числа $51$ по модулю $2n$ (при условии $n≥ 3).$ Этот показатель является делителем числа $ϕ(2n)= 2n−1,$ т.е. является степенью двойки. Но при любом натуральном $s$ верно $( ) v2 512s − 1 = s+ 21.$ Значит, показатель в самом деле равен $2n−2.$

Таким образом, степени числа $51$ пробегают ровно четверть всевозможных остатков по модулю $2n.$ Но по модулю $8$ эти степени могут давать лишь остатки $1$ и $3,$ а значит, степени числа $51$ пробегают все остатки по модулю $2n,$ дающие $1$ или $3$ по модулю $8.$ В частности, остаток $1$ тоже пробегают.

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

Задача 4#97875

Пусть $N$ — произведение первых ста простых чисел. Сравнимо ли $2N$ с единицей по модулю $17?$

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

Подсказка 1

Посчитайте показатель 2 по модулю 17.

Подсказка 2

N должно на него делиться, не так ли?

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

Заметим, что $ord (2)= 8. 17$ $N$ на $8$ не делится, а значит, сравнения быть не может.

Ответ:

Нет

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

Задача 5#98615

Докажите, что сравнение $x4 ≡ −1 (mod p)$ имеет решение тогда и только тогда, когда простое $p= 8k+1.$

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

Подсказка 1

Пусть x⁴ сравнимо с -1 по модулю p. Обозначим через s показатель x по модулю p. Что можно сказать про s?

Подсказка 2

Конечно! Тогда x⁸ сравнимо с 1, и поэтому s делит 8. Чему равно s?

Подсказка 3

Верно! s = 8, а из малой теоремы Ферма s делит (p-1). Какой вывод можно сделать?

Подсказка 4

Теперь в обратную сторону. Любое число в степени 8k сравнимо с 1 по модулю p, поскольку p простое. Тогда любое число в степени 4k сравнимо с 1 или -1 по модулю p. А какое число можно возвести в степень 4k, чтобы наверняка получить -1?

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

Пусть для некоторого $x$ имеет место сравнение $x4 ≡ −1 (mod p).$ Тогда $x8 ≡ 1 (mod p).$ Пусть $s =ord(x). p$ Заметим, что $s|8.$ Если $s∈ {1,2,4},$ то сравнение $4 x ≡− 1 (mod p)$ не выполняется, откуда получаем, что $s= 8.$ Так как $p−1 x ≡ 1 (mod p)$ (по малой теореме Ферма), то $s|(p− 1),$ тогда $p− 1 =8k,$ откуда и получаем $p= 8k +1.$

Обратно, предположим, что $p= 8k+ 1.$ Пусть $g$ — первообразный корень по модулю $p.$ Поскольку $ordp(g)= 8k,$ легко видеть, что из сравнения $8k g ≡ 1 (mod p)$ следует, что $4k g ≡ −1 (mod p)$ (в случае $4k g ≡ 1 (mod p)$ получаем противоречие с тем, что $g$ — первообразный корень). В качестве решения $4 x ≡ −1 (mod p)$ берем $k x≡ g (mod p).$

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

Задача 6#98616

(a) Пусть $p =4k+ 1$ — простое. Докажите, что $a$ является первообразным корнем по модулю $p$ тогда и только тогда, когда $− a$ является первообразным корнем;

(b) Пусть $p= 4k+ 3$ — простое. Докажите, что $a$ является первообразным корнем по модулю $p$ тогда и только тогда, когда $ordp(−a)= 2k+ 1.$

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

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

Ясно, что достаточно доказать утверждение только в одну сторону. Пусть s — показатель -a по модулю p. Может ли s быть нечетным?

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

Поскольку s — показатель -a, то степени s остатков a и (-1) сравнимы по модулю p. А какая степень остатка a сравнима с 1?

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

Верно, степень 2s! Но мы знаем, что 4k — показатель a, поэтому 4k | 2s, то есть 2k | s. Значит, s четное число. С каким числом сравнима s-я степень a?

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

Сначала предположим, что a — первообразный корень по модулю p. Очевидно, что (2k+1)-я степень a сравнима с -1. Обозначим через s показатель -a. Что можно сказать об s?

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

Верно! Тогда s делит 2k+1, следовательно, s не превосходит 2k+1. Остается понять, почему невозможно неравенство s < 2k+1. Для ответа на этот вопрос вспомним, что показатель a равен 4k+2!

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

Теперь будем доказывать обратное. Пусть показатель -a равен 2k+1, а s — теперь показатель a. Тогда сразу получаем, что s делит 4k+2. Предположим, что s < 4k+2. Может ли s быть четным?

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

Если s делит 4k+2 и меньше 4k+2, то s меньше 2k+1, поскольку оно четно. В чем противоречие?

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

Верно! Тогда s-я степень -a сравнима с 1, хотя показатель у -a нечетный. Но тогда s нечетно, поэтому из s | (4k+2) следует, что s | (2k+1). А где тут противоречие?

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

(a) Достаточно доказать утверждение только в одну сторону, так как в обратную сторону утверждение получается заменой $t= −a.$ Итак, пусть $a$ — первообразный корень по модулю $p.$ Тогда $ordp(a)=4k.$ Пусть $s= ordp(−a).$ Тогда $s s a ≡p (−1) .$ Предположим, что $s$ нечетно, тогда $s a ≡p − 1,$ поэтому $2s a ≡p 1.$ Тогда $4k|2s,$ то есть $2k|s,$ поэтому $s$ — четно, получаем противоречие. Тогда $s a ≡p 1.$ Отсюда получаем, что $s≥ 4k.$ Легко видеть, что при $s= 4k$ получаем верное сравнение.

(b) Пусть $a$ — первообразный корень. Тогда $ordp(a)= 4k+ 2.$ То есть $4k+2 a ≡p 1,$ поэтому $2k+1 a ≡p 1$ (что невозможно, иначе $a$ не является первообразным корнем) или $2k+1 a ≡− 1.$ Тогда $2k+1 (−a) ≡p 1.$ Пусть $s= ordp(−a).$ Тогда $s|2k +1,$ следовательно, $s≤ 2k+ 1.$ Предположим, что $s< 2k+ 1.$ Тогда $2s <4k+ 2,$ при этом $(−a)s ≡p 1,$ откуда $(− a)2s ≡p 1,$ поэтому $a2s ≡p 1,$ что противоречит тому, что $a$ является первообразным корнем. Значит, $ordp(−a)= 2k+ 1.$

Обратно, пусть теперь $ordp(−a)= 2k +1.$ Тогда $a2k+1 ≡p − 1,$ поэтому $a4k+2 ≡p 1.$ Пусть $ordp(a)=s.$ Предположим, что $s< 4k+ 2.$ Тогда $s|4k+2,$ потому $s≤ 2k+ 1.$ Если $s$ четно, то имеем $(−a)s ≡p 1,$ при этом $s <2k+ 1$ — противоречие. Тогда $s$ нечетно. Значит, из $s|4k +2$ следует, что $s|2k+ 1.$ Но тогда $a2k+1 ≡p −1$ и $as ≡p 1,$ что невозможно. Значит, $s= 4k+2,$ что и требовалось.

Курсы

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

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

Задача 7#98617

Пусть $q$ — простое число. Оказалось, что $p= 4q +1$ — простое. Докажите, что $2$ является первообразным корнем по модулю $p.$

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

Подсказка 1

Пусть s — показатель 2 по модулю p. Какие значения может принимать s?

Подсказка 2

Верно! s — это одно из чисел 2, 4, q, 2q или 4q. Поскольку p — простое число, то по модулю p есть первообразный корень. Тогда остаток 2 — некоторая степень k этого первообразного корня. Тогда мы знаем, что 4q | sk. Как доказать, что s не может быть равно 2 или 4?

Подсказка 3

Точно! Тогда бы получилось, что 16 сравнимо с 1 по модулю p, что невозможно для p вида 4q+1 с простым q. Для того, чтобы доказать, что s не может быть равно q или 2q вспомним, что 4q | sk. Какими свойствами обладает k?

Подсказка 4

Верно! В обоих случаях k четно, поэтому 2 является квадратичным вычетом по модулю p. Возможно ли это?

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

Пусть $g$ — первообразный корень по модулю $p$ и $s =ord(2). p$ Тогда $24q ≡ 1$ по малой теореме Ферма, а потому $s|4q.$ С другой стороны, $k 2≡p g ,$ поскольку $НОД (2,p)=1.$ Таким образом, $sk g ≡ 1,$ следовательно $4q|sk.$ Ясно, что тогда $s∈ {2,4,q,2q,4q}.$ В случае $s∈ {2,4}$ имеем $k = qm,$ поэтому $qm g ≡p 2,$ следовательно, $16 ≡p 1,$ поскольку $4q g ≡ 1.$ Очевидно, что $k ⁄=0.$ При простых $p$ это возможно только для $p= 3$ и $p =5,$ которые не представляются в виде $4q+ 1$ для простых $q.$

Предположим, что $s= q.$ Тогда $4t 2≡p g .$ Тогда $2$ является квадратичным вычетом по модулю $p.$ Найдем символ Лежандра

( 2) 2 2 p = (−1)(p−1)∕8 =(−1)2q +q = −1

Тогда $q$ не может являться квадратичным вычетом по модулю $p$ — противоречие. В случае $s= 2q$ снова получаем, что $k =2t,$ поэтому $g2t = 2,$ но $2$ не может являться квадратичным вычетом по модулю $4q +1.$ Таким образом, $s =4q,$ что и требовалось.

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

Задача 8#98618

Найдите все простые $p =5k+ 1$ такие, что остатки чисел $15,25,...,k5$ при делении на $p$ различны.

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

Подсказка 1

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

Подсказка 2

Докажите, что вычетов пятой степени ровно k, и их можно записать как первообразный корень в степенях 1, 2, 3, ..., k. Непонятно, как в терминах первообразных корней понять, что нужные нам числа - это именно 1, 2, 3, ..., k. Раз не получается сказать про объекты по отдельности, то нужно посмотреть сразу на все объекты. Рассмотрите какие-либо симметричные функции от k переменных.

Подсказка 3

Вычеты пятой степени, как мы уже поняли, образуют геом. прогрессию. У нее хорошо считается сумма и оказывается, что по модулю p она равна 0. Тогда и сумма пятых степеней чисел 1, 2, 3, ..., k равна 0. Как ее можно посчитать?

Подсказка 4

Попробуйте выразить сумму пятых степеней первых чисел через симметрические функции, либо угадать ответ и проверить его по индукции.

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

Для начала покажем, что вычетов пятой степени ровно $k$ по модулю $p=5k +1.$

Пусть $α −$ первообразный корень по модулю $p= 5k+ 1.$ Тогда все ненулевые остатки можно записать как $0 1 2 5k−1 α ,α ,α ...α .$ Так как $α−$ первообразный корень, то если пятые степени каких-то остатков $x y α ,α$ совпадают, то $5x− 5y$ кратно $5k,$ то есть $x− y$ кратно $k,$ значит, все остатки разбиваются на $k$ групп по $5$ чисел, пятые степени которых дают одинаковый результат по модулю $p.$

Все эти остатки пятой степени можно записать как $0 5 10 5k−5 α,α ,α ...α .$ Сумма всех этих остатков равна $α5k−1 α5−1 ≡ 0 (mod p).$

Значит, если остатки чисел $5 5 5 1 ,2,...,k$ при делении на $p$ различны, то это все остатки пятой степени, а, значит, по доказанному ранее сумма пятых степеней этих чисел равна нулю по модулю $p.$ Воспользуемся следующей формулой

k2(k+ 1)2(2k2+2k− 1) 15+ 25+35+ ⋅⋅⋅+ k5 =--------12--------

которую можно доказать по индукции. Если это выражение равно нулю по модулю $5k+1,$ то $2k2+ 2k− 1$ кратно $p.$ Далее все сравнения по модулю $p.$

2k2+ 2k− 1≡0 ⇔ 2k2 +7k≡ 0⇔ 2k+ 7≡ 0⇔ 10k+ 35≡ 0⇔ 33≡ 0

Тогда $p =11.$ Нетрудно проверить, что такое $p$ действительно подходит.

Ответ:

$p =11$

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

Задача 9#98619

Дано $n$ -значное число $A.$ Докажите, что найдётся такое натуральное $k,$ что число $2k$ имеет хотя бы $2n$ цифр, и в десятичной записи этого числа можно зачеркнуть не более, чем $n$ цифр с конца так, чтобы полученное число оканчивалось числом $A.$

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

Подсказка 1

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

Подсказка 2

Для решения задачи достаточно доказать, что существуют степени 2, дающие при делении на 10^(2n) остаток между A*10^n и (A+1)*10^n. Как искать такие степени? Что означает сформулированное утверждение на языке сравнений и показателей?

Подсказка 3

Докажите, что число 2 принадлежит к показателю 4*5^{m - 1} по модулю 5^m, и существует бесконечно много таких k, что 2^k сравнимо с r по модулю 10^{2n}. Выведите из этих двух утверждений решение задачи. Осталось лишь доказать эти два утверждения. Индукция вам в поможет.

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

Докажем, что для любого $r,$ кратного $22n$ и не кратного $5,$ существует бесконечно много таких $k,$ что $2k ≡ rmod 102n.$ Очевидно, достаточно найти такие $k,$ что $k 2n 2 ≡r mod5$ (поскольку $k 2n 2 ≡ r≡ 0mod 2$ при $k≥ 2n).$ Заметим, что число $2$ принадлежит к показателю $m− 1 4 ⋅5$ по модулю $m 5$ (то есть $4⋅5m−1 m 2 ≡1 mod5 ,$ но никакие меньшие степени $2$ не сравнимы с $1$ по этому модулю). Это утверждение несложно доказать по индукции: база $m ≤ 2$ проверяется непосредственно, а переход вытекает из формулы $5s s 4s 3s 2s s 2 − 1= (2 − 1)(2 + 2 + 2 +2 + 1)$ — если $s 2− 1$ делится на $2 5 ,$ то вторая скобка делится на $5,$ но не на $25,$ поэтому для делимости произведения на $m 5$ первая скобка должны делиться на $m−1 5 .$ Тем самым мы доказали, что все вычеты по модулю $m 5 ,$ не кратные $5,$ сравнимы со степенями двойки. При $n m= 2$ это даёт нам нужное утверждение.

Докажем теперь, что в условии задачи всегда можно зачеркнуть ровно $n$ цифр, то есть, что существуют степени $2,$ дающие при делении на $102n$ остаток между $A ⋅10n$ и $(A +1)⋅10n.$ Число $A⋅10n+ 22n$ является остатком степени $2$ (оно не кратно $5$ и кратно $22n).$ Оно попадает в нужный интервал, потому что $22n =4n <10n.$

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

Задача 10#99354

Даны два числа: $A =22n + 1$ и $B =22m + 1,$ где $m ⁄=n$ — натуральные числа. Найдите все возможные наибольшие общие делители $A$ и $B$ и докажите, что других нет.

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

Без ограничения общности можно полагать $n > m.$ Предположим, что $p$ — общий простой делитель данных чисел. Имеются сравнения

2n 2 ≡p −1

2m 2 ≡p − 1

Тогда имеем $ordp(2)|2m+1.$ Тогда имеем делимость $ordp(2)|2n,$ так как $n> m.$ Но это противоречит условию $22n ≡p −1.$ Таким образом, у данных чисел не может быть общих простых делителей, а потому они взаимно просты.

Ответ:

$1$

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

Задача 11#75630

Назовём многочлен $P(x)∈ ℤ[x] p$ перестановочным по простому модулю $p,$ если его значения дают все возможные остатки при делении на $p.$ Существует ли перестановочный по модулю $101$ многочлен степени $17?$

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

Подсказка 1

Давайте доказывать, что такой многочлен существует. Более того, давайте доказывать, что x^17 подходит. Как это можно сделать?

Подсказка 2

Для проверки достаточно показать, что сравнение a^17 = b ^17 бывает только при a = b. Как это можно сделать? Вспомните про первообразный корень и докажите это.

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

Докажем, что $x17$ — перестановочный многочлен. Для этого проверим, что $a17 ≡ b17 ⇔ a ≡b.$

Если $a≡ b,$ то утверждение очевидно.

Пусть $17 17 −117 a ≡ b ⇔ (ab ) ≡ 1.$ Пусть $g$ — первообразный корень по модулю 101. Тогда $−1 n ab ≡ g .$ Получаем систему:

{ 17n g100 ≡1 g ≡ 1

Тогда $gНОД(100,17n) ≡ 1.$ Так как $g$ — первообразный корень, то $НО Д(100,17n)= 100.$ Откуда получаем, что $100 | n.$ Тогда $ab−1 ≡ gn ≡ 1⇔ a≡ b.$

Тогда получаем, что $x17$ осуществляет биекцию $Z → Z , p p$ и, следовательно, является перестановочным.

Ответ: да

Интенсивы

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

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

Задача 12#82081

Рассмотрим все числа вида $10i− 10j$ при $0≤ j <i≤ 99.$ Сколько из них делятся на $1001?$

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

Подсказка 1

Для начала давайте поймëм, что 10 никак не помогает в делимости на 1001. Значит, можно рассматривать делимость 10^{i - j} - 1 на 1001.

Подсказка 2

Делимость на 1001 рассматривать тяжело. Вместо этого давайте поймëм, что 1001 = 7 • 11 • 13, и отдельно рассмотрим делимость на каждое из этих простых чисел.

Подсказка 3

Так, теперь мы пришли к простым числам. На этом этапе стоит вспомнить свойства показателей и понять, как с ними связано i - j.

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

Заметим, что $10i− 10j =10j(10i− j − 1).$ Ясно, что $10i−j$ делиться на $1001= 7⋅11⋅13$ никак не помогает. Следовательно, для делимости необходимо и достаточно, чтобы выполнялись следующие сравнения: $i−j i−j 10 ≡ 1 (mod 7),10 ≡ 1 (mod 11)$ и $i−j 10 ≡ 1 (mod 13).$ А это равносильно тому, что $i− j$ делится на $ord710,ord1110$ и $ord1310.$ Нетрудно посчитать, что $ord710= 6,ord1110= 2$ и $ord1310 =6.$ Таким образом, $i− j$ должно делиться на $6.$

Теперь найти все подходящие значения нетрудно. Понятно, что $i− j$ может равняться $6,12,...,96$ — всего $16$ вариантов. Рассмотрим уравнение $i− j = 6k,k∈ [1;16].$ Оно имеет следующие решения $(i,j):(6k,0),(6k+ 1,1),(6k+ 2,2),...,(6k+ 99− 6k,99− 6k).$ Всего $100− 6k,$ значит надо просуммировать это выражение по всем $k ∈[1;16].$ Итоговый ответ: $16⋅17- 1600− 6 ⋅ 2 =784.$

Ответ:

$784$

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

Задача 13#82082

Сколько делителей от $1$ до $200$ имеет число $2239− 1?$

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

Подсказка 1

Если совсем нет идей, то для начала стоит понять, что чётные делители можно отбросить.

Подсказка 2

Теперь давайте поймëм, что мы ищем такие n, для которых 2²³⁹ сравнимо с 1 по модулю n. Стоит подумать о показателе двойки по модулю n и о том, как он связан с 239.

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

Ясно, что на чётные делители это число делиться не может. А для любого нечетного числа $a$ если $2239 ≡1 (mod a),ord 2 a$ делит $239.$ Однако число $239$ — простое, то есть либо $orda2= 1,$ либо $239.$ Заметим, что по теореме Эйлера $φ(a) 2 ≡ 1 (mod a).$ Но $orda2≤φ(a)< a≤ 200 <239.$ Следовательно, $orda2= 1,$ откуда $a= 1.$

Ответ:

$1$

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

Задача 14#82083

Докажите, что при натуральном $n >1$ число $2n − 1$ не делится на $n.$

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

Подсказка 1

Тут стоит идти от противного. Ясно, что n нечëтное. Учитывая, что из двойки в степени n вычитается единица и (2, n) равно 1, есть смысл поискать противоречие, связанное с показателем.

Подсказка 2

Рассмотрите наименьший простой делитель n.

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

Предположим противное, пусть существует такое $n.$ Ясно, что оно нечётное. Выберем у $n$ наименьший простой делитель $p.$ На него делится $n 2 − 1,$ то есть $n$ делится и на $ordp2.$ Также на этот показатель делится $φ(p)= p− 1.$ Учитывая, что $ordp2 >1,$ понимаем, что у $ordp2$ есть простой делитель, меньший $p,$ поскольку $ordp2≤ p− 1.$ Следовательно, $n$ также делится на этот делитель, значит $p$ — не наименьший простой делитель, пришли к противоречию.

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

Задача 15#82084

Найдите все пары простых чисел $p$ и $q$ таких, что $(5p− 2p)(5q− 2q)..pq. .$

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

Подсказка 1

Для начала стоит откинуть случаи, когда первая сколка делится на p, либо вторая на q. В этом вам поможет МТФ.

Подсказка 2

Стало быть, теперь первая скобка делится на q, а вторая - на p.

Подсказка 3

Пусть p > q. Ясно, что (p, q - 1) = 1. Значит, 1 представляется в виде линейной комбинации p и q - 1. Попробуйте, используя это знания, провести некоторые манипуляции со сравнениями.

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

Предположим, что $5p− 2p$ кратно $p.$ По МТФ $5p− 2p ≡ 5− 2 =3 (mod p).$ Следовательно, $p= 3.$ Таким образом, $5p− 2p =3⋅3⋅13.$ То есть либо $q =3,$ либо $q = 13,$ либо $q$ делит $q q 5 − 2$ (аналогичная ситуация). Значит, в этом случае мы получили пары $(3,3),(3,13),(13,3).$

Пусть теперь $p$ не делит $p p 5 − 2,q$ не делит $q q 5 − 2 .$ Отсюда ясно, что $p p 5 − 2$ кратно $q q q,5 − 2$ кратно $p.$ Пусть $p >q.$ Ясно, что $(p,q − 1)= 1$ и, следовательно, существуют такие положительные $a$ и $b,$ что $ap− b(q − 1)= 1.$ Поскольку $(2,q)= (5,q)= 1,$ по МТФ имеем $q−1 q−1 5 ≡ 2 (mod q).$ По нашему предположению $p p 5 ≡ 2 (mod q),$ отсюда $ap ap 5 ≡ 2 (mod q).$ Последнее сравнение равносильно следующему: $b(q−1)+1 b(q−1)+1 5 ≡ 2 (mod q).$ Но в силу наших рассуждений $b(q−1)+1 b(q−1)+1 5 ≡5 (mod q),2 ≡2 (mod q).$ То есть $5 ≡2 (mod q),$ это возможно лишь при $q = 3,$ но этот случай сейчас не рассматривался.

Ответ:

$(3,3),(3,13),(13,3)$

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

Задача 16#82086

Найдите все упорядоченные тройки простых чисел $(p,q,r)$ таких, что

q .. r .. p .. p + 1.r,q + 1.p,r + 1.q

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

Подсказка 1

Для начала поймем могут ли быть равные числа среди p, q, r?

Подсказка 2

Правильно, не могут! Попробуем теперь доказать следующую лемму: если p,q,r — такие различные простые числа, что p делит q^r+1 и p > 2, то либо p − 1 кратно 2r, либо q^2 − 1 кратно p. Заметим, что из условия леммы следует, что q^r сравнимо с -1, но не сравнимо с 1 по модулю p. Что можно сделать с этим сравнением?

Подсказка 3

Верно! Надо возвести его в квадрат и получить, что q^(2r) сравнимо с 1 по модулю p. Что тогда можно сказать про ord(q) по модулю p?

Подсказка 4

Точно! Он делит 2r, но не делит r. Так как p простое, то какой вывод можно сделать?

Подсказка 5

Ага! либо (ord q по модулю p) = 2, либо (ord q по модулю p) = 2r. Если верно второе, то p− 1 кратно 2r, поэтому лемму доказали. Теперь остается ее применить и поразбирать случаи. Предположим, что p, q, r — нечетные. Что следует из того, что p - 1 делится на 2r?

Подсказка 6

Верно! 0 ≡ p^q + 1 ≡ 2, то есть r = 2, а значит, противоречие. Теперь пусть q^2 - 1 делится на p. Какое тогда неравенство можно написать на p и q?

Подсказка 7

Точно! Из того, что q^2 - 1 делится на p следует, что либо (q-1)/2, либо (q+1)/2 делится на p, а значит, q > (q+1)/2 ≥ p. Теперь легко получаем противоречие. Осталось только разобрать случай, когда одно из чисел равно 2 и вычислить два других.

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

Ясно, что $qr+ 1$ не кратно $q,$ а значит $p⁄= q.$ Аналогично $q ⁄= r$ и $r⁄=p,$ то есть $p,q$ и $r$ различные.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем теперь следующую лемму: если $p,q,r$ — такие различные простые числа, что $p$ делит $r q + 1$ и $p >2,$ то либо $p− 1$ кратно $2r,$ либо $2 q − 1$ кратно $p.$

Из условия леммы следует, что $r q$ сравнимо с $− 1$ по модулю $p,$ но не сравнимо с $1,$ поскольку $p> 2.$ Следовательно, $2r 2 q ≡ (− 1) ≡ 1 (mod p).$ Получаем, что $2r$ кратно $ordpq$ и $r$ не кратно $ordpq.$ Поскольку $r$ — простое, это возможно лишь когда $ordpq =2$ или $ordpq =2r.$ Если верно второе, то $p− 1$ кратно $2r.$ В первом же случае получим, что $2 q − 1$ кратно $p.$ Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Начнём решение со случая, когда $p,q$ и $r$ нечётны. Поскольку $p$ делит $qr+ 1,$ по лемме либо $p− 1$ кратно $2r,$ либо $q2− 1$ кратно $p.$ Но первый случай невозможен, поскольку сравнение $p≡ 1 (mod r)$ влечёт за собой сравнения $0≡ pq+1 ≡2 (mod r),$ то есть $r= 2,$ что противоречит нашему предположению. Следовательно, $p$ делит $q2− 1= (q − 1)(q+ 1).$ Простое число $p$ нечётно, a $q− 1$ и $q+ 1$ чётны. Значит, одно из чисел $q−21$ или $q+21$ кратно $p.$ Отсюда следует, что $p≤ q+21< q.$ Аналогично $q < r$ и $r< p,$ противоречие.

Значит, среди чисел есть хотя бы одна двойка. Поскольку при циклической перестановке ничего не изменится, можно положить, что $p =2.$ Теперь $r$ делит $2q+ 1,$ тогда по лемме либо $2q$ делит $r− 1,$ либо $22− 1 =3$ кратно $r.$ Но первый случай невозможен, поскольку $q$ делит $r2+ 1= (r− 1)(r +1)+ 2$ и $q >2.$ Следовательно, $3$ кратно $r.$ По условию $r2+ 1= 10$ кратно $q.$ Ранее мы заключили, что $q ⁄=p,$ откуда $q ⁄= 2,$ то есть $q =5.$

Ответ:

$p =2,q = 5,r= 3$

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

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

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

Задача 17#82087

Найдите остаток суммы всех выражений вида $ij,$ где $1 ≤i< j ≤ p− 1$ по простому модулю $p.$

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

У простого числа есть первообразный корень $g.$ Следовательно, каждый остаток в сумме можно заменить на $g$ в соответствующей степени, ведь нас интересует лишь остаток суммы при делении на $p.$ Но тогда сумму можно записать в следующем виде:

g(g2+ g3+...+gp−1)+g2(g3 +g4+ ...+ gp−1)+ ...+ gp−2⋅gp−1 = gp+1−-g3-+ gp+2−-g5+ ...+ g2p−2−-g2p−3-= g− 1 g− 1 g− 1

gp(g+ g2+...+gp−2)− (g3+ g5 +...+ g2p−3) = ----------------g− 1----------------

Мы получили дробь, которая является целой. Покажем, что она делится на $p,$ кроме некоторых случаев.

Предположим, что $g− 1$ не делится на $p.$ В этом случае достаточно доказать, что $p$ делит числитель дроби. Посмотрим на его первое слагаемое: $gp ≡g (mod p),$ а $g+ g2+...+gp−2$ — это сумма всех остатков при делении на $p,$ кроме $0$ и $1,$ то есть она сравнима с $− 1+ 2− 2+3 − 3+ ...= −1$ по модулю $p.$ Тогда всё слагаемое сравнимо с $− g.$ Докажем теперь, что $− g− (g3 +g5+ ...+ g2p−3)= − g2p−21−g g −1$ кратно $p.$

Если знаменатель $g2− 1$ делится на $p,$ то $g+ 1$ кратно $p$ (в этом случае $p$ не делит $g− 1$ ), откуда $g ≡−1 (mod p)$ и $g2 ≡ 1 (mod p).$ То есть либо $p =3,$ либо $p= 2$ (тогда $− 1≡ 1 (mod p)$ ). В первом случае остаток $p − 1,$ во втором — $0,$ потому что в сумме нет слагаемых. Иначе $g2− 1$ не делится на $p,$ а числитель делится, так как $g2p−1 = gp⋅gp−1 ≡ g⋅1≡ g (mod p).$ Следовательно, при $p >3$ остаток $0.$

Если же $g− 1$ делится на $p,$ то $g ≡ 1 (mod p),$ то есть $p =2.$ Этот случай уже рассмотрен.

Ответ:

$0$ при $p⁄= 3$ и $p− 1$ при $p= 3$

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

Задача 18#82088

Пусть $p$ и $q$ — простые, $q > 5.$ Известно, что $2p+ 3p$ делится на $q.$ Докажите, что $q > 2p.$

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

Предположим противное, пусть $q ≤2p.$ По условию $q >5,$ то есть $q$ — нечётное, а значит $q ≤2p− 1.$ Делимость $2p+ 3p$ на $q$ равносильна сравнению $p p 2 ≡− 3 (mod q).$ Возведём его в квадрат: $2p 2p 2 ≡ 3 (mod p).$ Далее запишем его следующим образом: $2p− q+1 q−1 2p−q+1 q− 1 2 ⋅2 ≡ 3 ⋅3 (mod q).$ После применения МТФ последнее сравнение превратится в $2p−q+1 2p−q+1 2 ≡3 (mod q).$ Следовательно,

2p− q+1 2p−q+1 p− q−1- p− q−1 p− q−1 p− q−1 3 − 2 = (3 2 − 2 2 )(3 2 + 2 2 )

кратно $q.$ Отсюда вытекают два случая.

Если первая скобка кратна $q,$ то $3p− q−21≡ 2p− q−12-(mod q).$ Также ранее мы выяснили, что $22p ≡32p.$ Таким образом, зная, что если $x x (a,b)= 1,a ≡b (mod m)$ и $y y a ≡ b (mod m),$ то $НОД(x,y) НОД(x,y) a ≡ b (mod m )$ получаем:

(2p,p− q−1) (2p,p− q−1) 2 2 ≡ 3 2 (mod q)

Осталось заметить, что $p− q−1- 2$ не делится на $p,$ потому что $0 < q−1 ≤p− 1 2$ по нашему предположению. Следовательно, этот НОД равен либо $1,$ либо $2.$ То есть либо $1≡ 0 (mod q),$ либо $5≡ 0 (mod q),$ но при $q > 5$ это невозможно.

Если вторая скобка кратна $q,$ то $3p− q−21≡ −2p− q−21(mod q).$ Домножим сравнение на $6q−21$ и получим: $2q−21⋅3p ≡ −3q−21⋅2p (mod q).$ Условие позволяет заменить в последнем сравнении $2p$ на $− 3p$ и получить следующее: $2q−21≡ 3q−21.$ Снова приходим к первой задаче, только в этом случае нужно посмотреть на $q−1 (2p, 2 )$ и аналогичным способом убедиться, что он может быть лишь $1$ или $2,$ что приводит к противоречию.

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

Задача 19#82089

Докажите, что $2$ является первообразным корнем любого простого числа вида $p= 4q +1,$ где $q$ — простое.

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

Пусть $ord2 =d, p$ тогда $d$ делит $p− 1= 4q.$ Поскольку $q$ — простое, задача сводится к рассмотрению случаев.

Если $d= 1,$ то $2≡ 1 (mod p),$ что невозможно.

Если $d= 2,$ то $4≡ 1 (mod p),$ то есть $p= 3,$ но $p> 3,$ противоречие.

Если $d= 4,$ то $16≡1 (mod p),$ откуда $p =3$ или $p= 5,$ но $p> 5,$ противоречие.

Случаи $d= q$ и $p =2q$ влекут за собой сравнение $2q 2 ≡ 1 (mod p).$ Но $2q p−1 2 =2 2 .$ То есть двойка — квадратичный вычет по модулю $p.$ Заметим, что при нечётном $q$ простое число $p$ имеет вид $8k+ 5$ (при $q =2$ число $p$ составное). Однако двойка не может быть квадратичным вычетом по простому модулю вида $8k+ 5,$ противоречие. Следовательно, $d= 4q,$ что и требовалось.

Теперь докажем, что двойка не может быть квадратичным вычетом по простому модулю $p$ вида $8k +5.$ Остатки $p−1 1,2,...,-2-$ при делении на $p$ будем называть положительными, а остальные — отрицательными. Умножим все положительные остатки на $2 :2,4,...,p − 3,p− 1.$ Пусть среди полученных чисел есть $x$ отрицательных остатков. Тогда с одной стороны произведение этих остатков сравнимо с $(−1)x ⋅(p−21)!$ по модулю $p,$ с другой стороны оно сравнимо с $p−1- 2 2 ⋅(p−21)!$ по модулю $p.$ Отсюда получаем, что $p−1 2-2-≡ (−1)x (mod p).$

Осталось заметить, что отрицательными будут лишь те, которые лежат между $p+21-$ и $p− 1$ (границы включены). Количество таких чисел равно верхней целой части от $p−41.$ При $p= 8k+ 5$ оно нечётно, то есть $2p−12-≡ (−1)x ≡ −1 (mod p).$ Следовательно, двойка — квадратичный невычет, доказано.

Ответ:

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

Задача 20#82090

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

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

Докажем индукцией по $n,$ что $ord n2= φ(3n)= 2⋅3n−1. 3$ Нетрудно убедиться, что $2$ — первообразный корень по модулю $3.$

Предположим, что утверждение верно для всех $k≤ n+ 1.$ Пусть $ord3n+12= d,$ тогда $n+1 n+1 n n φ(3 )= 3 − 3 = 2⋅3$ кратно $d.$ Ясно, что $d$ чётное, иначе $d 3$ не будет давать остаток $1$ при делении на $n+1 3 .$ То есть $a d= 2⋅3 .$ Заметим, что

a a−1 a−1 a−1 22⋅3 − 1= (22⋅3 − 1)(24⋅3 + 22⋅3 +1)

По предположению $v(22⋅3a−1 − 1)= a. 3$ Вторая же скобка делится на $3,$ но не делится на $9,$ поскольку $2⋅3a−1$ кратно $φ(9)= 6$ при $a ≥2$ (случаи, когда $a< 2$ можно рассмотреть отдельно). Таким образом, степень вхождения $3$ в $2⋅3a 2 − 1$ равна $a+ 1.$ Значит, для делимости на $n+1 3$ необходимо, чтобы $a$ было не меньше $n.$ Следовательно, $n ord3n+12= 2⋅3,$ что и требовалось.

Предыдущий раздел

Следующий раздел