Различия
Здесь показаны различия между двумя версиями данной страницы.
Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия Следующая версия Следующая версия справа и слева | ||
ent [2016/01/13 23:05] Уланский Евгений Алесандрович [Нахождение первообразных корней] |
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$ | ||
Строка 834: | Строка 844: | ||
Теперь проверим, что $(-2)^{22}\not\equiv 1\pmod{23^2}$. Это действительно так, поскольку | Теперь проверим, что $(-2)^{22}\not\equiv 1\pmod{23^2}$. Это действительно так, поскольку | ||
$$(-2)^{22}-1=2^{22}-1=(2^{11}-1)(2^{11}+1)=2047\cdot 2049,$$ но $2047=23\cdot 89$, а значит, во-первых, $23$ не делит $2049$, а во-вторых, $23^2$ не делит $(-2)^{22}-1$. Это означает, что $-2$ является первообразным корнем и по модулю $23^2$. Но тогда число $23^2-2=527$ будет нечётным первообразным корнем по модулю $23^2$, а значит и по модулю $2\cdot 23^{19}$. | $$(-2)^{22}-1=2^{22}-1=(2^{11}-1)(2^{11}+1)=2047\cdot 2049,$$ но $2047=23\cdot 89$, а значит, во-первых, $23$ не делит $2049$, а во-вторых, $23^2$ не делит $(-2)^{22}-1$. Это означает, что $-2$ является первообразным корнем и по модулю $23^2$. Но тогда число $23^2-2=527$ будет нечётным первообразным корнем по модулю $23^2$, а значит и по модулю $2\cdot 23^{19}$. | ||
+ | |||
+ | |||
+ | ====Решение сравнений при помощи первообразных корней==== | ||
+ | |||
+ | |||
+ | Пользуясь следствием 13 можно решать сравнения некоторого вида. Допустим необходимо найти все решения сравнения | ||
+ | $$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}$. | ||
+ | |||
+ | Это связано с тем, что **//для любого первообразного корня//** $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). Исходное сравнение теперь перепишется в виде | ||
+ | $$ 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}$. |