Wyznaczanie liczby odwrotnej

michal9225 · Post autor: **michal9225** » 21 mar 2013, o 18:23

Witam!
Mam problem z pewnym zadaniem.

Zadanie:

Sprawdzić która z liczb: 1, 71, 73, 77 jest równa \(\displaystyle{ 13^{-1}_{mod100}}\)

Robiłem to zadanie korzystając z rozszeszonego algorytmu Euklidesa. Jednak wynik algorytmu to 23.
A liczba ta nie pasuje do żadnego rozwiązania.

Bardzo bym prosił o pomoc.

yorgin · Post autor: **yorgin** » 21 mar 2013, o 18:26

Skoro masz podane warianty odpowiedzi, to łatwo sprawdzić, że

\(\displaystyle{ 13\cdot 77=1001\equiv 1\mod 100}\)

michal9225 · Post autor: **michal9225** » 21 mar 2013, o 18:28

Wielkie dzięki za pomoc )-- 23 mar 2013, o 17:33 --Zatem do rozwiązania zadania potrzebny jest w ogóle rozszerzony algorytm Euklidesa? Wychodzi na to że rozwiązaniem tego zadania jest liczba \(\displaystyle{ 77}\) czy liczba \(\displaystyle{ 1}\)?