Równanie modulo n

[squared]

Mam rozwiązać równanie:
\(\displaystyle{ 437 \cdot _{1007} x = 57\ \textrm{w} \ Z_{1007}}\)

Generalnie robiłem to tak jak mnie nauczono, czyli:
\(\displaystyle{ 437x + 1007 y = 57 \ \ \ x,y \in \ZZ}\)
Szukałem tych \(\displaystyle{ x,y}\). Wyszło mi, że \(\displaystyle{ 57 = -69 \cdot 437 + 30 \cdot 1007 \ \ \ NWD(a;n)=17}\).

I to prawie koniec powinien być. Nie zrozumiałem co dalej. Podobno mam wziąć obustronnie modulo \(\displaystyle{ n}\). No to wtedy \(\displaystyle{ 30 \cdot 1007}\) skreślam i co dalej? Mam z \(\displaystyle{ -69 \cdot 437}\) wziąć resztę z dzielenia przez \(\displaystyle{ n}\) i wtedy to jest szukany \(\displaystyle{ x}\)?
Mam też podane, że \(\displaystyle{ x=x_{0} + t \frac{n}{NWD(a;n)}}\). Gdzie \(\displaystyle{ x_{0}}\) to rozwiązanie z tego równania chyba po obliczeniu tej reszty. Nie wiem czy dobrze myślę, czy tak to powinno być. Nie czuję się zbyt mocny z tego tematu.

[Andreas]

Skąd się wzięło 57?
I co to jest \(\displaystyle{ a}\) i \(\displaystyle{ n}\)?

[squared]

Była pomyłka, \(\displaystyle{ 57}\) miało być po równa się. Sprawdź sobie, bo teraz jest wszystko prawidłowo zapisane i się zgadza.

\(\displaystyle{ a=437 \ \ \ \ n=1007}\) w tym zadaniu. Mam nadzieję, że teraz wszystko jasne.

[Andreas]

No to już obliczyłeś, twój \(\displaystyle{ x}\) to \(\displaystyle{ -69}\). W \(\displaystyle{ \ZZ_{1007}}\) to \(\displaystyle{ 1007-69=938}\).
\(\displaystyle{ 437 \cdot 938 \equiv 57 \ (\text{mod } 1007)}\)
Więc się zgadza.

[squared]

Czyli rozwiązaniem zawsze będzie ten współczynnik stojący przy danej liczbie - w tym przypadku przy \(\displaystyle{ 437}\)?

I nie \(\displaystyle{ x}\), tylko \(\displaystyle{ x_{0}=-69}\)
\(\displaystyle{ x=-69+t\frac{1007}{19}=-69+53 t \ \ \ t \in \ZZ}\)

ponieważ \(\displaystyle{ \text{NWD(1007;437)}=19}\) - w pierwszym poście się pomyliłem przy przepisywaniu.

[Andreas]

Rozwiązaniem jest liczba naturalna, nie współczynnik.

I nie \(\displaystyle{ x}\), tylko \(\displaystyle{ x_{0}=-69}\)
\(\displaystyle{ x=-69+t\frac{1007}{19}=-69+53 t \ \ \ t \in \ZZ}\)

Nie, x to 938. A \(\displaystyle{ -69=938}\) w \(\displaystyle{ \ZZ_{1007}}\). Jest tylko jeden taki \(\displaystyle{ x \in \ZZ_{1007}}\).

[squared]

Zawsze jest tylko jedno rozwiązanie takiego równania? Chyba nie skoro taką dziwną zależność dostałem na te x.

[Andreas]

Miałeś rację, może być więcej rozwiązań. Sorry za wprowadzanie w błąd.