Rozwiązywanie równań, kwestia implikacji, równoważności

[matinf]

Witam,

Przede wszystkim pierwsze pytanie to:

Mamy kongruencję:
\(\displaystyle{ x^{59}\equiv 604 (\mod 2013)}\)
I wiadomo, że \(\displaystyle{ (604, 2013) = 1}\)
A Euklidesa:
\(\displaystyle{ (x^{59}, 2013) = (x^{59} \mod 2013, 2013) = (604, 2013) = 1}\) Tutaj ok ?
I dalej od razu stwierdzam, że w takim razie \(\displaystyle{ (x, 2013) = 1}\). Gdyby było inaczej, to\(\displaystyle{ x^{59}}\) nie byłoby względnie pierwsze z \(\displaystyle{ 604}\). Tutaj ok ?

I można teraz wyprowadzić z funkcji Carmichela \(\displaystyle{ x^{60} \equiv 1 (\mod 2013)}\)
I jak widać, pracowałem na razie niezależnie do równości, którą mam rozwiązać. Idę więc dalej - ale to co otrzymałem dotychczas to:
\(\displaystyle{ x^{60} \equiv 1(\mod 2013)}\)
\(\displaystyle{ x^{59}\equiv 604 (\mod 2013)}\)
I stąd jest implikacja, że \(\displaystyle{ x^{60}\equiv 604x (\mod 2013)}\)
Dalej z przechodniości kongruencji, tym razem równoważność, bo to relacja równoważności mamy, że
\(\displaystyle{ 604x \equiv 1 (\mod 2013)}\)
I z tym ostatnim sobie poradzę już, ale ale. Czy ja wszystkie rozwiązania mam ? Bo niepokoi mnie ta implikacja, gdyby tam była równoważność, to był bym spokojny, ale mamy implikację - czy to nie ominie, niektórych rozwiązań ?

[bakala12]

Nie ominie, jednak wręcz przeciwnie, kandydatów na rozwiązanie przybędzie, i trzeba będzie ich na koniec sprawdzać czy rzeczywiście spełniają to co na początku założyłeś. Teraz dlaczego to jest dobrze.
Rozumujemy tak. Skoro \(\displaystyle{ x}\) jest rozwiązaniem, to musi spełniać to i to. I jeżeli jest implikacja to w drugą stronę nie musi być to prawda, tzn. jeżeli liczba spełnia to i to, to niekoniecznie musi być rozwiązaniem.
Mam nadzieję, że zrozumiałeś coś z tego bełkotu Jeśli nie, to spróbuję to bardziej formalnie wyjaśnić.

[matinf]

Dzięki!

Weźmy w takim razie: \(\displaystyle{ x^{98} \equiv99(\mod 125)}\)

Z algorytmu Euklidesa:
\(\displaystyle{ (x^{98} , 125) = 1 \Rightarrow (x, 125) = 1}\)
skoro tak, to:
\(\displaystyle{ x^{\phi(125)} = x^{100} \equiv1\pmod{125} \wedge x^{98} \equiv99(\mod 125) \Rightarrow x^2\equiv99 \pmod{125} \Rightarrow x^2 \equiv{99}\pmod{5} \Rightarrow x^2 \equiv{4}\pmod{5}}\)

Więc, \(\displaystyle{ 5|(x-2)(x+2)}\)
czyli jedna z liczb musi być równa pięć:
\(\displaystyle{ x\equiv{7,3}\pmod{5}}\)
W konsekwencji:
\(\displaystyle{ x\equiv{7,3}\pmod{125}}\)

I jak ?