Znaleźć element odwrotny

[magdusiam]

Znaleźć element odwrotny do a w \(\displaystyle{ Z _{m}}\) jeśli:
a) a= 28, m=31
b) a=179 , m=301
c) a=17, b=57

[Psiaczek]

Znaleźć element odwrotny do a w \(\displaystyle{ Z _{m}}\) jeśli:
a) a= 28, m=31
b) a=179 , m=301
c) a=17, b=57

Można z algorytmu Euklidesa, np. a)

\(\displaystyle{ 31=1 \cdot 28+3,28=9 \cdot 3+1,3=3 \cdot 1+0}\)

Bierzemy linijkę gdzie jest ostatnia niezerowa reszta (czyli NWD), i powinno tą resztą być jeden, do tej linijki podstawiamy przekształconą pierwszą linijkę, i po jednej stronie zostawiamy samą jedynkę,

czyli do \(\displaystyle{ 28=9 \cdot 3+1}\) podstawiamy \(\displaystyle{ 3=31-1 \cdot 28}\)

po przekształceniach będzie: \(\displaystyle{ -9 \cdot 31+10 \cdot 28=1}\)

to co stoi przy 28 , czyli 10 jest szukanym elementem odwrotnym.Gdyby ten współczynnik wyszedł ujemny to dodać trzeba m do niego.

[magdusiam]

Nie rozumiem skąd jest tam 10 w "\(\displaystyle{ -9 \cdot 31+10 \cdot 28=1}\)"

[Psiaczek]

Nie rozumiem skąd jest tam 10 w "\(\displaystyle{ -9 \cdot 31+10 \cdot 28=1}\)"

No to krok po kroku:



\(\displaystyle{ 28=9 \cdot 3+1}\)

\(\displaystyle{ 28=9 \cdot (31-1 \cdot 28)+1}\)

\(\displaystyle{ 28=9 \cdot 31-9 \cdot 28+1}\)

\(\displaystyle{ 28+9 \cdot 28-9 \cdot 31=1}\)

\(\displaystyle{ 10 \cdot 28-9 \cdot 31=1}\)