równania kongruencyjne

[tukan]

Witam,

Przede wszystkim pierwsze pytanie to:

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

I można teraz wyprowadzić z funkcji Carmichela \(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:
\(x^{60} \equiv 1(\mod 2013)\)
\(x^{59}\equiv 604 (\mod 2013)\)
I stąd jest implikacja, że \(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
\(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ń ?

[Crazy Driver]

Jeśli chodzi o rozumowanie, wg mnie wszystko jest OK. (Poza może językiem, bo nie mamy tu do czynienia z ,,relacją równoważności"). Przyjrzyjmy się rozumowaniu i konsekwencjom wynikania pewnych kongruencji z innych, ale tylko w jedną stronę. \(x\) jest taką liczbą, że \(x^{60}\equiv1\pmod{2013}\) i \(x^{59}\equiv604\pmod{2013}\). Skoro zachodzi \(x^{59}\equiv604\pmod{2013}\), to także \(x^{60}\equiv604x\pmod{2013}\). Skoro \(x^{60}\equiv1\pmod{2013}\) i \(x^{60}\equiv604x\pmod{2013}\), to \(604x\equiv1\pmod{2013}\). To oznacza, że ostatnia kongruencja jest warunkiem koniecznym dla naszej liczby \(x\). Niczego więc nie stracimy, wręcz przeciwnie, może się okazać, że mamy nadmiar. Wiemy bowiem, że każda liczba spełniająca warunki początkowe, spełnia ten ostatni. Ale nie mamy już pewności, czy każda spełniająca ostatni będzie spełniać początkowe.

[tukan]

Ok, faktycznie to jest tak, że:
\(x^{59}\equiv604\pmod{2013}\wedge x^{60}\equiv1\pmod{2013} \So x^{60}\equiv604x\pmod{2013} \So 1\equiv604x\pmod{2013}\)

Mamy, \(p \So q\)

Wtedy \(q\) jest warunkiem koniecznym. Czyli żeby \(x\) spełniał to równanie, musi spełniać warunek konieczny, a więc
właśnie tamtą. I teraz się zgadzam, że wyłapiemy ich (przy pechu) za dużo. I jak się pozbyć tego za dużo ?

Tzn sytuacja jest taka:

Mamy to dokończyć z algorytmu Euklidesa - znajdując odwrotność. Jak przemnożymy przez tą odwrotność, to dostaniemy wynik postaci \(x\equiv...\). A tego oczekujemy. I teraz jak mogę sprawdzić każdy z wyników czy spełnia "pierwotne" wymagania ?

Warunek konieczny spełnia - czyli wszystkie iksy które potrzebowałem mam.

[tukan]

PS - to się nazywa metoda starożytnych ?

[Crazy Driver]

Jakie masz te wyniki? I co ma się nazywać metodą starożytnych?

[tukan]

No właśnie muszę sobie odświeżyć algorytm euklidesa rozserzony. Jak policzę to podam wynik, ale nie wiem kiedy to nastąpi.

Ale wynik będzie przecież jeden - znajdę jedną odwrotność, pomnożę razy nią i to wszystko.

[Crazy Driver]

Owszem. Jeśli więc istnieje \(x\) spełniający wyjściową kongruencję, to \(x=604^{-1}\bmod{2013}\).

[tukan]

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

Z algorytmu Euklidesa:
\((x^{98} , 125) = 1 \Rightarrow (x, 125) = 1\)
skoro tak, to:
\(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, \(5|(x-2)(x+2)\)
czyli jedna z liczb musi być równa pięć:
\(x\equiv{7,3}\pmod{5}\)
W konsekwencji:
\(x\equiv{7,3}\pmod{125}\)

I jak ?