Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

Предыдущая версия справа и слева Предыдущая версия
Следующая версия
Предыдущая версия
Следующая версия Следующая версия справа и слева
ent [2016/01/14 20:52]
Уланский Евгений Алесандрович [Решение сравнений при помощи первообразных корней]
ent [2016/05/01 12:24]
Уланский Евгений Алесандрович
Строка 1: Строка 1:
 ======Элементы теории чисел====== ======Элементы теории чисел======
 [[ent2|Элементы теории чисел - дополнение]] [[ent2|Элементы теории чисел - дополнение]]
 +
 +=====Литература=====
 +
 +  - [[http://​lib.mexmat.ru/​books/​109507|Задачник О.\~Н.\~Василенко и А.\~И.\~Галочкина]]
 +  - [[http://​lib.mexmat.ru/​books/​3205|Задачник Н.\~Б.\~Алфутовой и А.\~В.\~Устинова]]
 +  - [[http://​lib.mexmat.ru/​books/​42525|Учебник Ю.\~В.\~Нестеренко]]
 +  - [[http://​lib.mexmat.ru/​books/​4639|Учебник И.\~М.\~Виноградова]]
 +  - [[http://​lib.mexmat.ru/​books/​66901|Учебник Ш.\~Х.\~Михеловича]]
 +  - [[http://​lib.mexmat.ru/​books/​4852|Учебник А.\~Я.\~Хинчина]]
 +
 =====Обозначения===== =====Обозначения=====
 $\mathbb{N}$ --- множество натуральных чисел $1, 2, 3, 4, 5, 6, \ldots$ $\mathbb{N}$ --- множество натуральных чисел $1, 2, 3, 4, 5, 6, \ldots$
Строка 841: Строка 851:
 Пользуясь следствием 13 можно решать сравнения некоторого вида. Допустим необходимо найти все решения сравнения Пользуясь следствием 13 можно решать сравнения некоторого вида. Допустим необходимо найти все решения сравнения
 $$x^{17}\equiv 5\pmod{31}.$$ $$x^{17}\equiv 5\pmod{31}.$$
-Мы знаем, что $3$ -- первообразный корень по модулю $31$. Все его степени от нулевой до двадцать девятой образуют приведённую систему вычетов по модулю $31$ (всего в ней $\varphi(31)=30$ элементов). Находим $3^5=243\equiv -5\pmod{31}$,​ следовательно $5\equiv 3^20\pmod{31}$.+Мы знаем, что $3$ -- первообразный корень по модулю $31$. Все его степени от нулевой до двадцать девятой образуют приведённую систему вычетов по модулю $31$ (всего в ней $\varphi(31)=30$ элементов). Находим $3^5=243\equiv -5\pmod{31}$,​ следовательно $5\equiv 3^{20}\pmod{31}$.
  
-Это связано с тем, что **//для любого первообразного корня//​** $g$ **//по любому простому модулю//​** $p$ **//​выполнено//​** $-1\equiv g^{\varphi(p-1)/2}$. В этом легко убедиться,​ ведь для первообразного корня всегда выполнено $\displaystyle\left(\frac{g}{p}\right)=-1$,​ а $\displaystyle\left(\frac{g}{p}\right)\equiv g^{p-1/​2}\pmod{p}$ по критерию Эйлера. При этом ни в какой другой степени от $0$ до $p-2$ первообразный корень не даст $-1$, поскольку по следствию 13 все его степени попарно не сравнимы по модулю $p$.+Это связано с тем, что **//для любого первообразного корня//​** $g$ **//по любому простому модулю//​** $p$ **//​выполнено//​** $-1\equiv g^{p-1/2}$. В этом легко убедиться,​ ведь для первообразного корня всегда выполнено $\displaystyle\left(\frac{g}{p}\right)=-1$,​ а $\displaystyle\left(\frac{g}{p}\right)\equiv g^{p-1/​2}\pmod{p}$ по критерию Эйлера. При этом ни в какой другой степени от $0$ до $p-2$ первообразный корень не даст $-1$, поскольку по следствию 13 все его степени попарно не сравнимы по модулю $p$.
  
 Положим теперь $x\equiv 3^y\pmod{31}$. Мы можем это сделать,​ так как из самого условия задачи очевидно,​ что $x$ не делится на $31$, а значит сравним с одной (и только одной) из степеней первообразного корня (по следствию 13). Исходное сравнение теперь перепишется в виде Положим теперь $x\equiv 3^y\pmod{31}$. Мы можем это сделать,​ так как из самого условия задачи очевидно,​ что $x$ не делится на $31$, а значит сравним с одной (и только одной) из степеней первообразного корня (по следствию 13). Исходное сравнение теперь перепишется в виде
 $$ 3^{17y}\equiv 3^{20}\pmod{31}.$$ $$ 3^{17y}\equiv 3^{20}\pmod{31}.$$
-По следствию 12 это равносильно сравнению уже по модулю $\varphi(31)=30$:+По следствию 12 это равносильно сравнению уже по модулю $\varphi(31)=30$
 $$17y\equiv 20\pmod{30}.$$ Решая это сравнение,​ находим $y\equiv 10\pmod{30}$,​ откуда $x\equiv 3^y\equiv -6\pmod{31}$. $$17y\equiv 20\pmod{30}.$$ Решая это сравнение,​ находим $y\equiv 10\pmod{30}$,​ откуда $x\equiv 3^y\equiv -6\pmod{31}$.