Teoria liczb-

matematyka

Teoria liczb jest dziedziną matematyki, zajmującą się badaniem
własności liczb – początkowo tylko naturalnych.

Obecnie należałoby powiedzieć: głownie naturalnych. Jej początki
sięgają starożytności. Zajmowali się nią Pitagoras, Euklides,
Eratostenes, Diofantos i wielu innych.

Bujny rozwój teorii liczb datuje się mniej więcej od czasów
działalności Pierre'a Fermata (1601-1665), autora wypowiedzi
słynnego Wielkiego Twierdzenia Fermata. Do dwudziestego wieku
powszechną była opinia, iż teoria ta nie ma żadnego
zastosowania. Jednak dzięki wielkiemu rozwojowi kryptografii -
nauki zajmującej się układaniem i łamaniem szyfrów - pogląd ten
musiał zostać zweryfikowany.

Zacznijmy od przypomnienia szkolnego algorytmu dzielenia liczb
naturalnych. Podzielmy 1743 przez 12.

W wyniku dzielenia otrzymaliśmy iloraz 145 i resztę 3. Liczby te
spełniają równanie
1743 = 145*12 + 3 i reszta jest mniejsza od dzielnika.

Podobnie możemy postąpić dla dowolnych liczb a i b, pod warunkiem,
że b



0.

Twierdzenie 6.1 Dla dowolnych liczb naturalnych a oraz b > 0 istnieje
dokładnie jedna para liczb naturalnych q i r spełniających warunki:
1. a = bq + r
2. 0 r < b

q nazywa się ilorazem całkowitoliczbowym a przez b, a r nazywa się
resztą z dzielenia.

Zauważmy, że iloraz q jest zaokrągleniem w dół normalnego ilorazu;

Iloraz całkowitoliczbowy liczb a i b będziemy oznaczać przez

a resztę przez a mod b.

Przykład

Podzielność liczb

Liczbę a nazywamy dzielnikiem liczby b.

Relacja kongruencji

Przykład 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 6.2 Relacja przystawania modulo jest relacją równoważności,
czyli spełnia następujące trzy warunki:

1. zwrotność, dla każdego a zachodzi a = a (mod m),

2. symetrię, dla każdego a i b, jeżeli a = b (mod m); to b = a (mod
m),

3. przechodniość, dla każdego a, b i c, jeżeli a = b (mod m) i b = c
(mod m); to a = c (mod m).

Ponadto relacja modulo jest zgodna z dodawaniem, odejmowaniem
i mnożeniem.

Twierdzenie 6.3 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).

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:

Przykład: Dla m=3 mamy trzy klasy abstrakcji:

Zauważmy, że klasy abstrakcji elementów równoważnych pokrywają się.

Lemat 6.4. Jeżeli x = y (mod m); to [x] = [y].

Następna ważna własność klas abstrakcji to ich rozłączność.

Lemat 6.5. Jeżeli [x]



[y]  , to [x] = [y], inaczej, dwie klasy

abstrakcji [x] i [y] albo są identyczne, albo są rozłączne.

Pierścień Z

m

Klasy abstrakcji relacji modulo m wyglądają następująco:
[0], [1],...,[m - 1].

Dla dowolnego k z przedziału 0



k



m- 1, klasa [k] jest postaci:

z dodawaniem i mnożeniem określonym następującymi tabelami:

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:

Pierścień Z

5

Pierścień Z

4

Rozważmy teraz pierścień reszt modulo 4:

gdzie dodawanie i mnożenie jest określone następującymi tabelami:

W tym pierścieniu nie ma elementu odwrotnego do 2. Ponadto mamy
2



2= 0.

Zauważmy, że każdy element oprócz zera ma w tym pierścieniu
element odwrotny względem mnożenia, czyli

Największy wspólny dzielnik.

