NWD - rozszerzony algorym Euklidesa

[Scoler]

Korzystając z rozszerzonego algorytmu Euklidesa mam znaleźć \(\displaystyle{ \NWD}\) .
\(\displaystyle{ 122x\equiv _{129} 5}\)

Dalej jest coś takiego:
\(\displaystyle{ \NWD(122,129)=1}\)

Rozumiem tyle, że muszę znaleźć \(\displaystyle{ \NWD}\) liczb \(\displaystyle{ 122}\) i \(\displaystyle{ 129}\) , ale co oznacza \(\displaystyle{ =1}\) ?
Mam zapisane, że liczy się to tak:

\(\displaystyle{ 129:122=1}\) reszta \(\displaystyle{ 7}\)
\(\displaystyle{ 122:7 = 17}\) reszta \(\displaystyle{ 3}\)
\(\displaystyle{ 7:3 = 2}\) reszta \(\displaystyle{ 1}\)
\(\displaystyle{ 3:1 = 3}\) reszta \(\displaystyle{ 0}\)

O co tu chodzi? Może coś źle zapisałem?

[koniak20]

NWD to największy wspólny dzielnik a że \(\displaystyle{ 122=2\cdot 61}\) a \(\displaystyle{ 129=3 \cdot 43}\)
Więc ich największy wspólny dzielnik to 1

[Janusz Tracz]

A nie masz przypadkiem rozwiązać kongruencji liniowej \(\displaystyle{ 122x\equiv5\bmod 129}\) która ma rozwiązania jako że \(\displaystyle{ 5:\mathbf{NWD}(122,129)\in\ZZ}\). Kongruencja taka jest równoważna równaniu diofantycznemu \(\displaystyle{ 122x-129y=5}\) i po to by je rozwiązać stosujesz rozszerzony algorytm Euklidesa. Zapisujemy \(\displaystyle{ 5}\) jako liniową kombinację \(\displaystyle{ 122}\) i \(\displaystyle{ 129}\) dostając \(\displaystyle{ -185 \cdot 122+175 \cdot 129=5}\) co pozwala znaleźć rozwiązania szczególne i wyznaczyć rozwiązania ogólne \(\displaystyle{ x=-185+129n}\) dla \(\displaystyle{ n\in\NN}\) no i jeszcze można to zapisać ładniej że \(\displaystyle{ x=73+129k}\) gdzie \(\displaystyle{ k\in\NN}\). Problemem w takich zadaniach jest zależnie liniowej kombinacji ale można to zrobić z rozszerzonego algorytmu Euklidesa cofając się z tym rozpisywaniem. Wiesz że

\(\displaystyle{ 129=122+7}\)

\(\displaystyle{ 122=17 \cdot 7+3}\)

\(\displaystyle{ 7=3 \cdot 2+1}\)

Teraz odwrotnie mamy

\(\displaystyle{ 1=7-3 \cdot 2=7-2 \cdot \left( 122-17 \cdot 7\right)=...}\)

Gdy wykorzystasz wszystkie reszty to dostaniesz liniową kombinację dla \(\displaystyle{ 1}\) potem tylko mnożysz przez \(\displaystyle{ 5}\) i koniec

[Scoler]

Dalej za bardzo tego nie ogarniam.

Jest równanie modularne postaci \(\displaystyle{ ax\equiv _{n}b}\)
\(\displaystyle{ a\equivb(mod n)\Leftrightarrow n|a-b}\)

Czyli \(\displaystyle{ 129|122x-5}\). To oznacza, że \(\displaystyle{ 129}\) jest dzielnikiem \(\displaystyle{ 122x-5}\).
Skoro \(\displaystyle{ 129}\) jest dzielnikiem \(\displaystyle{ 122x-5}\) to \(\displaystyle{ \exists _{k\in \mathbb{Z}} 122x-5 = 129k}\)

\(\displaystyle{ 122x-5=129k}\) mogę zapisać jako \(\displaystyle{ 122x-129k=5}\)

Teraz zapisuje \(\displaystyle{ 5}\) jako liniową kombinację \(\displaystyle{ 122}\) i \(\displaystyle{ 129}\).
\(\displaystyle{ 5*(-37)*122 + 35*7 * 129 = 5}\)

Nie ogarniam co tu się w ogóle dzieje i po co się takie coś rozwiązuje.

[Janusz Tracz]

Czyli \(\displaystyle{ 129|122x-5}\). To oznacza, że \(\displaystyle{ 129}\)jest dzielnikiem \(\displaystyle{ 122x-5}\).
Skoro \(\displaystyle{ 129}\) jest dzielnikiem \(\displaystyle{ 122x-5 to \exists _{k\in \mathbb{Z}} 122x-5 = 129k}\)

Tak. Zauważ że tak samo napisałem we wcześniejszym poście. Sprowadziłeś równanie modulo do równania diofantycznego (czeli takiego w liczbach całkowitych).

mogę zapisać jako \(\displaystyle{ 122x-129k=5}\)

Tak u mnie to było \(\displaystyle{ 122x-129y=5}\). Mniejsza o oznaczanie ważne jest to że \(\displaystyle{ x,y\in\NN}\)

Teraz zapisuje \(\displaystyle{ 5}\) jako liniową kombinację \(\displaystyle{ 122}\) i \(\displaystyle{ 129}\).
\(\displaystyle{ 5*(-37)*122 + 35*7 * 129 = 5}\)

To własnie jest konsekwencja rozszerzonego algorytmu Euklidesa. Ponieważ poszukujesz rozwiązań równania \(\displaystyle{ {\red{122}\blue{x}-\red{129}\blue{k}}=5}\) a udało Ci się pokazać że \(\displaystyle{ {\blue{5} \cdot \blue{(-37)} \cdot \red{122} + \blue{35} \cdot \blue{7} \cdot \red{129} }= 5}\). To zgodzisz się zapewne że znalazłeś jedno rozwiązanie jakim jest \(\displaystyle{ x=-37 \cdot 5}\) i \(\displaystyle{ k=35 \cdot 7}\). W szczególności interesuję Cie \(\displaystyle{ x}\) w postaci ogólne może to być rozwiązanie szczególne i każde jego przesunięcie o wartość mugolu stąd \(\displaystyle{ x=-185+129n}\). No ale zwykło się pisać to w takiej formie \(\displaystyle{ x=-185+2 \cdot 129+129(n-2)=73+129n^{*}}\) gdzie \(\displaystyle{ n^{*}\in\NN}\). Można teraz sprawdzić to rozwiązanie czy rzeczywiście spełnia równanie.

\(\displaystyle{ 122 \cdot (73+129n)=122 \cdot 73+122 \cdot 129n\equiv 122\cdot 73\bmod 129}\)

No i dalej

\(\displaystyle{ 122\cdot 73\equiv 5\bmod 129}\) Czyli faktycznie \(\displaystyle{ 122\cdot (73+129n)\equiv 5\bmod 129}\)