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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#127166

Покажите, что при всех натуральных $a,n> 1$ число $φ(an − 1)$ делится на $n$ .

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

Рассмотрим модуль $m= an− 1.$ Заметим, что:

n НОД(a − 1,a)= НОД (1,a)= 1

Значит, применима теорема Эйлера $aφ(m) ≡ 1 (mod m).$

С другой стороны $ordm a= n,$ так как при $k <n$ имеем $ak < an− 1.$ Тогда получаем, что $n$ делит $φ(an− 1),$ что и требовалось.

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

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

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

Задача 2#127175

Найдите все натуральные $n,$ для которых числа $n$ и $2n− 1$ имеют один и тот же набор простых делителей.

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

Подсказка 1.

Рассмотрите простой делитель p у числа n. Как можно использовать, что 2ⁿ−1 делится на p?

Подсказка 2.

Правильно! Ввести показатель и получить условия на него.

Подсказка 3.

Получаем, что n и p−1 делятся на этот показатель, а дальше непонятно, что делать... Было бы отлично, если бы n и p−1 были взаимно просты.

Подсказка 4.

Воспользуйтесь принципом крайнего на стадии выбора p.

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

Очевидно, что $n = 1$ подходит. Пусть теперь $n≥ 2,$ рассмотрим минимальный простой делитель $p$ числа $n.$ Пусть $ord 2= s. p$ Тогда $φ(p)$ делится на $s,$ то есть $p− 1$ делится на $s.$ По условию $n 2 − 1$ делится на $p,$ значит, $n$ делится на $s.$ Заметим, что $(n,p− 1)= 1,$ так как $p$ — минимальный простой делитель $n.$ Отсюда получаем, что $s= 1,$ значит, $1 2 − 1= 1$ делится на $p.$ Получаем противоречие, значит, таких $n≥ 2$ не существует.

Ответ:

$n =1$

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

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

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

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

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

Задача 5#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$ тоже пробегают.

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

Задача 6#97875

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

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

Подсказка 1

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

Подсказка 2

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

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

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

Ответ:

Нет

Курсы

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

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

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

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

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

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

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

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

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

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

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

Интенсивы

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

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

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

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

Задача 13#122836

Пусть $ord a= d , m 1$ $ord b= d , m 2$ и $(d ,d )= 1. 1 2$ Докажите, что $ord ab= dd . m 1 2$

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

Заметим, что $(ab)d1d2 ≡ 1, m$ поэтому $ord ab= kl=d, m$ причем $k|d 1$ и $l|d , 2$ так как $d|d d. 1 2$ Кроме того, $(k,l)=1.$ Возведем сравнение $kl (ab) ≡m 1$ в степень $d1 k .$ Тогда получим

kld1 kld1 ld (a )k ⋅(b )k ≡m b 1 ≡m 1

Тогда $d |ld , 2 1$ следовательно, $d |l, 2$ так как $(d ,d )= 1. 1 2$ Таким образом, $d|l 2$ и $l|d , 2$ следовательно, $l=d . 2$ Аналогично, $k =d . 1$

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

Задача 14#122849

Докажите, что для любого делителя $d$ числа $p − 1$ существует натуральное число $a$ такое, что $ord a= d. p$

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

Пусть $g$ — первообразный корень. Рассмотрим $gn,$ где $n = p−1. d$ Предположим, что $(gn)l ≡ 1. p$ Тогда $(p− 1) | nl.$ Если $p− 1= nl,$ то, очевидно, $l$ — показатель. Тогда $n p−1 ordpg = n =d.$

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

Задача 15#122855

(a) Докажите, что существует ровно $φ(p − 1)$ вычетов, являющихся первообразными корнями по модулю $p;$

(b) Докажите, что любого делителя $d$ числа $p− 1$ существует ровно $φ(d)$ вычетов $a$ таких, что $ordpa= d.$

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

(a) Пусть $g$ — первообразный корень. Тогда все остальные первообразные корни имеют вид $x g .$ Предположим, что $(x,p− 1)= d> 1.$ Тогда $x(p− 1)∕d (g ) ≡p 1,$ причем $p−1 d <p− 1,$ откуда $x g$ — не первообразный корень.

