Prosta kongruencja

[laewqq]

Jak liczyć kongruencje ? bo nie bardzo potrafie to zrozumieć.

np. taką
\(\displaystyle{ 27x\equiv 25 \pmod{256}}\)

Wiem, że trzeba znaleźć największy wspólny dzielnik liczb 27 oraz 256 ktory jest równy 1. Mam zapisane cos takiego:

\(\displaystyle{ 27a+256=1 \\
256=9 \cdot 27+13 \\
27=2 \cdot 13+1}\)
wiec
\(\displaystyle{ 1=27-2 \cdot 13=27 \cdot 19-2 \cdot 256}\)

ale co mi właściwie to daje ? i jak to dokończyć ?

[eMaerthin]

przemnóż obie strony przez w tym przypadku \(\displaystyle{ 25}\) i będziesz mieć, że
\(\displaystyle{ 25\equiv 27\cdot (19\cdot 25) \pmod{256}}\)
ale \(\displaystyle{ 19\cdot25\equiv219\pmod{256}}\), więc ostatecznie
\(\displaystyle{ 27\cdot219\equiv25\pmod{256}}\)