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.