Kongruencja - sprawdzenie.

[magnus250]

Cześć, mógłby ktoś rzucić okiem na moje rozwiązanie przykładu?

\(\displaystyle{ 53^{-1} \pmod{217} \\
(53, 217) = 1 \\
217=4 \cdot 53 + 5 \\
53 = 10 \cdot 5 +3 \\
5 = 3+2 \\
3 = 2+1 \\
2 = 2 \cdot 1 = 0 \\ \\
1 = 3-2 = 3-(5-3) = 2 \cdot 3 - 5 = 2 \cdot (53 - 10 \cdot 5) - 5 = 2 \cdot 53 - 21 \cdot 5 = \\ = 2 \cdot 53 - 21 \cdot (217 - 4 \cdot 53) = 2 \cdot 53 - 21 \cdot 217 + 86 \cdot 53 = \\= 86 \cdot 53 - 21 \cdot 217 \\

21 \cdot 217 = 86 \cdot 53 - 1 \\
217 | 86 \cdot 53 - 1 \\ \\
53 \cdot (86) = 1 \pmod{217} \\
53^{-1} \pmod{217} = 86 = 303}\)-- 12 cze 2018, o 07:21 --@Jan Kraszewski, dzięki za poprawienie, mógłbyś zerknąć na to?

[Premislav]

\(\displaystyle{ 2 \cdot 53 - 21 \cdot (217 - 4 \cdot 53) = 2 \cdot 53 - 21 \cdot 217 + 86 \cdot 53}\)

Ta równość jest błędna, ale chyba to literówka/przeoczenie, ponieważ dalej masz poprawnie. Wynik \(\displaystyle{ 86}\) jest OK, tylko nie wiem, czemu to zamieniasz na jakieś \(\displaystyle{ 303.}\) Przecież w\(\displaystyle{ \ZZ_{217}}\) mamy \(\displaystyle{ 303\equiv 86}\)