24406

W zbiorze Z_n można wprowadzić następujące działania:

a +„ b = a + b a_n b = a • b

Czy działania te są dobrze określone? Czy może się zdarzyć taka sytuacja, że 7i = Z, b = d a a + c ^ b + d lub (HI: jć 6 • rf? Otóż nie, a wynika to z faktu, że relacja przystawania modulo n jest kongruencją. Jeśli mamy Ti = Z.b = d toa = r mod n, 6 = d mod n. a stąd a + c = 6 + d mod n, a • c = 6 • d mod n, a więc a + c = b + d i Fć ^ 6 • d

Oczywiście spełniona jest następująca własność:

a = b <=> a = b mod n

i dwie klasy są albo równe albo są rozłączne.

Twierdzenie 1 Dla dowolnych klas a, b.ć (ż Z_n mamy:

(i)    a + (6 + c) = (a + 6) + c,

(ii)    (i + 6 = b+ a,

(iii)    a + Ó = 0-fa = a,

(iv)    a + n — o = n — a-|-a = Ó,

(v)    a ■ (b • c)_ = ((i ■ b) ■ ć,

(vi)    d - b = b a,

(vii)    a • I = I • a = a,

(viii)    (i • (6 + ć) = a ■ b + d - ć,

(ix)    (6 + ć) • a = b • a. + ć • a.

Przykład Skonstruować tabelki działań w pierścieniu Zr,.

*n	0	1	2	3	1
0	0	0	0	0	0
1	0	1	2	3	1
2	0	2	i	1	3
3	0	3	1	1	2
1	0	1	3	2	1

+n	0	1	2	3	4
0	0	1	2	3	1
1	1	2	3	1	0
2	2	3	1	0	1
3	3	1	0	1	2
1	1	0	1	2	3

Strukturę (Z_n, +,

nazywać będziemy pierścieniem reszt modulo n. Pytanie, które teraz się pojawia to: Kiedy równanie a _n x = 1 ma rozwiązanie w pierścieniu Z_n? Odpowiedzi można udzielić korzystając z wcześniejszych rozważań dotyczących równań diofantycznych.

Twierdzenie 2 Równanie a _nx = 1 ma rozwiązanie w pierścieniu Z_n wtedy i tylko wtedy gdy liczby a i n są względnie pierwsze. Inaczej mówiąc liczba a jest odwracalna modulo n wtedy i tylko wtedy gdy NWD(a,b) = 1.

2