Пусть теперь для некоторого $x$ имеем $xl (g )≡p 1.$ Тогда $(p − 1) | xl.$ Если теперь $x$ взаимно просто с $p− 1,$ то очевидно, что $l= p− 1$ — показатель $x g.$ Итак, $x g$ является первообразным корнем тогда и только тогда, когда $(x,p− 1)= 1,$ а потому количество первообразных корней равно количеству подходящих $x,$ то есть $φ(p− 1).$

(b) Пусть $g$ — первообразный корень. Любой вычет имеет вид $x g .$ Попробуем найти критерий того, что $k ordpg = d,$ где $d | (p− 1).$ Пусть $p− 1= xd$ и $k d (g ) ≡p 1.$ Тогда $(p− 1) | kd,$ то есть $xd | kd,$ тогда $x | k.$ Пусть $k =xl.$ Предположим, что $(l,d)= 1.$ Тогда $(gxl)y ≡p 1,$ и получае, что $d | xly,$ откуда $d | y.$ Тогда $y ≥ d,$ поэтому показатель не меньше $d,$ а, с другой стороны, степень $d$ дает остаток 1.

Предположим, что $(l,d)= t>1.$ Тогда $(gxl)d∕t ≡p 1,$ а потому $d$ не может являться показателем. Итак, $ordpgk = d$ равносильно $k =xl$ и $(l,d)= 1.$ Чтобы подсчитать количество подходящих вычетов, достаточно найти количество чисел взаимно простых с $d.$ Это в точности $φ(d).$

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

Задача 16#122857

Дано простое число $p$ и натуральное $i< p− 1.$ Докажите, что

i i i 1 + 2+ ...+ (p− 1) ≡ 0 (mod p)

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

Пусть $g$ — первообразный корень. Заметим, что $1i+ ...+ (p − 1)i ≡ (g0)i+ ...+ (gp−2)i, p$ так как любой вычет — степень первообразного корня. Считаем сумму геометрической прогрессии:

(gi)p−1− 1 (g0)i+ ...+ (gp−2)i ≡p--gi−-1--

Знаменатель не делится на $p,$ так как $i< p− 1.$ Числитель делится на $p.$ Тогда и исходное число делится на $p,$ что и требовалось.

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

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

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

Задача 17#127180

Найдите все натуральные $n$ такие, что число $3n − 2n− 1$ является квадратом целого числа.

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

Подсказка 1.

Приравняв выражение к x², получаем уравнение в натуральных числах. Какой приём зачастую спасает в таких ситуациях?

Подсказка 2.

Разложение на множители! Оставляйте в левой части разности, которые потенциально могут разложиться на скобочки, и постарайтесь вывести как можно больше условий.

Подсказка 3.

Из разложения 3ⁿ−2ⁿ выведите, что n — степень двойки, предположив, что есть простой нечётный делитель.

Подсказка 4.

Теперь уже хочется получать противоречие со степенью вхождения двойки в разные части уравнения. Для начала найдите степень вхождения двойки в 3ⁿ−1.

Подсказка 5.

Изучите степень вхождения двойки в x, рассмотрев разложение 3ⁿ−x².

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

Пусть $3n− 2n = x2+ 1.$ Предположим, что у $n$ есть некоторый нечетный простой делитель $p.$ Тогда

2 n n p p x +1= 3 − 2 = t(3 − 2).

При этом $3p− 2p ≡3 (mod 4).$ Тогда у этого числа есть простой делитель $q = 4k+ 3,$ иначе $3p− 2p ≡ 1 (mod 4).$ Но такого не может быть, так как тогда $x2 ≡− 1 (mod q);$ $x4 ≡ 1 (mod q).$ Тогда если $ordqx$ = $s$ : $s$ является делителем 4, но не является делителем 2. Тогда $s= 4$ и $φ(q)=q− 1= 4k+ 2$ делится на $s= 4$ — противоречие. Значит, $n =2s$ для некоторого натурального $s.$ Тогда

2s 2 2s−1 2s− 1 2s 3 − x = (3 − x)(3 +x)= 2 +1.

Рассмотрим произвольный простой делитель $p$ числа $22s + 1$ . Тогда $22s ≡− 1 (mod p),$ а $22s+1 ≡1 (mod p).$ То есть показатель 2 по модулю $p$ делит $22s+1,$ но не делит $22s.$ Тогда он равен $2s+1,$ откуда $p≡ 1 (mod 2s+1).$ Тогда обе скобки $32s−1 − x$ и $32s−1 +x$ сравнимы с 1 по модулю $22s+1,$ откуда