Dla dwóch liczb całkowitych a i b, ich największy wspólny
dzielnik to największa liczba całkowita n, która dzieli a i b.
Największy wspólny dzielnik liczb a i b będziemy oznaczać przez
NWD(a, b). Na przykład: NWD(4, 6) = 2, NWD(4, 0) = 4.

Największy wspólny dzielnik dwóch liczb dodatnich można
obliczyć za pomocą algorytmu Euklidesa.

Algorytm Euklidesa: Aby obliczyć największy wspólny dzielnik
dwóch dodatnich liczb naturalnych a, b, powtarzamy aż do skutku:

czyli q=0, sprzeczność.

* dopóki a



b  0, wykonuj:

** jeżeli a



b, to a := a mod b,

** w przeciwnym wypadku b := b mod a.
* NWD(a, b) = 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:

Algorytm Euklidesa można tak zmodyfikować, aby oprócz
największego wspólnego dzielnika NWD(a, b), wyliczał
także liczby x i y, takie że: xa + yb = NWD(a, b).

Rozszerzony algorytm Euklidesa.

Dane wyjściowe: NWD(a,b) oraz liczby całkowite x,y takie, że
xa + yb = NWD(a, b).

Dane wejściowe: dwie liczby naturalne a,b.

* podstaw: xa := 1, ya := 0, xb := 0, yb := 1.

* dopóki a



b  0, wykonuj:

** jeżeli a



b, to a := a mod b,

xa := xa – xb



(a



b);

ya := ya – yb



(a



b);

** w przeciwnym wypadku: b := b mod a,
xb := xb – xa



(b



a);

yb := yb – ya



(b



a).

* NWD(a,b): = 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 Euklidesa 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.

Liczby pierwsze i względnie pierwsze.

Dwie liczby naturalne a i b są względnie pierwsze, jeżeli NWD(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.

Twierdzenie: Liczb pierwszych jest nieskończenie wiele.

Rozkład liczby 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:

Twierdzenie 6.6. Każdą liczbę naturalną n > 1 można przedstawić jako
iloczyn liczb pierwszych (niekoniecznie różnych):
n = q

1

q

2

...q

r

Zasada minimum. W każdym niepustym zbiorze liczb naturalnych
istnieje liczba najmniejsza

.

Lemat Euklidesa: Jeżeli n|ab i NWD(a,n) = 1, to n|b.

Twierdzenie 6.7. Każdą liczbę naturalną n > 1 można w dokładnie
jeden sposób przedstawić w postaci iloczynu:

gdzie



i są dodatnimi liczbami naturalnymi, pi są liczbami pierwszymi

oraz zachodzi

Elementy odwracalne.

Twierdzenie 6.7.

Przykład.

Rozwiązywanie równań z kongruencją.

Jeśli mamy równanie

to rozwiązaniem jest

Przykład Rozwiązać równanie 2x



101 (mod 637).

Funkcja Eulera.

Twierdzenie Eulera

Przykład. Za pomocą twierdzenia Eulera obliczyć 129 podniesione
do potęgi 209 modulo 18.

Twierdzenie chińskie o resztach.

Kod RSA.

Niech litery alfabetu – liczby 1-26; pauza 27, pozostałe znaki-
powyżej 27.

Z danego słowa otrzymujemy liczbę L.

Na przykład: ADAM: 01040113; L=1040113.

Niech p, q- liczby względnie pierwsze, r = p



q, L



<0,r).

Niech s- liczba naturalna taka, że NWD(s,p-1)=1 i NWD(s, q-1)=1.

Kod C liczby L obliczamy według wzoru:

Jak odkodować liczbę L ?

Z tego, że NWD(s,p-1)=1 wynika, że istnieją liczby całkowite a, b
takie, że sa+(p-1)b = 1.

W takim razie

(ponieważ z twierdzenia Eulera mamy, że

).

Podobnie, z tego, że NWD(s,q-1)=1 otrzymamy,
że

L otrzymamy rozwiązując układ równań:

Przykład Dla p=13, q=17, s=5 zakodować AB.