Neka je n prirodan broj. Posmatramo skup
Zn = {a| 1 <= a <= n-1, nzd(a, n) = 1}
n = 15
Z15 = {1, 2, 4, 7, 8, 11, 13, 14}
Nad skupom Zn se moze definisati operacija modularnog mnozenja
a *n b = (a * b) mod n
4 *15 7 = 13
7 *15 13 = 1
Invezni element:
Ako je x neki element Zn, onda postoji x’ takvo da je
x *n x’ = x’ *n x = 1
x’ je multiplikativni inverz
n = 15, x = 7, x’ = 13
x = 8, x’ = 2
Posto je x element skupa Zan, onda je nzd(x, n) = 1,
ali po prosirenom euklidovom algoritmu, postoje brojevi p i q
takvi da je x * p + n * q = 1
x * p = n * (-q) + 1
x *n p = x * p mod n = (n * (-q) + 1) mod n = 1
n = 15, x = 8
15
8
7 = 15 * 1 + 8 * (-1)
1 = 8 * 1 + 7 * (-1) = 8 * 2 + 15 * (-1)
n = 15, x = 7
15
7
1 = 15 * 1 + 7 * (-2) = 15 * (-6) + 7 * 13
NTP 