2s−1 2s−1 3 + x− 3 + x= 2x

делится на $2s+1,$ то есть $x2$ делится на $22s.$ С другой стороны

3n− 1= 32s − 1= (32s−1 + 1)(32s−2 + 1)...(32+ 1)(32− 1)= 2s+2(2l+1),

то есть $v2(3n − 1)= s+ 2,$ что меньше чем $2s$ при $s≥ 3.$ Тогда при $s≥ 3$ имеем

v2(3n− 2n − 1)= s+ 2= 2v2(x)≥2s,

откуда $s≤ 2$ — противоречие. Осталось лишь проверить, что $n= 1,2,4$ подходят.

Ответ:

$n =1,2,4$

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

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

Ответ: да

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

Задача 19#75801

(a) Докажите, что многочлен $2016 x − 1$ раскладывается над $𝔽2017$ в произведение нескольких многочленов вида $7 x − a$ для $a ∈𝔽2017;$

(b) Можно ли натуральные числа $1,2...,2016$ можно разбить на группы по $7$ так, чтобы сумма чисел в каждой семерке делилать на $2017?$

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

(a) Рассмотрим все возможные ненулевые вычеты по модулю $2017.$ Пусть $g$ — первообразный корень. Тогда эти вычеты имеют вид $1 2016 g ,...,g .$ Возведем их в $7$ степень. Тогда получим набор $7 1 7 2016 (g ),...,(g) .$ Заметим, что $2016$ делится на $7,$ и частное равно $288.$ Тогда легко видеть, что $7 ordpg = 288.$ Из этого получаем, что сравнение $7 x − a≡p 0$ имеет решения $r r+288 r+6⋅288 g,g ,...,g$ для $7r g ≡p a.$ Таким образом, все решения сравнения $2016 x − 1≡p 0$ являются решениями одного из сравнений вида $7 x − a≡p 0,$ откуда вытекает требуемое.

(b) Будем воспринимать данный набор чисел, как набор ненулевых остатков по модулю $2017.$ Так как число $2017$ — простое, то существует первообразный корень по модулю $2017.$ Пусть $y$ — некоторый первообразный корень по модулю $2017.$ Пусть $t≡y288 (mod 2017).$ Заметим, что $t7− 1 ≡0 (mod 2017)$ — по малой теореме Ферма. Преобразуем это сравнение:

t7− 1 ≡0 (mod 2017)

(t− 1)(t6+ t5+ t4+t3+ t2 +t+ 1)≡0 (mod 2017)

Заметим, что $t⁄≡ 1 (mod 2017),$ так как $y$ — первообразный корень. Это значит, что $6 5 4 3 2 t +t + t+ t +t + t+1≡ 0 (mod 2017).$

Тогда разделим все числа на $288$ групп вида $2 3 4 5 6 a,at,at ,at,at,at,at,$ где $a$ некоторый ненулевой остаток по модулю $2017.$ Проверим, что сумма этих чисел делится на $2017 :$

a+ at+at2+ at3+ at4 +at5+at6 = a(1+ t+ t2+ t3+t4+ t5+ t6)≡ 0 (mod 2017)

Теперь покажем, что все числа различны. Допустим, что два числа совпали внутри группы. Тогда имеем

atm ≡ atn (mod 2017)

a(tm − tn)≡ 0 (mod 2017)

Тогда получаем, что $m n t ≡ t (mod 2017).$ Будем считать, что $m ≥n.$ Тогда, так как $2017$ — простое, имеем $m−n t ≡1 (mod 2017).$ При этом $m,n< 7,$ тогда $(m−n,7) t ≡ 1 (mod 2017).$ Так как $7$ — простое, то $t≡ 1 (mod 2017),$ но это противоречит тому, что $y$ первообразный корень.

Допустим, теперь, что числа из разных групп совпали. Это эквивалентно сравнению $axm ≡bxn (mod 2017).$ Но тогда мы получаем, что $b≡ axm−n (mod 2017),$ то есть $b$ — число из группы $a,at,at2,at3,at4,at5,at6,$ однако мы предполагали, что числа из разных групп — противоречие.

Итак, мы получили разбиение, требуемое условием задачи.

Ответ:

$b)$ Да, можно

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

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

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

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