Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Teoria liczb
1.1 Dzielenie całkowitoliczbowe
Zacznijmy od przypomnienia szkolnego algorytmu dzielenia liczb naturalnych. Podziel-
my 174 przez 12.
1 4
1 7 4 : 1 2
1 2
5 4
4 8
6
W wyniku dzielenia otrzymaliśmy iloraz 14 i resztę 6 . Liczby te spełniają równanie
174 = 14 · 12 + 6
i reszta jest mniejsza od dzielnika. Podobnie możemy postąpić dla dowolnych liczb natu-
ralnych a i b pod warunkiem, że b = 0.

Twierdzenie 1.1 Dla dowolnych liczb naturalnych a oraz b > 0 istnieje dokładnie jedna
para liczb naturalnych q i r spełniających warunki:
" a = bq + r
" 0 d" r < b
q nazywa się ilorazem całkowitoliczbowym a przez b, a r nazywa się resztą z dzielenia
a
Zauważmy, że iloraz q jest zaokrągleniem w dół normalnego ilorazu q = . Iloraz
b
całkowitoliczbowy liczb a i b będziemy oznaczać przez
a ÷ b lub a div b.
a resztÄ™ przez
a mod b.
3
4 Rozdział 1. Teoria liczb
PrzykÅ‚ad 1.2 22 ÷ 4 = 5 oraz 22 mod 4 = 2, ponieważ 22 = 5 · 4 + 2 oraz 0 d" 2 < 4.
Powyższe definicje zakładały, że a i b są naturalne. W przypadku, gdy a i b są liczba-
mi całkowitymi, iloraz i różnice można róznie definiować. Na przykład w języku Pascal
iloraz dwóch liczb typu całkowitego oznacza się przez
a div b
a a a a
i jest to  zaokrąglenie ilorazu w dół, gdy jest dodatnie i ,  zaokrąglenie
b b b b
a a
ilorazu w górę, gdy jest ujemne. Reszta, którą oznacza się przez
b b
a mod b,
jest określona wzorem:
a mod b = a-(a div b)*b.
Mamy więc, na przykład:
22 div 4 = 5; (-22)div 4 = -5; 22 div(-4)= -5; (-22)div(-4)= 5;
22 mod 4 = 2; (-22)mod 4 = -2; 22 mod(-4)= 2; (-22)mod(-4)= -2.
1.2 Podzielność liczb
Mówimy, że liczba całkowita a = 0 dzieli liczbę całkowitą b, jeżeli istnieje liczba całko-

wita z, taka że:
b = az.
Będziemy to oznaczać przez a|b. Zauważmy, że zachodzi wtedy:
b mod a = 0.
LiczbÄ™ a nazywamy dzielnikiem liczby b.
Przykład 1.3 3|6, 3| - 6 oraz 3|0.
Lemat 1.4 Jeżeli a|b oraz a|c , to a|(b + c) oraz a|(b - c)
Dowód. Jeżeli a|b i a|c, to istnieją dwie liczby całkowite k i m, takie że:
b = ak oraz c = am.
Mamy więc:
b + c = ak + am = a(k + m)
oraz
b - c = ak - am = a(k - m)
czyli a dzieli b + c oraz b - c.
1.3. Relacja kongruencji 5
1.3 Relacja kongruencji
Niech m będzie dowolną liczbą naturalną m = 0. Powiemy, że dwie liczby całkowite a i

b są równoważne (lub przystają) modulo m, jeżeli
m|(a - b).
Będziemy wtedy pisać:
a = b (mod m).
Przykład 1.5 1 = 4 (mod 3), 3 = 0 (mod 3), -1 = 2 (mod 3),
-1 = -7 (mod 3).
Jeżeli a i b są dodatnie, to a = b (mod m) wtedy i tylko wtedy, gdy a i b mają takie
same reszty z dzielenia przez m.
Lemat 1.6 Relacja przystawania modulo jest relacją równoważności, czyli spełnia na-
stępujące trzy warunki:
" zwrotność, dla każdego a zachodzi a = a (mod m),
" symetrię, dla każdego a i b, jeżeli a = b (mod m), to b = a (mod m),
" przechodniość, dla każdego a, b i c,
jeżeli a = b (mod m) i b = c (mod m), to a = c (mod m).
Dowód. Udowodnimy tylko przechodniość relacji. Jeżeli m|(a - b) oraz m|(b - c),
to m|((a - b) + (b - c)), czyli m|(a - c).
Ponadto relacja modulo jest zgodna z dodawaniem, odejmowaniem i mnożeniem.
Twierdzenie 1.7 Jeżeli a = b (mod m) oraz c = d (mod m), to:
a + c = b + d (mod m), a - c = b - d (mod m), ac = bd (mod m).
Dowód. Z założenia mamy:
m|(a - b) oraz m|(c - d),
z tego zaś łatwo wynika, że m dzieli:
(a + c) - (b + d), (a - c) - (b - d) oraz ac - bd = a(c - d) + d(a - b),
czyli zachodzi teza twierdzenia.
Przykład 1.8 Twierdzenie 1.7 może być użyte do obliczania reszty z dzielenia Jeżeli chce-
my policzyć na przykład
1999 mod 3,
6 Rozdział 1. Teoria liczb
to pytamy, która z trzech liczb {0, 1, 2} przystaje do 1999 modulo 3. Zróbmy najpierw
kilka prostych obserwacji. Po pierwsze:
10 = 1 (mod 3),
bo 3|(10 - 1). Z twierdzenia 1.7 wynika, że każda potęga liczby dziesięć przystaje do 1
modulo 3, czyli:
10k = 1 (mod 3)
dla każdego k. Mamy teraz:
1999 = 1000 + 9 · 100 + 9 · 10 + 9 = 1 + 9 + 9 + 9 = 1 (mod 3).
Podobnie, dla dowolnej liczby x, jeżeli zapiszemy x w postaci dziesiętnej:
x = di · 10i,
to
x = di (mod 3),
czyli x ma takie same reszty modulo 3 co suma cyfr w zapisie dziesiętnym.
Przykład 1.9 Aby przekonać się, że
2002 · 1999 = 4001999

wystarczy zauważyć, że liczba 2002 jest parzysta, więc także wynik mnożenia powinien
byż parzysty. Mówiąc inaczej 2002 = 0 (mod 2), więc na podstawie twierdzenia 1.7
mamy 2002 · 1999 = 0 (mod 2), a liczba 4001999 przystaje do jedynki modulo 2.
Podobnie możemy się przekonać, że
2002 · 1999 = 4001996

