6161619794

Niektóre właściwości relacji kongriiencji:

a = b (mod n) <=> a mod n = b mod n a =a (mod n)

a=b (mod n) =>b = a (mod n) a =b (mod n) a b =c (mod n) => a = c (mod n) a =b (mod n) a c =d (mod n) =>

a ±c =b ±d (modn) Aa c =b d (mod n) a = b (mod u) a r \ n =7 a = b (mod r)

a =b (mod n) a a =b (mod m) Agcdfm, n) = 1 =>a =b (mod mn) d\a Ad\b Ad\n => (a = b (mod n) =>a / d=b / d (mod n Id ))

Zbiór wszystkich liczb całkowitych kongruentnych do a modulo n nazywa się klasą równoważności liczby a.

Dla ustalonego n zbiór $ jest podzielony przez relację kongruencji modulo n na (rozłączne) klasy równoważności.

a - qn + r a 0 < r <n => a =r (mod n)

Wniosek'.

Każda liczba całkowita a jest kongruentna modulo n do unikalnej liczby całkowitej z zakresu od 0 do (n -1), zwanej najmniejszą resztą a modulo n ; a i r należą do tej samej klasy równoważności, która może być reprezentowana przez tą resztę.

Zbiór „ , zwany zbiorem liczb całkowitych modliło n. jest zbiorem liczb { 0, 1, 2,    n-1 }. W zbiorze tym dodawanie, odejmowanie i

mnożenie wykonywane są modulo n.

Przykład:

W zbiorze ^ ₂;:

7 + 18 = 4    7-18 = 10    7 18 = 0

Liczba całkowita x e $ _n jest (multiplikatywnym) elementem odwrotnym do liczby całkowitej a e Z _n <=> ax = 1 (mod n).