6161619796

Niech d = gcd (a, n).

Równanie ax = b (mod n) ma rozwiązanie(a) x e f_n <=>d I b.

(ponadto rozwiązań tych jest dokładnie d, zaś wszystkie rozwiązania są kongruentne modulo (n / d))

Przykład 1:

3x =2 (mod 5)

d = gcd (3, 5) = 1 1 12

3 0 (mod 5) = 0 3 1 (mod 5) =3 3'2 (mod 5) = 6 (mod 5) = 1 3'3 (mod 5) =9 (mod 5) = 4 3 4 (mod 5) = 12 (mod 5) =2

jedno rozwiązanie: x = 3    2 (mod 5) = 2'2 (mod 5) =4

Przykład 2:

3x =5 (mod 6)

3 0 (mod 6) = 0 3 1 (mod 6) =3 3 '2 (mod 6) = 6 (mod 6) = 0 3 ' 3 (mod 6) = 9 (mod 6) = 3 3 4 (mod 6) = 12 (mod 6) = 0 3'5 (mod 6) = 15 (mod 6) =3

d = gcd (3, 6) = 3 nieprawda, że 3 I 5 brak rozwiązań

Przykład 3:    3x =3 (mod 6)

d = gcd (3, 6) = 3 3\3

trzy rozwiązania: xi = I, x₂ = 3, Xj = 5 n / d = 2

Xj = x2 =x₃ (mod 2)