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