3582320535

Wykład 3

Arytmetyka modulo n

Niech n będzie dodatnią liczbą całkowitą (n > 0) i niech a, b £ Z. Mówimy, że a przystaje do b modulo n jeśli n\ (a — b) i piszemy wtedy a = b mod n.

Relacja przystawania modulo n jest relacją równoważności. Rzeczywiście relacja jest zwrotna bo dla każdej liczby całkowitej a, liczba 0 = a — a jest podziełna przez n. Zatem a = a mod n. Relacja ta jest również symetryczna bo jeśli n|(a — b) to również n\(b — a), bo b — a = —(a — 6). Relacja jest przechodnia, bo jeśli n\ (a — b) i n| (6 — c) to również n dzieli (a — b) + (b — c) — a — c, a więc n|(a — c).

Relacja przystawania modulo n ma jeszcze jedną bardzo ważną własność:

jeśli

to a + c= b + d mod n i a ■ c = b • d mod n. Każdą

a = b mod n

c = d mod n

relację równoważności, która spełnia powyższą własność nazywać będziemy kongruencją w Z.

Oznaczmy przez [a] klasę abstrakcji elementu a względem relacji przystawania modulo n, a więc:

[a] = {b £ Z : n|(a — 6)}

Można zauważyć, że klasa abstrakcji elementu a jest wyznaczona przez resztę z dzielenia tego elementu przez n i że dwa elementy są w relacji wtedy i tylko wtedy gdy dają tę samą resztę przy dzieleniu przez n. A więc w tym przypadku mamy dokładnie n różnych klas abstrakcji:

[0]    = {i £ Z : n|x} — nZ

[1] = {s £ Z : nj(x — 1)} = 1-fnZ

[2] = {x £ Z : nj (xc — 2)} = 2 + nZ

[n — 1] = {x e Z : n\(x — (n — 1))} = (n — 1) +nZ

Zamiast zapisu [a] będziemy zwykle używać zapisu a, a czasem będziemy opuszczać kreskę nad elementem. Przez Z_n oznaczać będziemy zbiór klas abstrakcji relacji przystawania modulo n, a więc:

~ {0,1,..., n — 1}

1