1. Arytmetyka.
Niech n będzie dowolną liczbą naturalną, a x będzie liczbą całkowitą. Dla przez oznaczamy resztę z dzielenia x przez n. Np. , - 8mod10 = 2. Zbiór reszt modulo n, czyli oznaczamy przez . Mówimy, że x jest elementem odwrotnym do , jeśli . W tej sytuacji piszemy . Zbór elementów, dla których istnieją odwrotni w , oznaczamy przez . W zbiorze można wykonywać dwie operacje: x jest sumą y i z modulo n, jeśli ; x jest iloczynem y i z modulo n, jeśli . Jeśli n jest liczbą złożoną: n=pq, wtedy iloczyn pq jest równy zero w : n=pq=0 mod n. Piszemy , gdy i mówimy, że x i y są kongruentne modulo n.
Twierdzenie 1. Następujące warunki są ekwiwalentne
1. ,
2. , gdzie k jest liczbą całkowitą,
3. , gdzie açb oznacza, że a dziele b.
Właściwości kongruencji
1. if i then
2. if i then
Przykład. Udowodnić że 73524 jest dzielone przez 11.
Oczywiście, że 10 º -1 (mod 11). Na mocy przedstawionej powyżej właściwości znajdujemy 100 º 1 (mod 11), 1000 º -1 (mod 11), 10000 º 1 (mod 11). Skąd 20 º -2 (mod 11), 500 º 5 (mod 11), 3000 º -3 (mod 11), 70000 º 7 (mod 11). Kolejne dodawanie daje 73520 º 7 (mod 11). Zatem 73520 +4 º 7+4 º 0 (mod 11).
Algorytm Euklidesa (3 wiek do n.e.) obliczania największego wspólnego dzielnika (NWD) liczb naturalnych a i b.
NWD(a, b)=NWD(a, a mod b) dla a³b (*)
Przykład. NWD (211, 79)? Kolejno wykorzystujemy wzór (*) póki nie otrzymamy (**)
211=79*2+53
79=53*1+26
53=26*2+1
26=1*26+0
Mamy NWD(211, 79) =NWD(79, 53) =NWD(53, 26) =NWD(26, 1)= =NWD(1,0)=1.
W ogólnym przypadku działania algorytmu Euklidesa można wyznaczyć następująco:
1. Położyć
2. Przy i-tej iteracji obliczyć
3. if then i=i+1 goto 2
4. if then NWD (a, b)=
5. End
Ilość kroków m algorytmu Euklidesa definiowana jest nierównością .
W trakcie działania algorytmu Euklidesa można wyznaczyć liczby całkowite x, y, taki że ,
gdzie a i b względnie pierwsze: NWD(a, b)=1, a>0, b>0.
Niech , gdzie
wtedy
; .
Te obliczenia zręcznie prowadzić za pomocą tabeli
N
-2
-1
0
1
2
...
k-1
k
Przykład. Wyznaczyć liczby całkowite x, y, taki że
17 x - 13 y = 1
17 = 13*1 + 4 =1
13 = 4*3 + 1 =3
4 = 1*4 + 0 =4
Zatem
diabolic