Znaleźć rozwiązanie kongruencji ....

[bicek]

Witam,

Prośba o wytłumaczenie rozwiązania następującego przykładu

1. Znaleźć rozwiązanie kongruencji \(\displaystyle{ 25*x\equiv11(mod7)}\) w zbiorze liczb \(\displaystyle{ \lbrace 0,1,2,3,4,5,6\rbrace}\)


Nie jestem pewien ile jest sposobów, ale jak można to poproszę o rozwiązanie wykorzystujące algorytm Euklidesa.

dzięki

[BettyBoo]

\(\displaystyle{ 25=4\mod 7,\ 11=4\mod 7}\), więc wyjściowe równanie jest równoważne z \(\displaystyle{ 4x=4\mod 7}\)

Ponieważ 4 jest odwracalne modulo 7, to możemy pomnożyć przez \(\displaystyle{ 4^{-1}}\) obustronnie i mamy

\(\displaystyle{ x=1}\)

Pozdrawiam.