Kongruencja, jak się za to zabrać?

[Lukassz]

Witajcie, mam problem z kongruencjami. Nie wiem jak się zabrać za przykład. Czytałem, że trzeba użyć rozszerzonego algorytmu euklidesa, ale nie potrafię zrozumieć zapisów na wikipedii.

\(\displaystyle{ 9x\equiv 9 \pmod{25}}\)

[mol_ksiazkowy]

mam problem z kongruencjami.

Jesli \(\displaystyle{ 9(x-1)}\) dzieli sie przez 25, to \(\displaystyle{ x-1}\) tez. stad wynik: \(\displaystyle{ x \equiv 1 \ (mod \ 25)}\)

[Lukassz]

Ok, ale jak się do tego zabrać jeżeli miałbym skorzystać z algorytmu euklidesa? Co jeżeli zamiast \(\displaystyle{ 9x}\) bylo \(\displaystyle{ 8x}\)

[Premislav]

Co jeżeli zamiast\(\displaystyle{ 9x}\) bylo \(\displaystyle{ 8x}\)

Wtedy można by np. pomnożyć przez \(\displaystyle{ 19}\) stronami i zredukować wielokrotności \(\displaystyle{ 25}\) po obu stronach, co dałoby bodajże \(\displaystyle{ 2x\equiv 21 \pmod{25}}\), następnie pomnożyć stronami przez \(\displaystyle{ 13}\) i masz \(\displaystyle{ x\equiv 23\pmod{25}}\) (pewnie można szybciej, ale wcześnie jest). Ogólnie często można zgadnąć, że warto przez coś pomnożyć kongruencję/coś dodać stronami/odjąć stronami, ale chyba nie o to pytałeś.
Otóż weźmy ten przypadek równania \(\displaystyle{ 8x\equiv 9\pmod{25}}\). Ponieważ \(\displaystyle{ (8,25)=1}\), więc istnieje takie \(\displaystyle{ 0<q<25}\), że \(\displaystyle{ 8q\equiv1\pmod{25}}\). Znajdujemy je posiłkując się algorytmem Euklidesa dla \(\displaystyle{ 8}\) i \(\displaystyle{ 25}\). \(\displaystyle{ 25=3 \cdot 8+1}\) (ludzie z UWr, zróbcie przysługę pierwszorocznym z matmy i zabierzcie KiERP B Sz.P. Doktorowi Galowi i Sz.P.Doktorowi Mincerowi) Przerzucając \(\displaystyle{ 25}\) na prawą stronę, zaś \(\displaystyle{ 3 \cdot 8}\) na lewą, mamy \(\displaystyle{ -3 \cdot 8=-25+1}\). \(\displaystyle{ -3\equiv22\pmod{25}}\), więc szukaną liczbą jest \(\displaystyle{ 22}\). Mnożąc teraz początkowe równanie stronami przez \(\displaystyle{ 22}\), dostajemy \(\displaystyle{ x\equiv198\pmod{25}}\), co po redukcji wielokrotności \(\displaystyle{ 25}\) po prawej stronie daje \(\displaystyle{ x\equiv23\pmod{25}}\)

[Lukassz]

Ok. Tylko nie rozumiem tego przerzucenia. Tutaj miałem taki przykład i zrobiłem to tak:
\(\displaystyle{ 99x \equiv 1(mod13)}\)
\(\displaystyle{ 99=7\cdot 13+8\\
13=1\cdot 8+5\\
8 = 1\cdot 5+3\\
5=1\cdot 3+2\\
3=1\cdot 2+1\\
1=3-2=3-(5-3)=2\cdot 3-5=2(8-5)-5=2\cdot 8-3\cdot 5=2\cdot 8-3(13-8)=5\cdot 8-3\cdot 13=5\cdot (99-7\cdot 13)-3\cdot 13=5\cdot 99-38\cdot 13}\)


Nie wiem tylko co zrobić dokładnie z końcowym wynikiem.

[Qń]

Skoro \(\displaystyle{ 1=5\cdot 99-38\cdot 13}\), to po wzięciu obu stron równości modulo \(\displaystyle{ 13}\) dostaniemy:
\(\displaystyle{ 1\equiv 5\cdot 99\pmod{13}}\)
co oznacza, że jeśli wyjściową kongruencję przemnożymy stronami przez \(\displaystyle{ 5}\), to po lewej stronie zostanie \(\displaystyle{ 1\cdot x= x}\).

Można było też przez zaprzęgnięciem algorytmu Euklidesa zastąpić \(\displaystyle{ 99}\) przez \(\displaystyle{ 99-7\cdot 13 = 8}\) otrzymując kongruencję:
\(\displaystyle{ 8x\equiv 1\pmod{13}}\)


Q.

[Lukassz]

Skoro \(\displaystyle{ 1=5\cdot 99-38\cdot 13}\), to po wzięciu obu stron równości modulo \(\displaystyle{ 13}\) dostaniemy:
\(\displaystyle{ 1\equiv 5\cdot 99\pmod{13}}\)

Tego tylko nie rozumiem. Przy końcowym wyniku zawsze mam podstawić (zastąpić) modulo?