Odwrotność modularna (artykuł) | Khan Academy

https://pl.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses

Odwrotność modularna a zwykła Odwrotność... 

"W arytmetyce modularnej 

nie mamy operacji dzielenia. Jednak dysponujemy odwrotnością modularną.

• Odwrotnością modularną A (mod C) jest A^-1
• (A * A^-1) ≡ 1 (mod C) ub równoważnie (A * A^-1) mod C = 1
• Tylko liczby względnie pierwsze z C (liczby nie posiadające wspólnych czynników pierwszych z C) posiadają odwrotność modularną (mod C)"

Jak znaleźć odwrotność modularną

Metoda naiwna znajdowania odwrotności modularnej do A (mod C) to:

krok 1. Oblicz A * B mod C, dla wartości B od 0 do C-1

krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1

Zauważ, że B mod C może przyjmować wartości całkowite wyłącznie od 0 do C-1, więc testowanie dla większych wartości  B jest zbyteczne.

Przykład: A=3, C=7

Krok 1. Obliczmy A * B mod C dla B z przedziału 0 do C-1

3 * 0 ≡ 0 (mod 7)

3 * 1 ≡ 3 (mod 7)

3 * 2 ≡ 6 (mod 7)

3 * 3 ≡ 9 ≡ 2 (mod 7)

3 * 4 ≡ 12 ≡ 5 (mod 7)

3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <--- ZNALEZIONO ODWROTNOŚĆ!

3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

Krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1

5 jest odwrotnością modularną 3 mod 7 ponieważ 5*3 mod 7 = 1

Proste!