Arytmetyka modularna

Arytmetyka modularna jak sama nazwa wskazuje, tyczy się modulo, oznaczającego resztę z dzielenia.

Odwrotność modularna

O odwrotności modularnej mówimy że: $b = a^{- 1} mod c$

("b" jest odwrotnością "a" w arytmetyce modulo "c" wtedy gdy)

$a \cdot b mod c = 1$

Odwrotność modularna nie musi istnieć dla każdej liczby!

$2$ nie ma odwrotności w arytmetyce $mod 4$ $6$ nie ma odwrotności w arytmetyce $mod 9$

By istniała odwrotność modularna liczby $a$ w arytmetyce modulo $c$ konieczne jest by: $N W D (a, c) = 1$

Do szukania odwrotności modularnej danej liczby wykorzystujemy odwrócony algorytm Euklidesa

Załóżmy że szukamy odwrotności liczby $w$ w arytmetyce $mod m$

Bierzemy nasze $w, m$
Rozpisujemy równanie $N W D (w, m) = 1$ $m : w = a r r_{1}$ $w : r_{1} = b r r_{2}$ $i t d ...$
Gdy mamy już resztę równą 0, należy rozpisać równiania pomocnicze, które opisują daną resztę (np. $r_{1} = 1 \cdot m - w \cdot a$ )
Następnie, pod ostatnie równanie podstawiamy tak liczby, by w efekcie uzyskać: $1 = x \cdot m + w^{- 1} \cdot w$

(łatwiej jest to zrozumieć na liczbach mimo wszystko)