wystarczy zauważyć, że w iloczynie 2002 · 1999 ostatniÄ… cyfrÄ… powinno być 8 a nie 6.
Inaczej 2002 = 2 (mod 10) oraz 1999 = 9 (mod 10), więc na podstawie twierdze-
nia 1.7 mamy 2002 · 1999 = 8 (mod 10), a liczba 4001996 przystaje do 6 modulo
10.
1.4 Klasy abstrakcji
Dla relacji przystawania modulo m definiujemy klasy abstrakcji. Dla dowolnej liczby
całkowitej x, klasę abstrakcji elementu x definiujemy w następujący sposób:
[x] = {y | y = x (mod m)}.
Innymi słowy, klasa abstrakcji liczby x to zbiór wszystkich liczb z nią równoważnych.
Przykład 1.10 Dla m = 3 mamy trzy klasy abstrakcji
1.5. Pierścień Zm 7
[0] = {3k | k " Z} = {. . . , -9, -6, -3, 0, 3, 6, 9, . . .}
[1] = {3k + 1 | k " Z} = {. . . , -8, -5, -2, 1, 4, 7, 10, . . .}
[2] = {3k + 2 | k " Z} = {. . . , -7, -4, -1, 2, 5, 8, 11, . . .}
Zauważmy, że klasy abstrakcji elementów równoważnych pokrywają się.
Lemat 1.11 Jeżeli x = y (mod m), to [x] = [y].
Dowód. Jeżeli z " [x], to
z = x (mod m)
i z przechodniości relacji mamy
z = y (mod m),
czyli z " [y], a więc pokazaliśmy, że:
[x] ‚" [y].
Identycznie pokazujemy zawieranie odwrotne [y] ‚" [x].
Następna ważna własność klas abstrakcji to ich rozłączność.
Lemat 1.12 Jeżeli [x] )" [y] = ", to [x] = [y],

inaczej, dwie klasy abstrakcji [x] i [y] albo są identyczne, albo są rozłączne.
Dowód. Przypuśćmy, że klasy [x] i [y] mają wspólny element z. Wtedy:
z = x (mod m) oraz z = y (mod m).
Z przechodniości mamy wtedy
x = y (mod m),
a z lematu 1.11
[x] = [y].
1.5 Pierścień Zm
Klasy abstrakcji relacji modulo m wyglądają następująco:
[0], [1], . . . , [m - 1].
Dla dowolnego k z przedziału 0 d" k d" m - 1, klasa [k] jest postaci:
[k] = {jm + k | j " Z}
8 Rozdział 1. Teoria liczb
(Z oznacza zbiór liczb całkowitych). Zbiór klas abstrakcji modulo m oznacza się przez
Zm.
Ponieważ relacja modulo jest zgodna z działaniami dodawania i mnożenia, możemy
zdefiniować dodawanie i mnożenie na klasach abstrakcji. Mówiąc w skrócie, aby wyko-
nać działanie na dwóch klasach abstrakcji, wybieramy dowolnych przedstawicieli tych
klas i wykonujemy działania na tych przedstawicielach. Dokładniej, dodawanie klas abs-
trakcji definiujemy następująco:
[x] + [y] = [x + y].
Podobnie definiujemy odejmowanie i mnożenie:
[x] - [y] = [x - y], [x] · [y] = [x · y].
Poniższy lemat pokazuje, że działania te są dobrze zdefiniowane; że wynik działania na
dwóch klasach nie zależy od wyboru reprezentantów.
Lemat 1.13 Jeżeli [x] = [y] oraz [u] = [w], to:
[x + u] = [y + w], [xu] = [yw] oraz [x - u] = [y - w].
Dowód. Z założenia mamy:
x = y (mod m) oraz u = w (mod m).
a z twierdzenia 1.7:
[x + u] = [y + w], [x - u] = [y - w] oraz [xu] = [yw].
Przykład 1.14 Niech m = 3. Dla dowolnych dwóch liczb x " [0] i y " [1] ich suma
x + y należy do [0 + 1] = [1] a iloczyn do [0 · 1] = [0].
Lemat 1.15 Działania na klasach abstrakcji
[0], [1], . . . , [n - 1]
spełniają następujące warunki:
" dodawanie oraz mnożenie są przemienne i łączne,
" klasa [0] jest elementem neutralnym dodawania, to znaczy dla każdego a mamy
[a] + [0] = [a],
" dla każdej klasy [a] istnieje klasa do niej przeciwna [-a], taka że [a] + [-a] = [0],
" klasa [1] jest elementem neutralnym mnożenia, to znaczy dla dowolnego [x] mamy
[x] · [1] = [x],
1.5. Pierścień Zm 9
" mnożenie jest rozdzielne względem dodawania, czyli dla każdych trzech klas [x],
[y], [z] mamy [x]([y] + [z]) = [x][y] + [x][z].
Zbiór z dwoma działaniami spełniającymi powyższe warunki nazywa się pierścieniem
przemiennym z jedynkÄ….
Dowód: Udowodnimy tylko rozdzielność:
[x]([y] + [z]) = [x][y + z] = [x(y + z)] = [xy + xz] = [xy] + [xz] = [x][y] + [x][z].
Skorzystaliśmy w tym dowodzie z rozdzielności mnożenia względem dodawania dla liczb
całkowitych.
1.5.1 Pierścień Z5
Rozważmy zbiór reszt modulo 5. Składa się on z pięciu klas:
[0], [1], [2], [3], [4],
dla prostoty będziemy dalej opuszczać nawiasy. Mamy więc zbiór:
Z5 = {0, 1, 2, 3, 4}
z dodawaniem i mnożeniem określonym następującymi tabelami:
+ 0 1 2 3 4 · 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
Zauważmy, że każdy element oprócz zera ma w Z5 element odwrotny względem mnoże-
nia, czyli dla każdego x " Z5 - {0} istnieje x-1, taki że xx-1 = 1:
1-1 = 1, 2-1 = 3, 3-1 = 2, 4-1 = 4.
Dlatego Z5 jest ciałem, czyli pierścieniem przemiennym z jedynką i z odwrotnością
względem mnożenia.
1.5.2 Pierścień Z4
Rozważmy teraz pierścień reszt modulo 4:
Z4 = {0, 1, 2, 3},
gdzie dodawanie i mnożenie jest określone następującymi tabelami:
10 Rozdział 1. Teoria liczb
+ 0 1 2 3 · 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 x 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1
Z4 nie jest ciałem, ponieważ nie ma w nim elementu odwrotnego do 2. Ponadto w Z4
mamy:
2 · 2 = 0,
czyli zero można przedstawić jako iloczyn dwóch liczb różnych od zera.
A
atwo zauważyć, że jeżeli liczba m jest złożona, m = pq dla 1 < p, q < m, to w
pierścieniu Zm mamy pq = 0 i ani p, ani q nie mają elementów odwrotnych. Przypuśćmy
bowiem, że istnieje p-1. Mamy wtedy:
0 = p-10 = p-1(pq) = (p-1p)q = 1q = q,
czyli q = 0, sprzeczność. Tak więc Zm nie jest ciałem, jeżeli m jest liczbą złożoną.
W dalszej części tego rozdziału zobaczymy, że jeżeli m jest liczbą pierwszą, to Zm jest
ciałem.
1.6 Największy wspólny dzielnik
Dla dwóch liczb całkowitych a i b, ich największy wspólny dzielnik to po prostu naj-
większa liczba całkowita n, która dzieli a i b. Największy wspólny dzielnik liczb a i b
będziemy oznaczać przez NW D(a, b).
Przykład 1.16 NW D(4, 6) = 2, NW D(4, 0) = 4, NW D(4, -6) = 2.
1.7 Algorytm Euklidesa
Aby obliczyć największy wspólny dzielnik dwóch dodatnich liczb naturalnych a, b robi-
my co następuje
dopóki a · b = 0 wykonuj:

jeżeli a e" b, to
a := a mod b
w przeciwnym przypadku
b := b mod a;
NWD:=a+b
Powyższy algorytm oblicza resztę z dzielenia większej liczby przez mniejszą tak długo,
aż otrzyma zero. Wtedy wynikiem działania algorytmu jest ta druga liczba (jeżeli a = 0,
to a + b = b, a jeżeli b = 0, to a + b = a). W poniższej tabeli pokazano kolejne kroki
działania algorytmu Euklidesa na parze liczb 36 i 15:
1.7. Algorytm Euklidesa 11
a b
36 15
6 15
6 3
0 3
Tak więc 3 jest największym wspólnym dzielnikiem liczb 15 i 36. Poprawność algorytmu
Euklidesa wynika z poniższego lematu.
Lemat 1.17 Niech a i b będą dwoma liczbami naturalnymi i niech 0 < b d" a. Wtedy
para a, b ma taki sam zbiór wspólnych dzielników jak para a mod b, b.
Dowód. Z definicji ilorazu i reszty mamy
a = (a ÷ b) · b + a mod b.
Jeżeli liczba r jest wspólnym dzielnikiem pary a, b, to r dzieli także resztę a mod b, czyli
r jest wspólnym dzielnikiem pary (a mod b), b. Na odwrót, jeżeli liczba r jest wspólnym
dzielnikiem pary (a mod b), b, to r dzieli także a, czyli r jest wspólnym dzielnikiem pary
a, b.
Tak więc po każdej iteracji pętliwhilepara a, b ma taki sam zbiór wspólnych dziel-
ników, a więc także taki sam największy wspólny dzielnik. Na końcu, gdy a = 0 lub
b = 0, NW D = a + b, czyli jest równy tej drugiej liczbie. Należy jeszcze pokazać, że
dla każdej pary dodatnich liczb naturalnych a i b algorytm zatrzyma się. Ale to wynika z
faktu, że po każdej iteracji pętli dopóki liczba
max{a, b}
jest coraz mniejsza, a ponieważ jest to zawsze liczba naturalna dodatnia, więc nie może
zmniejszać się w nieskończoność.
Twierdzenie 1.18 Niech a i b będą dwoma dodatnimi liczbami naturalnymi i niech d =
NW D(a, b). Wtedy istnieją liczby całkowite x i y, takie że:
xa + yb = d,
lub mówiąc inaczej, d jest kombinacją całkowitoliczbową liczb a i b.
Dowód. Niech a0 i b0 oznaczają początkowe wartości zmiennych a i b, odpowiednio.
Pokażmy, że wszystkie wartości, jakie przyjmują zmienne a i b w trakcie wykonywania
algorytmu Euklidesa, są całkowitoliczbowymi kombinacjami liczb a0 i b0. Na początku,
gdy a = a0 i b = b0, mamy:
a = 1a0 + 0b0, b = 0a0 + 1b0.
Załóżmy teraz, że po i-tej iteracji pętli a > b oraz że zachodzi:
a = xaa0 + yab0, b = xba0 + ybb0.
12 Rozdział 1. Teoria liczb
Wtedy w (i + 1) iteracji a bÄ™dzie pomniejszone o b · (a ÷ b) i bÄ™dziemy mieli:
a = (xa - xb · (a ÷ b))a0 + (ya - yb · (a ÷ b))b0
oraz
b = xba0 + ybb0.
Z tego wynika, że także ostateczna wartość d jest kombinacją liczb a0 i b0.
1.7.1 Rozszerzony algorytm Euklidesa
Algorytm Euklidesa można tak zmodyfikować, aby oprócz największego wspólnego dziel-
nika NW D(a, b), wyliczał także liczby x i y, takie że:
xa + yb = NW D(a, b).
Oto ten algorytm
xa := 1; ya := 0;
xb := 0; yb := 1;
dopóki a · b = 0 wykonuj:

jeżeli a e" b, to
a := a mod b
xa := xa - xb " (a ÷ b);
ya := ya - yb " (a ÷ b)
w przeciwnym przypadku
b := b mod a;
xb := xb - xa " (b ÷ a);
yb := yb - ya " (b ÷ a)
NW D := a + b
jeżeli a > 0, to x := xa; y := ya;
jeżeli b > 0, to x := xb; y := yb;
W poniższej tabeli pokazano kolejne kroki działania rozszerzonego algorytmu Eukli-
desa na parze liczb 36 i 15:
a b xa ya xb yb
36 15 1 0 0 1
6 15 1 -2 0 1
6 3 1 -2 -2 5
0 3 5 -12 -2 5
Tak więc liczbę 3 można przedstawić jako kombinację liczb 15 i 36 w następujący sposób:
3 = (-2) · 36 + (5) · 15.
1.8. Liczby pierwsze i względnie pierwsze 13
Zauważmy, że jeżeli jakaś liczba r dzieli liczby a i b, to dzieli także każdą ich kombinację
całkowitą
xa + yb,
a więc dzieli także największy wspólny dzielnik NW D(a, b). Udowodniliśmy poniższy
lemat.
Lemat 1.19 NW D(a, b) jest podzielny przez każdy wspólny dzielnik liczb a i b.
Z lematu 1.19 wynika, że największy wspólny dzielnik NW D(a, b) może być rów-
noważnie zdefiniowany jako taki wspólny dzielnik liczb a i b, który jest podzielny przez
każdy wspólny dzielnik a i b.
Lemat 1.20 Liczba naturalna d jest największym wspólnym dzielnikiem liczb a i b wtedy
i tylko wtedy gdy d jest wspólnym dzielnikiem a i b oraz istnieją liczby całkowite x i y,
takie że d = xa + yb.
Dowód Jeżeli NW D(a, b) = d to d|a, d|b oraz (z twierdzenia 1.18) istnieją liczby całko-
wite x i y, takie że: d = xa + yb.
Na odwrót, jeżeli d dzieli a i b oraz xa + yb = d, to każdy wspólny dzielnik a i b
dzieli d, a więc d jest największym wspólnym dzielnikiem a i b.
Wniosek 1.21 Jeżeli istnieją liczby całkowite x i y, takie, że xa+yb = 1, to NW D(a, b) =
1.
Przykład 1.22 Ponieważ:
2000 - 1998 = 2
oraz 2 jest wspólnym dzielnikiem 1998 i 2000, więc NW D(1998, 2000) = 2.
2001 - 1999 = 2,
więc NW D(1999, 2001) dzieli 2, a ponieważ 2 nie dzieli ani 1999, ani 2001, więc
NW D(1999, 2001) = 1.
1.8 Liczby pierwsze i względnie pierwsze
Dwie liczby naturalne a i b są względnie pierwsze, jeżeli NW D(a, b) = 1, a liczba
naturalna p jest pierwsza, jeżeli p > 1 i jedynymi dzielnikami naturalnymi p są jedynka i
samo p.
Oto wszystkie liczby pierwsze mniejsze od 50:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Liczba n > 1, która nie jest pierwsza jest złożona. Istnieją wtedy dwie liczby k, m < n,
takie, że n = k · m.
14 Rozdział 1. Teoria liczb
1.9 Rozkład liczb na czynniki pierwsze
W tym rozdziale zobaczymy, że każdą liczbę naturalną n > 1 można rozłożyć na czynniki
pierwsze i że taki rozkład jest jednoznaczny z dokładnością do kolejności czynników. Na
przykład:
12 = 22 · 3 i 180 = 22 · 32 · 5.
Przyjmujemy przy tym, że jeżeli liczba jest pierwsza, to jej rozład składa się tylko z jednej
liczby.
Twierdzenie 1.23 Każdą liczbę naturalną n > 1 można przedstawić jako iloczyn liczb
pierwszych (niekoniecznie różnych):
n = q1q2 · · · qr.
Dowód nie wprost. 2 jako liczba pierwsza ma trywialny rozkład składający się z jednej
liczby. Przypuśćmy, że istnieje liczba naturalna n, której nie można przedstawić jako
iloczynu liczb pierwszych i że n jest najmniejszą taką liczbą. n nie może być liczbą
pierwszą (bo wtedy n = q1), więc n jest liczbą złożoną, czyli jest postaci:
n = km
dla k, m < n. Ale ponieważ k i m są mniejsze od n, więc można je rozłożyć na czynniki
pierwsze
k = p1p2 · · · ps oraz m = r1r2 · · · rt,
ale wtedy, wbrew założeniu, mamy rozkład liczby n na czynniki pierwsze:
n = p1p2 · · · psr1r2 · · · rt.
Aby pokazać, że rozkład jest jednoznaczny (z dokładnością do kolejności czynników),
musimy najpierw udowodnić dwa lematy.
Lemat 1.24 Niech a i b będą dodatnimi względnie pierwszymi liczbami naturalnymi.
Wtedy dla dowolnej liczby c, jeżeli a|bc, to a|c.
Dowód. Z twierdzenia 1.18, istnieją dwie liczby całkowite x i y, takie że:
xa + yb = 1.
Pomnóżmy teraz obie strony tego równania przez c:
xac + ybc = c,
i zauważmy, że a dzieli oba składniki po lewej stronie równania, a więc dzieli prawą
stronÄ™, czyli c.
1.10. Elementy odwracalne 15
Lemat 1.25 Jeżeli liczba pierwsza p dzieli iloczyn liczb pierwszych
q1q2 · · · qr
(niekoniecznie różnych), to wtedy p jest równe jednej z liczb qi.
Dowód przez indukcję ze względu na r. Dla r = 1 mamy p|q1, a ponieważ q1 jest
pierwsza i p > 1, więc p = q1.
Załóżmy teraz, że teza zachodzi dla r i przypuśćmy, że p dzieli
q1q2 · · · qrqr+1.
Mamy dwa przypadki: albo p dzieli qr+1, albo nie. W pierwszym przypadku p = qr+1.
W drugim przypadku mamy NW D(p, qr+1) = 1, bo 1 i qr+1 to jedyne dzielniki liczby
qr+1. Z lematu 1.24 wynika teraz, że p dzieli q1q2 · · · qr, a z zaÅ‚ożenia indukcyjnego, że
p = qi dla jakiegoÅ› 1 d" i d" r. .
Udowodnimy teraz, że rozkład liczby na czynniki pierwsze jest jednoznaczny, z dokład-
nością do kolejności czynników.
Twierdzenie 1.26 Każdą liczbę naturalną n > 1 można w dokładnie jeden sposób przed-
stawić w postaci iloczynu:
1 2 r
n = pÄ… pÄ… . . . pÄ… ,
1 2 r
gdzie Ä…i sÄ… dodatnimi liczbami naturalnymi, pi sÄ… liczbami pierwszymi oraz zachodzi
p1 < p2 < . . . < pr.
Dowód. Twierdzenie 1.23 orzeka, że liczba ma rozkład na czynniki pierwsze. Trzeba
pokazać, że jest to rozkład jednoznaczny. n = 2 jako liczba pierwsza ma jednoznaczny
rozkład. Przypuśćmy, że n jest najmniejszą liczbą z dwoma różnymi rozkładami:
²1 ²2
²s
1 2 r
n = pÄ… pÄ… . . . pÄ… = q1 q2 . . . qs . (1.1)
1 2 r
n
Wtedy z jednej strony p1 nie może występować po prawej stronie równania (1.1), bo
p1
byłoby mniejszą liczbą z niejednoznacznym rozkładem. Z drugiej strony p1 dzieli prawą
stronę, a więc, z lematu 1.25 występuje po prawej stronie. Mamy więc sprzeczność.
Lemat 1.27 Jeżeli a i b są względnie pierwsze, to ich rozkłady są rozłączne. To znaczy
mają rozłączny zbiór liczb pierwszych występujących w ich rozkładach.
1.10 Elementy odwracalne
Definicja 1.28 Element a " Zm jest odwracalny, jeżeli istnieje b " Zm, takie, że
a · b = 1 (mod m).
b nazywamy elementem odwrotnym do a i oznaczamy przez a-1.
16 Rozdział 1. Teoria liczb
PrzykÅ‚ad 1.29 Liczba 3 jest odwracalna w Z8 bo 3 · 3 = 1 (mod 8). Oprócz 3 w Z8
odwracalne są także 1, 5 i 7.
Lemat 1.30 Liczba a " Zm jest odwracalna wtedy i tylko wtedy, gdy NW D(a, m) = 1.
Dowód. Jeżeli NW D(a, m) = 1, to istnieją liczby całkowite x i y, takie że:
xa + ym = 1,
a więc m dzieli ax - 1, czyli:
ax = 1 (mod m).
Teraz wystarczy przyjąć za a-1 taką liczbę z przedziału od 1 do m - 1, która przystaje
do x modulo m.
Z drugiej strony jeżeli istnieje element a-1 odwrotny do a to
a-1a = 1 (mod m)
czyli
a-1a - 1 = k · m
dla jakiegoś k. Mamy więc
a-1a + (-k)m = 1
czyli NW D(a, m) = 1 (wniosek 1.21).
Z powyższego dowodu wynika, że element odwrotny do a można wyliczyć stosując
algorytm Euklidesa. Na przykład, policzmy element odwrotny do 12 w pierścieniu Z17.
Najpierw zastosujemy algorytm Euklidesa, aby obliczyć x i y, takie że:
12x + 17y = 1.
Kolejne kroki algorytmu przedstawiono w tabeli:
a b xa ya xb yb
17 12 1 0 0 1
5 12 1 -1 0 1
5 2 1 -1 -2 3
1 2 5 -7 -2 3
1 0 5 -7 -12 17
Mamy więc:
5 · 17 + (-7)12 = 1,
czyli:
(-7)12 = 1 (mod 17),
ale:
-7 = 10 (mod 17),
czyli 10 jest elementem odwrotnym do 12 w pierścieniu Z17.
1.11. Funkcja liniowa 17
Definicja 1.31 Zbiór elementów odwracalnych w Zn oznaczamy przez Z" .
n
Przykład 1.32 Z" = {1, 3, 5, 7}.
8
Lemat 1.33 Jeżeli liczba m jest pierwsza, to każdy element a " Zm, a = 0, jest odwra-

calny, czyli pierścień Zm jest ciałem.
Lemat 1.34 Jeżeli a, b " Z" to ab " Z" oraz a-1 " Z" .
n n n
To oznacza, że Z" z mnożeniem jest grupą.
n
Dowód: Elementem odwrotnym do iloczynu ab jest b-1a-1, a elementem odrotnym do
a-1 jest a.
1.11 Funkcja liniowa
Zastanówmy się jak w pierścieniu Zm działa funkcja liniowa
f(x) = a · x (mod m).
Rozpatrzmy najpierw przypadek, gdy a i m są względnie pierwsze, czyli gdy NW D(a, m) =
1. Dla m = 8 i a = 3 wartości funkcji przedstawia tabela
x 0 1 2 3 4 5 6 7
3x 0 3 6 1 4 7 2 5
W takim przypadku istnieje a-1 element odwrotny do a i funkcja g(x) = a-1x, która
jest odwrotna do f. Rzeczywiście
f(g(x)) = aa-1x = x.
Z tego wynika, że f jest wzajemnie jednoznaczna i "na" oraz, że dla każdego b " Zm
równanie
ax = b
ma dokładnie jedno rozwiązanie w pierścieniu Zm, jest ono równe x = a-1b.
Funkcja f jest permutacją w Zm i wykorzystuje się ją, gdy trzeba wymieszać (prze-
permutować) elementy Zm. Zauważmy, że f jest także permutacją w Z" . Rzeczywiście,
m
jeżeli x " Z" , to na podstawie lematu 1.34 f(x) = ax " Z" . Mamy więc
m m
Lemat 1.35 Jeżeli NW D(a, m) = 1, to funkcja f(x) = ax jest funkcją wzajemnie
jednoznacznÄ… w Zm i w Z" .
m
Rozpatrzmy teraz przypadek, gdy a i m nie są względnie pierwsze, czyli gdy NW D(a, m) =
d > 1. Dla m = 8 i a = 6 wartości funkcji przedstawia tabela
x 0 1 2 3 4 5 6 7
6x 0 6 4 2 0 6 4 2
18 Rozdział 1. Teoria liczb
Zauważmy, że jeżeli b jest wartością funkcji f, czyli gdy
ax = b (mod m)
to istnieje takie k, że
ax - b = km,
a ponieważ d dzieli a i m, to d dzieli b, a więc wartościami funkcji f mogą być tylko
liczby podzielne przez d.
Lemat 1.36 Jeżeli NW D(a, m) = d oraz d|b, to równania
ax = b (mod m)
oraz
a b m
x = (mod )
d d d
są równoważne, czyli mają ten sam zbiór rozwiązań w zbiorze liczb całkowitych.
Dowód
ax = b (mod m)
wtedy i tylko wtedy, gdy istnieje k takie że
ax - b = km,
a to zachodzi wtedy i tylko wtedy, gdy istnieje k takie, że
a b m
x - = k ,
d d d
czyli wtedy i tylko wtedy, gdy
a b m
x = (mod ).
d d d
Przypuśćmy teraz, że d dzieli b i rozwiążmy równanie
ax = b (1.2)
w pierścieniu Zm, czyli szukamy takich x " {0, . . . , m - 1}, że
ax = b (mod m) (1.3)
Z lematu 1.36, to równanie jest równoważne równaniu
a b m
x = (mod ) (1.4)
d d d
1.12. Szyfry liniowe 19
a m
Ale teraz NW D( , ) = 1 i równanie (1.4) ma dokładnie jedno rozwiązanie x0 "
d d
m
{0, . . . , - 1} takie że
d
a b m
x0 = (mod ).
d d d
Ale równania (1.4) i (1.3) są spełnione także przez liczby
m m m
x0, x0 + , x0 + 2 , . . . , x0 + (d - 1) .
d d d
Są to wszystkie liczby ze zbioru {0, . . . , m - 1} spełniające równania (1.4) i (1.3), czyli
wszystkie rozwiązania równania (1.2) w pierścieniu Zm.
Przykład 1.37 Rozwiążmy równanie
6x = 9 (mod 15). (1.5)
Ponieważ NW D(6, 15) = 3, więc najpierw rozwiązujemy równanie
2x = 3 (mod 5)
W Z5 mamy 2-1 = 3 wiÄ™c rozwiÄ…zaniem jest x0 = 3 · 3 = 4. Tak wiÄ™c rozwiÄ…zaniami
równaia (1.5) w Z15 są liczby
4, 9, 14.
1.12 Szyfry liniowe
Przypuśćmy, że mamy tekst zapisany za pomocą 26 liter alfabetu łacińskiego:
a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z,
i chcemy ten tekst zaszyfrować. W tym celu utożsamiamy zbiór liter z elementami pier-
ścienia Z26:
a = 0, b = 1, c = 2, . . . , z = 25,
wybieramy dwie liczby a, b " Z26, takie że NW D(a, 26) = 1, i szyfrujemy litera po
literze według wzoru:
C(x) = ax + b (mod 26).
Funkcja deszyfrująca jest określona wzorem:
D(y) = a-1y - a-1b (mod 26).
Rzeczywiście:
D(C(x)) = a-1(ax + b) - a-1b = a-1ax + a-1b - a-1b = x.
Z tego wynika, że funkcja szyfrująca C(x) jest wzajemnie jednoznaczna.
20 Rozdział 1. Teoria liczb
Przykład 1.38 Wybierzmy a = 23 i b = 20 i zaszyfrujmy słowo
matematyka.
W tym celu musimy zaszyfrować 6 liter: m, a, t, e, y oraz k. Obliczenia przedstawiono w
tabeli:
litera x C(x) szyfr
m 12 10 k
a 0 20 u
t 19 15 p
e 4 8 i
y 24 0 a
k 10 16 q
SÅ‚owo matematyka po zaszyfrowaniu wyglÄ…da tak:
kupikupaqu.
Jeżeli zaś zastosujemy ten sam szyfr do początkowego zdania z wiersza Lokomotywa Ju-
liana Tuwima:
stoi na stacji lokomotywa,
to otrzymamy:
spewhuspuotwneqekepagu.
Szyfry liniowe są bardzo starym wynalazkiem. W prostszej wersji z a = 1 stosował je
już Juliusz Cezar. Ich wadą jest to, że bardzo łatwo dają się łamać. Czasami wystarcza od-
gadnąć, jak zaszyfrowano dwie litery. Można to zrobić analizując częstości występowania
liter w zaszyfrowanym tekście.
Przykład 1.39 (kontynuacja przykładu 1.38) W naszym drugim zaszyfrowanym tekście
litera e występuje cztery razy, a litery p i u po trzy razy. Może to nam pomóc w odgadnię-
ciu, że litera e koduje literę o, a litera p koduje literę t. Mamy więc dwa równania:
15 = 19a + b (mod 26),
4 = 14a + b (mod 26).
Po odjęciu tych równań stronami mamy:
11 = 5a (mod 26).
Korzystając z algorytmu Euklidesa, możemy teraz wyliczyć element odwrotny do 5 w pier-
ścieniu Z26. Jest to 21, ponieważ:
(-5)5 + 26 = 1 oraz - 5 = 21 (mod 26),
tak więc:
a = 21 · 11 = 231 = 23 (mod 26).
Teraz z drugiego równania możemy wyliczyć b:
b = 15 - 19 · 23 = 20 (mod 26).
1.13. Chińskie twierdzenie o resztach 21
1.13 Chińskie twierdzenie o resztach
W starożytnych Chinach generałowie używali pewnego ciekawego sposobu liczenia swo-
ich żołnierzy. Dla kilku niewielkich liczb parami względnie pierwszych, na przykład dla:
m1 = 3, m2 = 5, m3 = 7,
obliczano i zapamiętywano reszty z dzielenia liczby żołnierzy przez te liczby. W celu
obliczenia reszt kazano żołnierzom ustawić się trójkami, piątkami i siódemkami. Jeżeli
przy następnym apelu wszystkie trzy reszty były takie same, to znaczyło, że nie brakuje
żadnego żołnierza.
Zobaczmy, jak ten sposób działa. Wez
my najpierw dwie liczby:
m1 = 2 m2 = 3.
W poniższej tabeli mamy zestawione reszty modulo 2 i 3 liczb od 0 do 5:
a a (mod 2) a (mod 3)
0 0 0
1 1 1
2 0 2
3 1 0
4 0 1
5 1 2
Każda z liczb od 0 do 5 = 2 · 3 - 1 ma inny zestaw reszt oraz dla każdej pary reszt
(a1, a2), spełniających warunek 0 d" a1 < 2, 0 d" a2 < 3, istnieje liczba a, taka że:
a1 = a (mod 2),
a2 = a (mod 3).
Oczywiście 6 ma takie same reszty jak 0:
0 = 6 (mod 2), 0 = 6 (mod 3),
i ogólnie, jeżeli dwie liczby a i b różniÄ… siÄ™ o wielokrotność liczby 6 = 2 · 3, czyli:
a = b + k · 6
dla jakiegoś całkowitego k, to
a (mod 2) = b (mod 2),
a (mod 3) = b (mod 3).
Z tego widać, że sposób chińskich generałów, z liczbami 2 i 3, liczy żołnierzy z dokład-
nością do pięciu.
22 Rozdział 1. Teoria liczb
Sytuacja jest inna, jeżeli m1 i m2 nie są względnie pierwsze. Jeżeli, na przykład,
m1 = 4 i m2 = 6, to wÅ›ród liczb od 0 do 23 = 4 · 6 - 1 istniejÄ… takie, które majÄ… takie
same reszty, na przykład 1 i 13:
1 (mod 4) = 13 (mod 4) = 1,
1 (mod 6) = 13 (mod 6) = 1.
Ponadto nie istnieje taka liczba a, dla której:
1 = a (mod 4), 0 = a (mod 6).
Rzeczywiście, z pierwszej równości wynika, że a powinno być nieparzyste, a z drugiej,
że parzyste.
Jeżeli jednak m1 i m2 sÄ… wzglÄ™dnie pierwsze, to każda z liczb od 0 do m1 · m2 - 1 ma
inny zestaw reszt oraz dla każdej pary reszt (a1, a2), spełniających warunek 0 d" a1 <
m1, 0 d" a2 < m2, istnieje liczba a, taka że:
a1 = a (mod m1),
a2 = a (mod m2),
zachodzi bowiem poniższe twierdzenie.
Twierdzenie 1.40 (chińskie twierdzenie o resztach) Niech
m1, m2, . . . , mr
będą dodatnimi liczbami względnie pierwszymi, to znaczy dla każdej pary 1 d" i < j d" r
mamy NW D(mi, mj) = 1, oraz niech
a1, a2, . . . , ar
będą dowolnymi resztami. Wtedy istnieje liczba całkowita a, taka że:
a1 = a (mod m1),
a2 = a (mod m2), (1.6)
. . .
ar = a (mod mr).
Ponadto jeżeli liczby a i b są rozwiązaniami układu kongruencji (??), to ich różnica
a - b dzieli siÄ™ przez iloczyn wszystkich liczb mi, czyli przez:
r
M = mi.
i=1
1.13. Chińskie twierdzenie o resztach 23
Dowód. Najpierw udowodnimy drugą część twierdzenia. Dla każdego 1 d" i d" r mamy:
ai = a (mod mi) oraz ai = b (mod mi).
Po odjęciu stronami tych dwóch równań mamy:
0 = a - b (mod mi),
czyli
mi|(a - b),
Druga część twierdzenia wynika z następującego lematu:
Lemat 1.41 Jeżeli każda spośród liczb mi dzieli a-b i liczby m1, . . . , mr są względnie
pierwsze, to także ich iloczyn M dzieli a - b.
Dowód Lematu. Liczba m1 dzieli a - b, więc istnieje K1 takie, że
a - b = K1 · m1.
Liczba m2 też dzieli a - b, a ponieważ jest względnie pierwsza z m1, więc na podstawie
Lematu 1.24, m2 dzieli K1 i mamy
a - b = K2 · m2 · m1,
dla jakiegoś K2. Podobnie, liczba m3 jest względnie pierwsza z m1, więc dzieli iloczyn
K2 · m2, ale jest także wzglÄ™dnie pierwsza z m2, wiÄ™c dzieli K2 i mamy
a - b = K3 · m3 · m2 · m1,
dla pewnego K3. Powtarzając to rozumowanie r razy dochodzimy do wniosku, że
istnieje takie Kr, że
a - b = Kr · mr · · · m1,
Dowód Lematu, ciąg dalszy. Zobaczymy teraz, że układ (1.6) ma rozwiązanie. Niech
M
Mi = , czyli:
mi
Mi = m1 · · · mi-1mi+1 . . . mr.
Ponieważ Mi i mi mają rozłączne rozkłady, więc NW D(mi, Mi) = 1 oraz istnieje Ni,
takie że:
MiNi = 1 (mod mi).
Zauważmy, że jeżeli i = j, to mi|Mj, oraz że każdy iloczyn miMi ma następującą

własność
miMi = 1 (mod mi),
miMi = 0 (mod mj) dla j = i,

24 Rozdział 1. Teoria liczb
Wez
my teraz:
r
a = aiMiNi.
i=1
Z powyższej własności wynika, że
a = ai (mod mi)
dla każdego i, a więc a jest rozwiązaniem układu równań (1.6).
Przykład 1.42 W przypadku ukłau dwóch równań nasze rozumowanie można trochę upro-
ścić. Wez
my, na przykład, układ
a1 = a (mod 3), (1.7)
a2 = a (mod 5),
Ponieważ 3 i 5 są względnie pierwsze, więc istnieją x i y takie, że
3x + 5y = 1
Za pomocą rozszerzonego algorytmu możemy wyliczyć x i y, mamy
3 · 2 + 5 · (-1) = 1
Teraz zauważmy, że iloczyny 3 · 2 oraz 5 · (-1) majÄ… nastÄ™pujÄ…ce wÅ‚asnoÅ›ci
3 · 2 = 0 (mod 3),
3 · 2 = 1 (mod 5),
5 · (-1) = 1 (mod 3),
5 · (-1) = 0 (mod 5),
Dlatego liczba
a2 · 3 · 2 + a1 · 5 · (-1) = 1
jest rozwiązaniem układu 1.7
PrzykÅ‚ad 1.43 Każda z liczb od 0 do 104 = 3 · 5 · 7 - 1 ma inny zestaw reszt wzglÄ™dem
liczb 3, 5 i 7. Tak więc stosując sposób chińskich generałów z liczbami 3, 5, 7 możemy
liczyć żołnierzy z dokładnością do 104.
Ale sposób chińskich generałów pozwala także stwierdzić, o ile zmieniła się liczba
żołnierzy. Przypuśćmy bowiem, że na porannym apelu było x żołnierzy i uzyskano reszty:
x1 = x (mod 3), x2 = x (mod 5), x3 = x (mod 7),
a na apelu wieczornym było y żołnierzy i otrzymano reszty:
y1 = y (mod 3), y2 = y (mod 5), y3 = y (mod 7),
wtedy różnica x - y spełnia następujący układ kongruencji:
x1 - y1 = x - y (mod 3),
x2 - y2 = x - y (mod 5),
x3 - y3 = x - y (mod 7).
1.14. Obliczenia na dużych liczbach 25
1.14 Obliczenia na dużych liczbach
Chińskie twierdzenie o resztach pozwala wnioskować o dużych liczbach za pomocą ope-
racji na małych liczbach. Zobaczmy teraz kilka przykładów.
Przykład 1.44 Rozważmy następujące równanie.
58 721 569 · 54 567 769 = 71 900 738 · 41 312 424 + 14 969 161 · 15 626 209.
Chińskie twierdzenie o resztach daje możliwość sprawdzenia tego równania operując tyl-
ko na stosunkowo małych liczbach. Sprawdzamy to równanie licząc modulo kilka niedu-
żych liczb względnie pierwszych, na przykład: m1 = 999, m2 = 1000, m3 = 1001,
m4 = 1003, m5 = 1007, m6 = 1009. Jeżeli lewa strona równa się prawej modulo
wszystkie te liczby, to równa się także w liczbach całkowitych, ponieważ iloczyn tych liczb
m1m2m3m4m5m6 > (103)6 = 1018
jest większy od lewej i prawej strony.
Inny sposob, to sprawdzenie tej równości modulo wszystkie liczby pierwsze mniejsze
od 50. Ich iloczyn jest większy od 1017.
Przykład 1.45 Zastanówmy się teraz nad rozwiązaniem równania
x · 56 606 581 = 71 900 738 · 41 312 424 + 14 969 161 · 15 626 209.
Jeżeli spodziewamy się, że rozwiązaniem jest liczba naturalna, to znowu możemy wy-
korzystać obliczenia modulo. Wybieramy dużą liczbę pierwszą p, większą od każdej liczby
występującej w tym równaniu, a następnie rozwiązujemy to równanie w ciele Zp
x = (56 606581)-1 · (71 900 738 · 41 312 424 + 14 969 161 · 15 626 209).
Tak otrzymane rozwiązanie możemy zweryfikować metodą z poprzedniego przykładu.
Stosując tą metodę unikamy zaokrągleń, które przy bardziej skomplikowanych rachun-
kach mogą się kumulować. Można, na przykład, w ten sposób rozwiązywać duże układy
równań liniowych, w których wszystkie współczynniki i rozwiązania są liczbami całkowi-
tymi.
Przykład 1.46 Zastanówmy się, ile wynosi reszta z dzielenia liczby
M = 1 997 199 919
przez 15. A
atwo można policzyć, że: M = 4 (mod 5) oraz M = 1 (mod 3), a więc:
M = 4 (mod 15),
ponieważ 4 jest jedyną liczbą z przedziału 0, 1, 2, . . . , 14, która posiada reszty 4 = 1
(mod 3) oraz 4 = 4 (mod 5).
26 Rozdział 1. Teoria liczb
1.15 Algorytm rosyjskich chłopów mnożenia liczb
W poprzednim podrozdziale obliczaliśmy iloczyny typu
(x · y) (mod m).
Jeżeli wyrażenie to będziemy obliczać najpierw mnożąc, a potem licząc resztę, to wynik
poÅ›redni x · y może być dużo wiÄ™kszy niż m. W tym podrozdziale pokażemy jak obliczać
takie wyrażenia bez dużych wyników pośrednich. W tym celu rozważmy następujący
algorytm mnożenia dwóch liczb. Algorytm ten był stosowany w Rosji.
Aby pomnożyć dwie liczby a i b naturalne postępujemy w następujący sposób:
" Na początku dwóch kolumn wpisujemy a oraz b
" Powtarzamy następujący ciąg instrukcji dopóki na końcu drugiej kolumny pojawi
siÄ™ 0.
Ostatni wyraz w pierwszej kolumnie mnożymy przez dwa,
Ostatni wyraz drugiej kolumny dzielimy przez 2 (bez reszty).
" Następnie dodajemy te wyrazy pierwszej kolumny, dla których w drugiej kolumnie
jest liczba nieparzysta.
Przykład 1.47 Poniższa tabela ilustruje działanie algorytmu podczas obliczania 24 " 20.
Do kolumn z wartściami a i b dodaliśmy na początku kolumnę z numerem rzędu.
i a b
0 24 20
1 48 10
2 96 5
3 192 2
4 384 1
5 768 0
Teraz należy dodać wartości z pierwszej kolumny, które znajdują się w drugim i czwartym
rzędzie, czyli
24 " 20 = 96 + 384 = 480.
Zauważmy, że rzędy są numerowane od zera.
Poprawność algorytmu wynika z faktu, że b może być przedstawione w postaci dwój-
kowej
j
b = di2i.
i=0
Ponieważ cyfry di " {0, 1}, więc b jest sumą potęg dwójki. Na przykład
20 = 16 + 4 = 24 + 22.
1.16. Szybkie potęgowanie 27
Potęga 2i występuje w takiej sumie, jeżeli w rozwinięciu dwójkowym b cyfra di = 1.
Mnożąc 24 przez 20 mamy
24 · 20 = 24 · (24 + 22) = 24 · 24 + 24 · 22,
czyli iloczyn 24 · 20 jest sumÄ… wszystkich liczb postaci 24 · 2i, dla których di = 1. Tak
właśnie liczy algorytm rosyjskich chłopów. W i-tym rzędzie pierwszej kolumny mamy
wartość a " 2i. Jeżeli wyraz w drugiej kolumnie jest nieparzysty to i-ty bit rozwinięcia b
jest równy di = 1.
Zastosujmy teraz algorytm rosyjskich chÅ‚opów do obliczania iloczynu a·b (mod m).
Algorytm mnożenia
Dane wejściowe: czynniki mnożenia a oraz b.
Dane wyjÅ›ciowe: Iloczyn a · b mod m
iloczyn := 0
dopóki b > 0 wykonuj
jeżeli b mod 2 = 1 to
iloczyn := (iloczyn + a) mod m;
a := (2 " a) mod m;
b := b ÷ 2;
Zauważmy, że wyniki pośrednie, i ostateczny, należą do Zm i algorytm nie potrzebuje
zbyt dużej pamięci.
1.16 Szybkie potęgowanie
Teraz zastanowimy się jak można potęgować, czyli jak obliczyć ak mod n dla a " Zn
oraz k " N. Pierwszy nasuwający się algorytm potęgowania polega na k krotnym mno-
żeniu przez a:
y := 1;
dla i od 0 do k wykonuj
y := (y " a) mod n
W kryptografii oblicza się potęgi z wykładnikami posiadającymi po kilkaset bitów. Do
takich zastosowań powyższy algorytm jest nieprzydatny (wymaga on k mnożeń).
Pokażemy teraz jak można potęgować dużo szybciej. Zauważmy, że
a · a = a2, a2 · a2 = a4
i ogólnie
i i i+1
a2 · a2 = a2 .
Dlatego, aby obliczyć potęgę o wykładniku, który jest potęgą dwójki k = 2j należy
wykonać
28 Rozdział 1. Teoria liczb
y := a;
dla i od 0 do j wykonuj
y := (y " y) mod n
Przykład 1.48 Aby obliczyć 216 w Z21 obliczmy
22 = 2 · 2 = 4 (mod 21),
24 = 4 · 4 = 16 (mod 21),
28 = 16 · 16 = 4 (mod 21),
216 = 4 · 4 = 16 (mod 21).
Jeżeli wykładnik jest sumą potęg dwójki k = 2i + 2j, to
i j
ak = a2 · a2 .
Przykład 1.49 Aby obliczyć 220 mod 21 trzeba wymnożyć
220 = 216 · 22 · 4 = 16 · 16 = 4 (mod 21).
Zauważmy, że każda liczba naturalna k jest sumą potęg dwójki
j
k = di · 2i,
i=0
gdzie di " {0, 1} to cyfry rozwinięcia dwójkowego k.
Powyższe uwagi sugerują następujący algorytm obliczania potęgi ak (mod m).
" Na początku dwóch kolumn wpisujemy a oraz k
" Powtarzamy następujący ciąg instrukcji dopóki na końcu drugiej kolumny pojawi
siÄ™ 0.
Ostatni wyraz w pierwszej kolumnie podnosimy do kwadratu modulo m
Ostatni wyraz drugiej kolumny dzielimy przez 2.
" Następnie wymnażamy te wyrazy pierwszej kolumny, dla których w drugiej ko-
lumnie jest liczba nieparzysta.
Jak widać algorytm ten jest podobny do algorytmu mnożenia z poprzedniego rozdziału.
Przykład 1.50 Poniższa tabela ilustruje działanie algorytmu podczas obliczania 85 (mod 21).
Do kolumn z wartściami a i k dodaliśmy na początku kolumnę z numerem rzędu.
i a k
0 8 5
1 1 2
2 1 1
3 1 0
1.17. Pierwiastki kwadratowe 29
Teraz należy wymnożyć wartości z pierwszej kolumny, które znajdują się w zerowym, i
drugim rzędzie, czyli
85 = 8 · 1 = 8 (mod 5).
i
Zauważmy, że w i-tym wierszu pierwszej kolumny mamy potęgę 22 . Jeżeli wyraz w drugiej
kolumnie jest nieparzysty to i-ty bit rozwinięcia k jest równy di = 1.
Poniżej mamy powyższy algorytm w pseudo Pascalu.
Algorytm szybkiego potęgowania
Dane wejściowe: podstawa a oraz wykładnik k.
Dane wyjściowe: Potęga ak mod n
potega := 1
dopóki b > 0 wykonuj
jeżeli b mod 2 = 1 to
iloczyn := (potega · a) mod n;
a := (a " a) mod n;
b := b ÷ 2;
Zauważmy, że wyniki pośrednie, i ostateczny, należą do Zm i algorytm nie potrzebuje
zbyt dużej pamięci. Algorytmu tego nie można stosować do obliczania ak w liczbach
całkowitych, jeżeli k jest duże. Wtedy wynik ostateczny oraz pośrednie będą zbyt duże,
żeby mógł się zmieścić w pamięci komputera.
1.17 Pierwiastki kwadratowe
Definicja 1.51 Liczbę y nazywamy pierwiastkiem kwadratowym liczby x w pierścieniu
Zm, jeżeli
x = y2 (mod m).
Przykład 1.52 W Z5 pierwiastkami 4 są 2 i 3, ponieważ 22 = 32 = 4 (mod 5) a
liczba 2 nie posiada pierwiastka.
Zauważmy, że jeżeli y2 = x (mod m) to
(m - y)2 = m2 - 2my + y2 = y2 = x (mod m),
czyli m - y = -y (mod m), też jest pierwiastkiem x.
Lemat 1.53 Jeżeli m jest liczbą pierwszą i x = y2, to y i -y są jedynymi pierwiastkami
z x.
Dowód Jeżeli z2 = y2 (mod m), to m dzieli z2 - y2 = (z - y)(z + y), a ponieważ m
jest pierwsze to m dzieli z - y lub z + y. W pierwszym przypadku z = y (mod m), w
drugim z = -y (mod m).
30 Rozdział 1. Teoria liczb
Przykład 1.54 Tak nie musi być, jeżeli m nie jest liczbą pierwszą. Na przykład w Z15
mamy cztery pierwiastki z 1, sÄ… to 1, 4, 11 i 14.
Ogólnie rozważmy liczbę m która jest iloczynem dwóch różnych liczb pierwszych
p > q > 2. Wez
my teraz dowolną liczbę y, dla której
y mod p = 1 lub y mod p = -1
oraz
y mod q = 1 lub y mod q = -1
Wtedy
y2 mod p = 1 oraz y2 mod q = 1
czyli z chińskiego twierdzenia o resztach wynika, że
y2 = 1 (mod pq).
Ponieważ p > q > 2, to 1 = -1 (mod p) oraz 1 = -1 (mod q) i mamy wtedy

cztery różne pierwiastki z 1, y1, y2, y3, y4. Są to liczby dla których
y1 mod p = 1, y1 mod q = 1,
y2 mod p = 1, y2 mod q = -1,
y3 mod p = -1, y3 mod q = 1,
y4 mod p = -1 y4 mod q = -1.
Zauważmy, że y1 = 1 (mod n) oraz y4 = -1 (mod n).
1.18 Funkcja Eulera
Definicja 1.55 Funkcja Eulera, jest to funkcja, która liczbie m przypisuje Ć(m) liczbę
elementów odwracalnych w Zm. Z definicji przyjmujemy Ć(1) = 1.
Przykład 1.56 Ć(8) = 4, bo w Z8 odwracalne są {1, 3, 5, 7}.
Podobnie Ć(2) = 1, Ć(3) = 2, Ć(4) = 2, Ć(6) = 2, Ć(9) = 6.
Lemat 1.57 a) Jeżeli p jest liczbą pierwszą, to dla dowolnego ą e" 1, Ć(pą) =
pą-1(p - 1). W szczególności Ć(p) = p - 1.
b) Jeżeli m i n sÄ… wzglÄ™dnie pierwsze, to Ć(m · n) = Ć(m) · Ć(n)
Dowód:
a) Zauważmy że, wśród liczb 0, . . . , pą względnie pierwsze z pą nie są te, które są po-
pÄ…
dzielne przez p, jest ich = pÄ…-1, czyli
p
Ć(pą) = pą - pą-1 = pą-1(p - 1).
1.19. Małe twierdzenie Fermata 31
b) Najpierw zauważmy, ze dla dowolnej liczby x, 0 d" x < mn
NW D(x, mn) = 1
wtedy i tylko wtedy gdy
NW D(x, m) = 1 oraz NW D(x, n) = 1
a to zachodzi wtedy i tylko wtedy gdy reszty rm = x mod m oraz rn = x mod n speł-
niajÄ… warunki
NW D(rm, m) = 1 oraz NW D(rn, n) = 1 (1.8)
Par reszt (rm, rn) speÅ‚niajÄ…cych warunek (1.8) jest Ć(m)·Ä†(n), a z chiÅ„skiego twierdzenia
o resztach każdej liczbie x, 0 d" x < mn odpowiada dokładnie jedna para reszt, i na
odwrót każdej parze reszt odpowiada jedna liczba. Tak więc liczb względnie pierwszych
z mn jest Ć(m) · Ć(n).
1.19 Małe twierdzenie Fermata
Twierdzenie 1.58 (Fermata) Niech a " Z" , wtedy
m
aĆ(m) = 1 (mod m).
Dowód Niech
a1, a2, . . . , aĆ(m)
to będą wszystkie elementy Z" . Jeżeli pomnożymy je przez a
m
aa1, aa2, . . . , aaĆ(m)
to zgodnie z lematem 1.35 otrzymamy te same elementy tylko w innej kolejności.
Wymnóżmy teraz elemnty obu ciągów
Ć(m) Ć(m) Ć(m)
ai = aai = aĆ(m) ai (mod m).
i=1 i=1 i=1
Ć(m)
Po pomnożeniu przez odwrotność ai otrzymamy tezę twierdzenia.
i=1
Wniosek 1.59 Jeżeli p jest liczbą pierwszą, to dla każdego a względnie pierwszego z p
mamy
ap-1 = 1 (mod p).
32 Rozdział 1. Teoria liczb
1.20 Szyfry RSA
W szyfrach one-pad opisanych w rozdziale o funkcjach boolowskich klucz do szyfrowa-
nia jest ten sam co klucz do deszfrowania. W szyfrach liniowych wprawdzie klucze do
szyfrowania i deszyfrowania są różne, ale jaden łatwo można wyliczyć z drugiego. Takie
szyfry nazywamy symetrycznymi.
Teraz zapoznamy się ze sposobem szyfrowania, w których klucz do szyfrowania może
być jawny, nawet ogłaszany publicznie, a klucz do deszyfrowania jest tajny i jest praktycz-
nie niemożliwe wyliczenie klucza tajnego z klucza jawnego. Sposób ten zaproponowali
Rivest, Shamir i Adleman. Przypuśćmy, że Alicja chce utworzyć swój klucz. Bierze w
tym celu dwie duże liczby pierwsze p i q, każda może zawierać po kilkaset bitów. Tworzy
ich iloczyn n = pq. Funkcja Eulera Ć(n) = (p - 1)(q - 1). Następnie Alicja losuje liczbę
e, która jest względnie pierwsza z Ć(n). Skoro NW D(e, Ć(n)) = 1 to istnieje liczba
d, taka, że ed = 1 (mod Ć(n)). Teraz para (e, n) jest jawnym kluczem Alicji i może
być publicznie ogłoszona. Para (n, d) jest kluczem prywatnym Alicji, nie powinna go ona
nikomu zdradzać. Alicja nie powinna też zdradzać rozkładu liczby n na czynniki. Jeżeli
ktoś zna p i q, to może wyliczyć Ć(n) oraz d.
Przypuśćmy, że Bob chce przesłać Alicji jakąś zaszyfrowaną wiadomość x. Traktuje-
my tę wiadomość jako liczbę x < n. (Jeżeli wiadomość jest ciągiem znaków, to kodujemy
każdy znak jako 8 bitów i cały ciąg może być traktowany jako liczba w postaci dwójko-
wej.) Bob szyfruje wiadomość przy pomocy funkcji szyfrującej
CA(x) = xe mod n
i przesyła ją Alicji. Alicja odszyfrowuje za pomocą funkcji deszyfrującej
DA(y) = yd mod n.
Pokażemy teraz, że jeżeli NW D(x, n) = 1, to
DA(CA(x)) = x.
Mamy
DA(CA(x)) = xed mod n.
Ale ed = 1 (mod Ć(n)), więc istnieje k takie, że ed = 1 + kĆ(n), czyli
DA(CA(x)) = x1+kĆ(n) = x · xkĆ(n) (mod n)
ale ponieważ NW D(x, n) = 1, więc mamy
xkĆ(n) = (xĆ(n))k = 1 (mod n).
Tak więc DA(CA(x)) = x. W powyższym rozumowaniu zakładaliśmy, że NW D(x, n) =
1. Ale gdy ktoś trafi na wiadomość x, która nie jest względnie pierwsza z n, to Alicja ma
pecha, ponieważ wtedy można dokonać rozkładu liczby n i złamać jej szyfr.
A
atwo też można pokazać, że CA(DA(x)) = x.
1.21. Testy pierwszości 33
Niesymetryczne szyfry dają nowe możliwości. Można ich na przykład używać do
podpisu. Aby podpisać jakąś wiadomość m, Alicja szyfruje ją swoim szyfrem prywat-
nym DA(m) i jest to podpis wiadomości m. Alicja wysyła Bobowi parę (m, DA(m)).
Żeby sprawdzić, że wszystko się zgadza Bob szyfruje podpis publicznym kluczem Alicji
i sprawdza czy
CA(DA(m)) = m.
1.21 Testy pierwszości
W tym rozdziale zajmiemy się zagadnieniem jak sprawdzić, czy liczba n jest pierwsza.
Możemy sobie wyobrazić, że n ma kilkaset bitów. Jak widać z poprzedniego rozdziału
duże liczby pierwsze mogą być przydatne.
1.21.1 Test naiwny
"
Najprostszy sposób to, dzielić n przez kolejne liczby (pierwsze) aż do n. Jednak ten
test jest zupełnie niepraktyczny, jeżeli n ma kilkaset bitów.
1.21.2 Test Fermata
Drugi test jest algorytmem probabilistycznym i opiera siÄ™ na twierdzeniu Fermata 1.58.
Losujemy liczbę a < n i najpierw sprawdzamy, czy NW D(a, n) = 1. Jeżeli a i n
nie są względnie pierwsze, i NW D(a, n) = d > 1, to d jest dzielnikiem n i n nie jest
pierwsza.
Jeżeli NW D(a, n) = 1, to obliczamy an-1 mod n. Jeżeli an-1 = 1 (mod n), to

orzekamy, że n jest liczbą złożoną. Jeżeli an-1 = 1 (mod n), to orzekamy, że liczba n
jest pierwsza.
Zauważmy, że jeżeli wylosujemy liczbę a, dla której an-1 = 1 (mod n), to wte-

dy mamy pewność, że n nie jest liczbą pierwszą. Wynika to bezpośrednio z twierdze-
nia Fermata1.58. Jeżeli jednak wylosujemy liczbę a względnie pierwszą z n, dla której
an-1 = 1 (mod n), to wtedy możemy popełnić błąd. Liczba n może być złożona, a
mimo to wylosujemy pechowo i an-1 = 1 (mod n).
Przykład 1.60 W przykładzie 1.50 pokazano, że 85 = 8 (mod 21). Z tego wynika,
że 810 = 82 = 1 (mod 21) oraz , że 820 = 1 (mod 21).
Definicja 1.61 Taką liczbę a, dla której NW D(a, n) = 1 oraz an-1 = 1 (mod n) bę-

dziemy nazywać świadkiem złożoności dla n, ponieważ zaświadcza ona, że n jest złożona.
Przykład 1.62 Jak pokazano wyżej 8 nie jest świadkiem złożoności dla 21. W przykła-
dzie 1.49 pokazaliśmy, że 220 = 4 (mod 21), czyli 2 jest świadkiem złożoności
liczby 21.
Zachodzi następujący lemat.
34 Rozdział 1. Teoria liczb
Lemat 1.63 Jeżeli istnieje takie a " Z" , że an-1 = 1 (mod n), to przynajmniej poło-

n
wa elementów Z" jest świadkiem Fermata dla n.
n
Dowód. Przypuśćmy, że
{b1, . . . , bk}
są to wszystkie elementy Z" , dla których bn-1 = 1 (mod n). Wtedy po pomnożeniu
n i
przez a otrzymamy k elementów
{ab1, . . . , abk}
różnych między sobą (lemat 1.35), z których każdy jest świadkiem Fermata. Rzeczywi-
ście
(abi)n-1 = an-1bn-1 = an-1 = 1 (mod n).

i
A więc świadków złożoności jest co najmniej połowa.
Jeżeli n jest pierwsze, to z Twierdzenia Fermata, algorytm zawsze orzeknie dobrze.
Z lematu 1.63 wynika, że jeżeli n jest złożona i istnieje świadek Fermata dla n, to takich
świadków jest co najmniej połowa, i nasz algorytm pomyli się z prawdopodobieństwem
1
. Prawdopodobieństo, to można zmniejszyć poprzez powtórzenie algorytmu r razy, z
2
różnymi wylosowanymi a.
Istnieją jednak liczby złożone n, które nie mają świadków złożoności. Na przykład
n = 561. KÅ‚opot bierze siÄ™ stÄ…d, że 561 = 3 · 11 · 17, a 560 = 561 - 1 dzieli siÄ™ przez
2 = 3 - 1, 10 = 11 - 1 oraz przez 16 = 17 - 1. Dlatego dla dowolnego a, jeżeli
NW D(a, 561) = 1, to a jest względnie pierwsze z 3, 11 i 17 oraz mamy
a560 = (a2)280 = 1 (mod 3)
a560 = (a10)56 = 1 (mod 11)
a560 = (a16)35 = 1 (mod 17)
i z chińskiego twierdzenia o resztach wynika, że
a560 = 1 (mod 561)
Takie liczby nazywajÄ… sie liczbami Carmichaela. Pierwsze trzy z nich to 561, 1105 i 1729.
Występują one bardzo rzadko, jest ich tylko 255 wśród liczb mniejszych od 100 000 000.
1.21.3 Test Millera-Rabina
Zakładamy, że n jest nieparzyste (2 jest jedyną parzystą liczbą pierwszą). Najpierw spraw-
dzamy, czy n jest potęgą jakiejś liczby naturalnej. Dla ą od 2 do log2 n sprawdzamy czy
n = kÄ…, dla jakiegoÅ› k. W rozdziale o arytmetyce opisano jak za pomocÄ… binary search
stwierdzić, czy liczba jest potęgą innej liczby. Jeżeli n jest potęgą, to jest złożona.
Ponieważ n jest nieparzyste, to n - 1 możemy przedstawić w postaci
n - 1 = m · 2k.
1.21. Testy pierwszości 35
dla jakiegoÅ› m nieparzystego.
Losujemy a < n. Sprawdzamy, czy NW D(a, n) = 1 (jeżeli NW D(a, n) > 1, to n
jest złożona).
Następnie obliczamy am mod n. Jeżeli am mod n = 1, to koniec, stwierdzamy, że n
jest pierwsza. Jeżeli am mod n = 1, to obliczamy po kolei

2 k
am2 mod n, am2 mod n, . . . , am2 mod n.
Zauważmy, że w tym ciągu każda liczba jest kwadratem poprzedniej. Jeżeli wśród tych
liczb nie ma jedynki, to z twierdzenia Fermata wynika, że n jest złożona, bo wtedy
k
am2 = an-1 = 1 (mod n).

Jeżeli w tym ciągu jest jedynka, na przykład
i
am2 = 1 (mod n)
i-1
to patrzymy na poprzedni element x = am2 . Jeżeli x = -1, to orzekamy, że n jest

liczbą złożoną. Znależliśmy nietrywialny pierwiastek z 1, a z twierdzenia 1.53 wynika,
że jest to możliwe tylko wtedy gdy n nie jest pierwsze. Jeżeli x = -1, to orzekamy, że n
jest pierwsze.
A
atwo więc widać, że jeżeli n jest pierwsze, to test zawsze odpowie prawidłowo,
niezależnie od losowania. Wiadomo też, że jeżeli n jest złożona i nie jest potęgą liczby
1
pierwszej, to z prawdopodobieństwem większym niż wykryjemy to. Dowód tego faktu
2
wybiega poza zakres tej książki i pomijamy go.
Przykład 1.64 Prześledz
my algorytm Millera-Rabina dla n = 21 i a = 8.
n - 1 = 20 = 5 · 22.
W przykładzie 1.50 pokazaliśmy, że
85 = 8 (mod 21).
Teraz podnosimy 8 do kwadratu i otrzymujemy
85·2 = 82 = 1 (mod 21).
W tym momencie algorytm znalazł nietrywialny pierwiastek 1 i orzeka, że 21 jest liczbą
złożoną.
W praktyce stosujemy wszystkie trzy testy na raz. MajÄ…c nieparzystÄ… liczbÄ™ n, naj-
pierw sprawdzamy, czy dzieli siÄ™ ona przez kilka kolejnych liczb pierwszych
p1, p2, . . . , pd.
Dobór d zależy od tego jak duże liczby sprawdzamy. W ten sposób eliminujemy dużą
część liczb. Zauważmy, że obliczając iloczyn tych liczb
d
x = pi
i=1
36 Rozdział 1. Teoria liczb
i sprawdzając, czy NW D(x, n) = 1 możemy za jednym razem sprawdzić, czy n dzieli
się przez którąś z tych liczb. Po przejściu pierwszego testu stosujemy test drugi, a gdy
liczba n go przejdzie stosujemy test trzeci. Ponieważ liczby Carmichaela są dość rzadkie,
więc drugi test wyeliminuje większość liczb złożonych.
1.21.4 Losowanie liczb pierwszych
Jeżeli chcemy wyklosować liczbę pierwszą to losujemy nieparzystą liczbę, a mastępnie
sprawdzamy, czy jest ona pierwsza. Jeżeli nie, to sprawdzamy następne liczby n + 2, n +
4, ....
1.22 Zadania
1. Podziel (oblicz ilorazy i reszty) liczb 175 oraz 1754 przez 11.
2. Dla każdej z liczb:x = 8, -8, 120 oraz -120 znajdz
liczbÄ™ y " {0, 1, 2, 3, 4} takÄ…,
że x = y (mod 5).
3. Oblicz: a) (50 · 51 + 15) mod 7, b) 15 · 36 mod 7; c) 153 · (37)3 mod 7.
4. Oblicz: a) 264 " 18 + 2002) mod 5,
5. Oblicz: a) 1039 mod 11, b) 239 mod 5 c) 740 mod 10.
6. Przedstaw klasy abstrakcji relacji kongruencji dla m = 6.
7. Jak wyglądają działania dodawania i mnożenia w pierścieniu Z6
8. W pierÅ›cieniu Z8 wykonaj dziaÅ‚ania 7 + 6 oraz 7 · 6.
9. W pierścieniu Z8 rozwiąż równania: a) 1 + x = 0, b) 1 + x = 2, c) 5 + x = 0, d)
5 + x = 2.
10. Podaj tabliczkę dodawania i mnożenia w ciele Z7. Podaj elementy odwrotne do 5 i
6 w Z7.
11. Dla liczb a = 600 i b = 1050 oblicz NW D(a, b) oraz liczby całkowite x i y
spełniające równanie xa + yb = NW D(a, b).
12. Oblicz NW D(667, 713).
13. Oblicz NW D(199816, 199819).
14. W pierÅ›cieniu Z5 rozwiąż równania: a) 4 · x = 1, b) 4 · x = 2.
15. W pierÅ›cieniu Z8 rozwiąż równania: a) 3 · x = 1, b) 3 · x = 2.
16. W pierścieniu Z17 rozwiąż równania: a) 8x = 2, b) 9x = 4.
17. W pierścieniu Z14 rozwiąż równania: a) 6x = 2, b) 6x = 9.
1.22. Zadania 37
18. Znajdz
liczby całkowite x i y spełniające równanie: 17x + 40y = 1.
19. Podaj rozkład na czynniki pierwsze liczb 240 oraz 111.
20. Ile dzielników ma liczba 240?
21. Znajdz
elementy odwrotne do wszystkich elementów dwracalnych w Z12.
22. Udowodnij, że dla każdego a " Zm istnieje co najwyżej jeden element odwrotny
a-1.
23. Przedstaw tabelÄ™ funkcji f(x) = 4 · x + 5 w pierÅ›cieniu Z13.
24. Przedstaw tabelÄ™ funkcji f(x) = 4 · x + 5 w pierÅ›cieniu Z12.
25. Rozwiąż układ kongruencji:
3 = a (mod 5),
5 = a (mod 6).
26. Sprawdz
, czy 100136 = 200146 (mod 30)
27. Dla jakich par reszt (a1, a2) istnieją liczby a spełniające układ kongruencji:
a1 = a (mod 4),
a2 = a (mod 6).
28. Które elementy Z12 są resztami kwadratowymi?
29. Które elementy Z13 są resztami kwadratowymi?
30. Ile jest pierwiastków z 1 w Z30?
31. Pokaż, że w Z105 jest osiem pierwiastków z 1.
32. Przy pomocy algorytmu szybkiego potęgowania oblicz: a) 414 mod 15; b)864 mod
65; c) 1264 mod 65; d)1464 mod 65; e) 1032 mod 33.
33. Przeprowadz
test Fermata dla: a) n = 15 oraz a = 4; b) n = 65 oraz a = 8; c)
n = 65 oraz a = 12.
34. Przeprowadz
test Millera-Rabina dla: a) n = 39 oraz a = 5; b) n = 65 oraz
a = 8; a) n = 65 oraz a = 12.
35. Oblicz: a) Ć(24); b) Ć(120).
36. Niech &! = {0, 1, . . . , 59}, będzie przestrzenią zdarzeń elementarnych z jednostaj-
nym rozkładem prawdopodobieństwa. Określmy na &! trzy zmienne losowe
X4(É) = É mod 4
X5(É) = É mod 5
X6(É) = É mod 6
Pokaż, że zmienne X5 i X6 są niezależne, a zmienne X4 i X6 nie są niezależne.
38 Rozdział 1. Teoria liczb
37. Niech &! = {0, 1, . . . , 104}, będzie przestrzenią zdarzeń elementarnych z jedno-
stajnym rozkładem prawdopodobieństwa. Określmy na &! trzy zmienne losowe
X3(É) = É mod 3
X5(É) = É mod 5
X7(É) = É mod 7
Pokaż, że zmienne X5, X5 i X7 są niezależne.
1.23 Problemy
1.23.1 Największy wspólny dzielnik
1. Udowodnij, że każda liczba postaci xa + yb, dla x i y całkowitych, jest wielo-
krotnością NW D(a, b), i na odwrót, każda wielokrotność NW D(a, b) jest postaci
xa + yb, dla jakiś x i y całkowitych.
2. Udowodnij, że NW D(a, b) jest najmniejszą dodatnią liczbą d, dla której istnieje x
i y całkowite, takie że xa + yb = d.
3. Zaprojektuj algorytm obliczania największego wspólnego dzielnika trzech (lub k)
liczb.
4. Które z liczb caÅ‚kowitych można przedstawić w postaci x · 10 + y · 21 (x i y " Z)?
5. Które z liczb caÅ‚kowitych można przedstawić w postaci x · 10 + y · 12 (x i y " Z)?
6. Niech r1, ... , rk będzie ciągiem kolejnych reszt uzyskiwanych w alorytmie Eukli-
ri
desa. Pokaż, że dla każdego i d" k - 2, mamy ri+2 < .
2
1.23.2 Najmniejsza wspólna wielokrotność
Niech NW W (a, b) oznacza najmniejszą wspólną wielokrotność liczb a i b.
1. Udowodnij, że NW W (a, b) dzieli każdą inną wspólną wielokrotność liczb a i b.
2. Pokaż, że NW W (a, b) · NW D(a, b) = a · b.
3. Jakie liczby całkowite dzielą się jednocześnie przez 24 i przez 54?
1.23.3 Liczby względnie pierwsze
Udowodnij, że jeżeli m jest względnie pierwsze z a i b, to m jest względnie pierwsze z
iloczynem tych liczb ab.
Jako wniosek udowodnij, że jeżeli m jest względnie pierwsze z każdą z liczb m1, ..., mk,
k
to m jest względnie pierwsze z iloczynem tych liczb mi.
i=1
1.23. Problemy 39
1.23.4 Liczby pierwsze
1. Udowodnij, że dla każdego k istnieje ciąg k kolejnych liczb złożonych.
2. Udowodnij, że liczb pierwszych jest nieskończenie wiele.
3. Udowodnij, że jeżeli dwie liczby x i y spełniają warunki: x2 = y2 (mod n) oraz
x = y (mod n) i x = -y (mod n), to NW D(x+y, n) = d jest nietrywialnym

dzielnikiem n.
1.23.5 Chińskie twierdzenie o resztach
Z chińskiego twierdzenia o resztach wynika, że jeżeli NW D(m, n) = 1, to funkcja
f(x) = (x mod m, x mod n)
stanowi wzajemnie jednoznaczne odwzorowanie pomiędzy Zmn a iloczynem kartezjań-
skim Zm × Zn.
Na iloczynie kartezjaÅ„skim Zm × Zn możemy okreÅ›lić dziaÅ‚ania dodawania i mnoże-
nia w następujący sposób:
(a, b) + (c, d) = (a + b, c + d) (a, b) · (c, d) = (a · b, c · d).
A
atwo można sprawdzić, że zbiór Zm × Zn z tak okreÅ›lonymi dziaÅ‚aniami, jest pierÅ›cie-
niem. Ponadto funkcja f speÅ‚nia warunki f(x+y) = f(x)+f(y) oraz f(x·y) = f(x)·(y).
1.23.6 System one-pad
System  one-pad (porównaj rozdział o funkcjach boolowskich) może być stosowany
do ciągów liter alfabetu łacińskiego. Wtedy utożsamiamy litery z liczbami od 0 do 25 i
zamiast operacji •" stosujemy:
x + k (mod 26),
czyli resztÄ™ z dzielenia (x + k) przez 26. Jak wyglÄ…da wtedy operacja deszyfrowania?
Pokaż, że system one-pad z literami jest równie bezpieczny jak system z dwoma cyframi
0 i 1.
1.23.7 Przestrzeń liniowa
Zbiór B = {0, 1} z dziaÅ‚aniami xor •" oraz koniunkcji · jest ciaÅ‚em Z2.
Udowodnij, że zbiór Bn jest przestrzeniÄ… liniowÄ… nad ciaÅ‚em {0, 1}, z •" jako doda-
waniem oraz mnożeniem przez skalar zdefiniowanym przez:
" 0 · x = 0 (tutaj zero po lewej stronie jest zerem z ciaÅ‚a, a zero po prawej stronie jest
wektorem zerowym),
" 1 · x = x.
40 Rozdział 1. Teoria liczb
1.23.8 Uogólnienie małego twierdzenia Fermata
Udowodnij
Twierdzenie 1.65 Niech G będzie dowolną grupą. Wtedy dla dowolnego a " G
a|G| = 1
.
1.23.9 Algorytm Euklidesa dla wielomianów
Rozważmy zbiór wielomianów, którego współczynniki są elementami jakiegoś ciała, na
przykład zbioru liczb rzeczywistych lub Z2. W pierwszym rozdziale pokazaliśmy jak
można dzielić wielomiany i dla dwóch wielomianów p i q wyliczyć iloraz i resztę z dzie-
lenia. Mówimy, że wielomian p dzieli wielomian q, jeżeli istnieje wielomian r taki, że
p · r = q. Można też dla wielomianów p i q zdefiniować najwiÄ™kszy wspólny dzielnik,
jako taki wielomian d, który dzieli p i q oraz jest podzielny przez każdy wspólny dzielnik
wielomianów p i q. Pokaz
, że
1. Algorytm Euklidesa oblicza największy wspólny dzielnik dla wielomianów.
2. Jeżeli NW D(p, q) = d, to istniejÄ… wielomiany x i y, takie, że p · x + q · y = d.
3. Można zdefiniować w pierścieniu wielomianów relację przystawania modulo wie-
lomian m, która ma podobne własności do relacji kongruencji modulo w liczbach
całkowitych.