równanie mod 23

wiosna · Post autor: **wiosna** » 21 lut 2009, o 14:26

Jak rozwiązać równanie \(\displaystyle{ x ^{7}=15 (mod 23)}\)?

XMaS11 · Post autor: **XMaS11** » 21 lut 2009, o 14:45

Można skorzystać z Małego Twierdzenia Fermata:
Dla każdego całkowitego \(\displaystyle{ x}\) zachodzi:
\(\displaystyle{ x^{22}=1 \ (mod23)}\)
W naszym przypadku wiemy też, że:
\(\displaystyle{ x^{21}=15^3 \ (mod23)}\)
Korzystając z tego, co napisałem wyżej dostajemy:
\(\displaystyle{ x \cdot 15^3=1 \ (mod23)}\)
No i to już nie jest problem.
Pozdrawiam.

Maciej87 · Post autor: **Maciej87** » 21 lut 2009, o 22:25

Warto też zauważyć że rozwiązanie pokazuje, że mamy dokładnie jeden pierwiastek- w ogólności może być ich więcej.