Различия
Здесь показаны различия между двумя версиями данной страницы.
Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия Следующая версия Следующая версия справа и слева | ||
ent [2016/01/14 13:14] Уланский Евгений Алесандрович |
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$ | ||
Строка 840: | Строка 850: | ||
Пользуясь следствием 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\equiv 3^y\pmod{31}$. Мы можем это сделать, так как из самого условия задачи очевидно, что $x$ не делится на $31$, а значит сравним с одной (и только одной) из степеней первообразного корня (по следствию 13). Исходное сравнение теперь перепишется в виде |
+ | $$ 3^{17y}\equiv 3^{20}\pmod{31}.$$ | ||
+ | По следствию 12 это равносильно сравнению уже по модулю $\varphi(31)=30$ | ||
+ | $$17y\equiv 20\pmod{30}.$$ Решая это сравнение, находим $y\equiv 10\pmod{30}$, откуда $x\equiv 3^y\equiv -6\pmod{31}$. |