Да се реши сравнението

[asdf]

Да се решат сравненията
[tex]x^2 \equiv -1 (mod 85)[/tex]
и
[tex]9x^{14} \equiv 1(mod 17)[/tex]
( не са система, а две отделни сравнения)
Предполагам, че не е нещо трудно, но в материала, който чета няма никакви примери, само теория и нещо не мога да зацепя как се решават задачки от този вид

[martin123456]

1
[tex]85=5.17[/tex] => [tex]x^2+1 \equiv 0 (mod 5)[/tex]=>[tex]x \equiv \pm 2 (mod 5)[/tex]
[tex]-1 \equiv 16 (mod 17)[/tex]=>[tex]x^2 \equiv 16 (mod 17)[/tex]=>[tex](x+4)(x-4) \equiv 0 (mod 17)[/tex]=>[tex]x \equiv \pm 4 (mod 17)[/tex]
значи [tex]x=17k \pm 4[/tex]
1) [tex]x=17k+4 \equiv \pm 2 (mod 5)[/tex]=>[tex]17k \equiv 3,4(mod 5)[/tex]=>[tex]k \equiv 2,4 (mod 5)[/tex]=>[tex]x=17(5s+2)+4 \equiv 38 (mod 85)[/tex]. аналогично и другите

[martin123456]

2
[tex]9x^{14} \equiv 1(mod 17)[/tex]
[tex]x^{16} \equiv 1 (mod 17)[/tex]
значи [tex]9x^{16} \equiv 9 (mod 17)[/tex], а от др страна е [tex]x^2[/tex]=>[tex]x^2 \equiv 9 (mod 17)[/tex]=>[tex](x+3)(x-3) \equiv 0 (mod 17)[/tex]=>[tex]x \equiv \pm 3 (mod 17)[/tex]

[asdf]

Изясниха ми се нещата, благодарско

[asdf]

Всъщност на втората задача, откъде идва [tex]x^{16} \equiv 1 (mod 17)[/tex] Като се опрости началното става [tex]x^{14} \equiv 2 (mod 17)[/tex]

[martin123456]

ами от т-мата на Ойлер или на ферма
малко съм пиян да се сетя
но от нея [tex](x,17)=1[/tex]=>[tex]x^{16} \equiv 1 (mod 17)[/tex]

[asdf]

Ау, да , от Ферма следва това, благодаря

[martin123456]

[nikko]

Как се решават задачи като втора.
Намирате примитивен корен по модул p, в случая 3 е примитивен корен по модул 17. Правите таблица на индексите
[tex]\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{n}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\
\hline
3^n mod 17&3&9&10&13&5&15&11&16&14&8&7&4&12&2&6&1\\
\hline\end{array}[/tex]
Индексирате сравнението, което става вече сравнение по модул [tex]\varphi(p)=p-1=16[/tex]

[tex]9x^{14} \equiv 1(\text{mod}\ 17)[/tex]

[tex]ind(9x^{14})\equiv ind(1)\equiv 16(\text{mod}\ 16)\Leftrightarrow ind(9)+14ind(x)\equiv 0(\text{mod}\ 16)\Leftrightarrow 2+14ind(x)\equiv0(\text{mod}\ 16)[/tex]
Ако [tex]y=ind(x)[/tex], то [tex]\Leftrightarrow 2+14y\equiv0(\text{mod}\ 16)\Leftrightarrow y\equiv1(\text{mod}\ 8)[/tex] и или индекса на x е 1 или 9 и от таблицата получаваме решението x?3 и x?14