kongruencja krok po kroku

[marvell]

\(\displaystyle{ 3x\equiv 59(mod100)}\)
\(\displaystyle{ a'\cdot x \equiv b(moda)}\)
Jak rozwiązać taką kongruencję? Nie mogę tego jakoś załapać.



w algorytmie przyjąłem takie oznaczenia:
a, a', s, s', t, t', q

wychodzi że nwd(a',a)=1
s=1

Co dalej z tym zrobić?

[norwimaj]

Nie wiem, czy dobrze rozumiem pytanie. Chcesz rozwiązać taką kongruencję?
\(\displaystyle{ 3x\equiv 59 \pmod{100}}\)

Za pomocą algorytmu Euklidesa można zapisać \(\displaystyle{ 3x-59=100y}\), jeśli \(\displaystyle{ \mathrm{NWD}(100,3)|59}\).

Zapisujemy algorytm Euklidesa:
\(\displaystyle{ 100 = 33\cdot3+1}\).

Wyszedł wyjątkowo krótki. Teraz zaczynamy od ostatniej równości i wyznaczamy z niej \(\displaystyle{ 1}\):
\(\displaystyle{ 1=100-33\cdot3}\). Tak przechodzimy od ostatniej równości aż do pierwszej, na końcu otrzymując zapis \(\displaystyle{ \mathrm{NWD}(100,3)}\) jako kombinację liniową \(\displaystyle{ 100}\) i \(\displaystyle{ 3}\).

Teraz mnożymy otrzymaną równość przez \(\displaystyle{ 59}\):
\(\displaystyle{ 59 =59\cdot100-1947\cdot3}\).

Stąd otrzymujemy rozwiązanie szczególne (w liczbach całkowitych) równania \(\displaystyle{ 3x-59=100y}\):
\(\displaystyle{ \begin{cases}x=-1947\\y=-59\end{cases}}\).

Rozwiązaniem ogólnym jest
\(\displaystyle{ \begin{cases}x=-1947+100t\\y=-59+3t\end{cases}}\).

Rozwiązaniem modulo \(\displaystyle{ 100}\) jest \(\displaystyle{ x=-47=53}\).

Niestety ponieważ algorytm Euklidesa był tutaj bardzo krótki, to to rozwiązanie nie oddaje istoty rzeczy.

[marvell]

Hmm, a mógłbyś jeszcze zrobić np ten przykład? Tutaj algorytm jest dłuższy.

\(\displaystyle{ 99x\equiv 1(mod13)}\)

[norwimaj]

\(\displaystyle{ 99=7\cdot13+8}\)
\(\displaystyle{ 13=8+5}\)
\(\displaystyle{ 8=5+3}\)
\(\displaystyle{ 5=3+2}\)
\(\displaystyle{ 3=2+1}\)

I teraz od końca:
\(\displaystyle{ 1=3-2}\).
Podstawiamy \(\displaystyle{ 2}\) z przedostatniej równości w algorytmie:
\(\displaystyle{ 1=3-(5-3)=2\cdot3-5}\).
Zauważ że nie wymnażam wszystkiego co się da, tylko trzymam cały czas kombinację odpowiednich liczb. Teraz podstawiamy 3, potem 5 itd.:
\(\displaystyle{ 1=2\cdot3-5=2(8-5)-5=2\cdot8-3\cdot5=2\cdot8-3(13-8)=5\cdot8-3\cdot13=5(99-7\cdot13)-3\cdot13=5\cdot99-38\cdot13}\).

Otrzymaliśmy \(\displaystyle{ 1=5\cdot99-38\cdot13}\). Zatem rozwiązaniem równania \(\displaystyle{ 99x-1=13y}\) jest na przykład \(\displaystyle{ x=5, y=38}\). Zatem rozwiązaniem kongruencji jest \(\displaystyle{ x=5}\).