Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия Следующая версия Следующая версия справа и слева | ||
|
ent [2016/01/13 23:05] Уланский Евгений Алесандрович [Нахождение первообразных корней] |
ent [2016/01/14 20:57] Уланский Евгений Алесандрович [Решение сравнений при помощи первообразных корней] |
||
|---|---|---|---|
| Строка 834: | Строка 834: | ||
| Теперь проверим, что $(-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}$. | ||