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