Matematyka dyskretna, wykład 9
Teoria liczb cz.1.
Gliwice, 23.04.2009
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Teoria liczb
Teoria liczb jest dziedzinÄ… matematyki, zajmujÄ…cÄ… siÄ™ badaniem
własności liczb  początkowo tylko naturalnych, i do dziś dla wielu
specjalistów są one szczególnie atrakcyjne.
Początki teorii liczb sięgają starożytności. Zajmowali się nią Pitagoras,
Euklides, Eratostenes, Diofantos i wielu innych (także Archimedes, ale
raczej marginesowo; nowe odkrycia historyczne mogą ten pogląd zmienić).
Bujny rozwój teoria liczb zawdzięcza w wielkiej mierze Pierre owi
Fermatowi (1601-1665), autorowi słynnej hipotezy, zwanej Wielkim
Twierdzeniem Fermata. Ogromny wkład w rozwój teorii liczb miał Carl
Friedrich Gauss. Z polskich matematyków znaczące wyniki w teorii liczb
uzyskali między innymi Wacław Sierpiński, Andrzej Schinzel i Henryk
Iwaniec. Posiadaczem szeregu wyliczeniowych rekordów światowych jest
Jarosław Wróblewski.
Badania w zakresie teorii liczb przyczyniły się do znacznego rozwoju
wielu gałęzi matematyki: algebry, teorii funkcji zmiennej zespolonej,
rachunku prawdopodobieństwa, geometrii algebraicznej i innych.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Teoria liczb
Dzielenie liczb całkowitych z resztą
Niech b > 0, wtedy dla każdej liczby całkowitej a istnieją
jednoznacznie wyznaczone q, r " Z takie, że:
a = qb + r i 0 r < b.
LiczbÄ™ q nazywamy ilorazem, liczbÄ™ r nazywamy resztÄ….
Definicja
Mówimy, że liczba całkowita b jest podzielna przez liczbę
całkowitą a, jeżeli istnieje liczba całkowita q taka, że b = qa.
Piszemy wtedy a|b (a dzieli b).
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Teoria liczb
Własności relacji podzielności w zbiorze Z
Dla dowolnych a, b, c " Z zachodzi:
1
jeśli a|b to a|bc,
2
jeśli a|b i b|c to a|c,
3
jeśli a|b, a|c to a|(b + c).
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Teoria liczb
Własności relacji podzielności w zbiorze Z
Dla dowolnych a, b, c " Z zachodzi:
1
jeśli a|b to a|bc,
2
jeśli a|b i b|c to a|c,
3
jeśli a|b, a|c to a|(b + c).
Dowód. 1. Jeśli a|b to istnieje q " Z takie, że
b = aq Ò! bc = a cq Ò! a|bc.

"Z
2. Jeżeli a|b i b|c wtedy istnieją q1, g2 " Z takie, że
b = aq1 '" c = bq2 Ò! c = a q1q2 Ò! a|c.

"Z
3. Jeżeli a|b i a|c wtedy istnieją q1, g2 " Z takie, że
b = aq1 '" c = aq2 Ò! b + c = aq1 + aq2 = a (q1 + q2) Ò! a|(b + c).

"Z
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Największy wspólny dzielnik
Definicja
Dla dowolnych liczb a, b " Z największym wspólnym dzielnikiem
tych liczb nazywamy liczbę d = NWD(a, b) taką, że:
d|a oraz d|b,
jeżeli istnieje e " Z takie, że e|a oraz e|b to e|d.
Oczywiście 1 NWD(a, b) min (|a|, |b|).
Ponieważ NWD(a, b) = NWD(|a|, |b|) możemy ograniczyć się do
przypadku a, b > 0.
Zauważmy, że NWD(a, b) = NWD(b, a), a zatem będziemy
zakładać ponadto, że b a > 0.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Największy wspólny dzielnik - Algorytm Euklidesa
Algorytm Euklidesa
Wykonujemy następującą procedurę
b = q1a + r1, 0 < r1 < b
a = q2r1 + r2, 0 < r2 < r1
r1 = q3r2 + r3, 0 < r3 < r2
. . . . . . . . . . . . . . . . . . . . . . . . . . .
rn-2 = qnrn-1 + rn 0 < rn < rn-1
rn-1 = qn+1rn + 0
Procedura musi się zakończyć ponieważ r1 > r2 > . . . > rn 0.
Wtedy rn = NWD(a, b).
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Największy wspólny dzielnik - Algorytm Euklidesa
Dowód. Na początku udowodnimy, że jeśli b = qa + r, to
NWD(a, b) = NWD(a, r).
Jeśli d = NWD(a, b), to d|a oraz d|b, a więc d|r = b - aq, czyli
d|NWD(a, r) = c.
Z drugiej strony c|a oraz c|r, a więc c|aq + r = b, czyli c|d.
Ostatecznie c = d.
Zasadność algorytmu Euklidesa wynika z ciągu równości
NWD(b, a) = NWD(a, r1) = NWD(r1, r2) = · · · = NWD(rn-1, rn) = NWD(rn, 0) = rn.
Przykład. NWD(12378, 3054) =?
12378 = 4 · 3054 + 162
3054 = 18 · 162 + 138
162 = 1 · 138 + 24
138 = 5 · 24 + 18
24 = 1 · 18 + 6
18 = 3 · 6 + 0 czyli NWD(12378, 3054) = 6.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Największy wspólny dzielnik - Algorytm Euklidesa
Przebieg algorytmu Euklidesa obliczania NWD(a, b):
1
oblicz c jako resztÄ™ z dzielenia b przez a
2
zastÄ…p pozycjÄ™ b liczbÄ… a, a pozycjÄ™ a liczbÄ… c
3
jeżeli pozycja a = 0, to szukane NWD = b, w przeciwnym
wypadku przejdz
do 1.
Zapis w pseudokodzie:
NWD(liczba całkowita a, liczba całkowita b)
dopóki a != 0
c := reszta z dzielenia b przez a
b := a
a := c
zwróć a
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozszerzony Algorytm Euklidesa
Poza znajdowaniem NWD dwóch podanych liczb a, b > 0 algorytm
Euklidesa można zastosować do wskazania dwu dodatkowych liczb
x, y " Z takich, że
ax + by = NWD(a, b).
Już sam fakt, że istnieją takie liczby x, y to obserwacja, która leży
u podstaw wielu kolejnych twierdzeń. Ponadto rozszerzony
algorytm Euklidesa jest intensywnie stosowany do rozwiÄ…zywania
równań, w przekształceniach kryptograficznych.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozszerzony Algorytm Euklidesa
Rozszerzenie Algorytmu Euklidesa
Załóżmy, że a > b. Niech r0 = a, r1 = b, natomiast r2 . . . , rn, rn+1 będą
kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym
rn+1 = 0. Wtedy wiemy, że rn = NWD(a, b) oraz
rn-1 = qn-1 · rn,
rn-2 = qn-2 · rn-1 + rn,
rn-3 = qn-3 · rn-2 + rn-1,
.
.
.
r1 = q1 · r2 + r3,
r0 = q0 · r1 + r2,
dla pewnych q0, q1, . . . , qn-1. Mamy zatem
rn-2 - qn-2 · rn-1 = NWD(a, b). Załóżmy indukcyjnie, dla 0 < i n - 2,
że istniejÄ… x, y " Z takie, że ri · x + ri+1 · y = NWD(a, b). Ponieważ
ri+1 = ri-1 + qi-1 · ri otrzymujemy:
NWD(a, b) = ri · x + ri+1 · y
= ri · x + (ri-1 + qi-1 · ri ) · y
= ri-1 · y + ri · (x + qi-1 · y).
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozszerzony Algorytm Euklidesa
A więc możemy zejść z liczbą i do i = 0, co daje pożądane
przedstawienie NWD(a, b) jako r0 · x + r1 · y = ax + by.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozszerzony Algorytm Euklidesa
A więc możemy zejść z liczbą i do i = 0, co daje pożądane
przedstawienie NWD(a, b) jako r0 · x + r1 · y = ax + by.
Przykład. Szukamy x, y " Z takich, że
44x + 390y = NWD(44, 390).
Stosujemy algorytm Euklidesa
390 = 8 · 44 + 38 Ò! 38 = 390 - 8 · 44
44 = 1 · 38 + 6 Ò! 6 = 44 - 1 · 38
38 = 6 · 6 + 2 Ò! 2 = 38 - 6 · 6
6 = 3 · 2 + 0
a zatem NWD(44, 390) = 2. Dalej
2 = 38 - 6 · 6 = 38 - 6 · (44 - 1 · 38) = 38 - 6 · 22 + 6 · 38 =
= 7 · 38 - 6 · 44 = 7 · (390 - 8 · 44) - 6 · 44 =
= 7 · 390 - 56 · 44 - 6 · 44 = 7 · 390 - 62 · 44.
StÄ…d 44 · -62 +390 · 7 = 2.


y
x
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Równanie Diofantyczne
Szukamy rozwiązań całkowitych równania
ax + by = c, a, b, c " Z.
Równanie te nazywamy równaniem diofantycznym.
Twierdzenie
Równanie diofantyczne ax + by = c ma rozwiązanie wtedy i tylko
wtedy, gdy NWD(a, b)|c. Jeśli para x0, y0 jest pewnym
rozwiązaniem tego równania, to wszystkie rozwiązania dane są
wzorami:
b a
x = x0 + · t, y = y0 - · t, t " Z.
NWD(a, b) NWD(a, b)
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Równanie Diofantyczne
Przykład. Szukamy x, y " Z takich, że 44x + 390y = 6.
Stosujemy algorytm Euklidesa
390 = 8 · 44 + 38 Ò! 38 = 390 - 8 · 44
44 = 1 · 38 + 6 Ò! 6 = 44 - 1 · 38
38 = 6 · 6 + 2 Ò! 2 = 38 - 6 · 6
6 = 3 · 2 + 0
a zatem NWD(44, 390) = 2. Dalej
2 = 38 - 6 · 6 = 38 - 6 · (44 - 1 · 38) = 38 - 6 · 22 + 6 · 38 =
= 7 · 38 - 6 · 44 = 7 · (390 - 8 · 44) - 6 · 44 =
= 7 · 390 - 56 · 44 - 6 · 44 = 7 · 390 - 62 · 44.
StÄ…d 44 · x + 390 · y = 2 Ò! 44 · -62 3 +390 · 7 · 3 = 6.

·
y
x
390 44
x = -186 + t = -186 + 195t, y = 21 - t = 21 - 22t.
2 2
Przykład. Równanie 44x + 390y = 7 nie posiada rozwiązań ponieważ
NWD(44, 390) = 2 |7.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Liczby pierwsze
Definicja
Liczbę naturalną p nazywamy liczbą pierwszą, jeżeli posiada ona
dokładnie dwa różne dzielniki.
Przykład. Lista liczb pierwszych mniejszych od 100
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97.
Definicja
Liczbę naturalną a nazywamy liczbą złożoną, jeżeli posiada ona
przynajmniej jeden dzielnik b różny od 1 oraz a.
Definicja
Liczby naturalne a i b nazywamy względnie pierwszymi, jeżeli
NWD(a, b) = 1.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Liczby pierwsze
Przykład. Liczby 3 i 10 są względnie pierwsze.
Liczby 14 oraz 49 nie są względnie pierwsze.
Lemat (Euklidesa)
Jeśli n|ab oraz NWD(a, n) = 1, to n|b.
Dowód. Ponieważ NWD(a, n) = 1 to istnieją x, y " Z takie, że
xa + yn = 1. Mnożymy obie strony równości razy b
bax + byn = b.
Z założenia wiemy, że n|ab a zatem istnieje k " Z takie, że
kn = ab.
knx + bny = b Ò! n(kx + by) = b Ò! n|b.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Zasadnicze Twierdzenie Arytmetyki
Obserwacja
Każdą liczbę naturalną n > 1 można przedstawić w postaci
iloczynu liczb pierwszych.
Przykład. Niech n = 236
236 2
118 2
59 59
1
stÄ…d n = 22 · 59.
Twierdzenie (Zasadnicze Twierdzenie Arytmetyki)
Każda liczba naturalna n > 1 ma jednoznaczny (z dokładnością do
kolejności liczb w iloczynie) rozkład na iloczyn liczb pierwszych.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Zasadnicze Twierdzenie Arytmetyki
Dowód. Niech n > 1 będzie najmniejszą liczbą naturalną
posiadającą dwa różne rozkłady na liczby pierwsze:
p1 . . . pk = n = q1 . . . qm, gdzie p1 . . . pk oraz q1 . . . qm.
Żadna z liczb pi nie może pojawić wśród q1, . . . , qm (i na odwrót),
gdyż wydzielając obie strony przez pi, otrzymalibyśmy mniejszą
liczbę z dwoma różnymi rozkładami.
Liczba pierwsza p1 dzieli pierwszy iloczyn, a więc też dzieli i drugi:
p1|q1 . . . qm.
Zauważmy, że
NWD(p1, q1) = 1,
gdyż są to dwie, różne liczby pierwsze.
Na mocy Lematu Euklidesa otrzymujemy, iż p1|q2 . . . qm. Kolejno
możemy wyeliminować pozostałe liczby qi z prawego iloczynu
dochodząc do p1|1, sprzeczność.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Problem Faktoryzacji
Problem Faktoryzacji
Obecnie nie jest znany żaden efektywny algorytm faktoryzujący
liczby naturalne, tzn. znajdujący rozkład na iloczyn liczb
pierwszych. Oczekiwana trudność tego problemu jest sercem wielu
współczesnych systemów kryptograficznych (np. RSA). Nie
wszystkie liczby są równie trudne w rozkładzie. Póki co, (w połowie
2006 roku) najtrudniejsze wydają się liczby, które są iloczynami
dwu liczb pierwszych podobnej długości.
Obserwacja
Ä…k
Ä…1 Ä…2
Jeśli n = p1 p2 . . . pk jest rozkładem liczby n na iloczyn liczb
²1 ²k
pierwszych, to każdy jej dzielnik d|n jest postaci d = p1 . . . pk ,
dla pewnych 0 ²i Ä…i.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Problem Faktoryzacji
Dowód. Załóżmy niewprost, że w rozkładzie liczby d występuje liczba
Ä…1 Ä…2 Ä…k
pierwsza p, która nie występuje w rozkładzie n = p1 p2 . . . pk .
Oczywiście p|n, bo d|n. Ponieważ p i p1 są dwiema różnymi liczbami
Ä…2 Ä…k
pierwszymi, to na mocy Lematu Euklidesa otrzymujemy p|p2 . . . pk .
W podobny sposób możemy wyeliminować kolejno liczby p2, . . . , pk
dochodząc do sprzeczności, że p|1.
A więc rozkład liczby d zawiera wyłącznie liczby pierwsze z rozkładu
²1 ²k
liczby n, czyli d = p1 . . . pk , przy czym wszystkie ²i sÄ… nieujemne, ale
niektóre mogą być zerowe.
Pozostaje pokazać, że ²i Ä…i. Załóżmy, że ²i > Ä…i dla pewnego i.
Wtedy
d n
dzieli ,
Ä…i
Ä…i
pi pi
d n
przy czym liczba ąi ma w swoim rozkładzie czynnik pi , a liczba ąi nie
pi pi
ma.
To prowadzi do sprzeczności z tym, że wszystkie czynniki rozkładu
każdego dzielnika liczby naturalnej występują w rozkładzie tego dzielnika.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Problem Faktoryzacji
Wniosek
Ä…k
Ä…1 Ä…2
Jeśli n = p1 p2 . . . pk jest rozkładem liczby n na iloczyn liczb
pierwszych, to liczba n ma dokładnie
(Ä…1 + 1) · (Ä…2 + 1) · . . . · (Ä…k + 1) dodatnich dzielników.
Wniosek
Dla a, b, c " N jeśli a|c, b|c i NWD(a, b) = 1, to ab|c.
Obserwacja
Ä…k ²1 ² ²k
Ä…1 Ä…2
Jeśli a, b > 0, a = p1 p2 . . . pk i b = p1 p22 . . . pk , gdzie
Ä…i, ²i 0, to
min(Ä…1
min(Ä…k
NWD(a, b) = p1 ,²1) · . . . · pk ,²k ).
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Najmniejsza wspólna wielokrotność
Definicja
Najmniejsza wspólna wielokrotność dwu liczb a, b > 0 (oznaczamy
NWW(a, b)) to najmniejsza liczba dodatnia w taka, że a|w i b|w.
Obserwacja
Ä…k ²1 ² ²k
Ä…1 Ä…2
Jeśli a, b > 0, a = p1 p2 . . . pk i b = p1 p22 . . . pk , gdzie
Ä…i, ²i 0, to
max(Ä…1
max(Ä…k
NWW(a, b) = p1 ,²1) · . . . · pk ,²k ).
Obserwacja
NWW(a, b) · NWD(a, b) = ab.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Ilość liczb pierwszych
Twierdzenie
Liczb pierwszych jest nieskończenie wiele.
Dowód. Załóżmy niewprost, że zbiór P wszystkich liczb pierwszych
jest skończony. To znaczy, że P = {p1, p2, . . . , pn}. Niech
p = p1p2 · · · pn + 1.
Zauważmy, że p1 |p, p2 |p, . . . , pn |p oraz p > p1, p > p2, . . . ,
p > pn, a zatem p jest liczbą pierwszą, sprzeczność p " P.
Twierdzenie (Dirichlet)
Dla dowolnych dwu dodatnich i względnie pierwszych liczb a, d
istnieje nieskończenie wiele liczb pierwszych postaci nd + a dla
n > 0.
Przykład. Istnieje nieskończenie wiele liczb pierwszych postaci
4n + 1. (5,17,29,37,41)
Istnieje nieskończenie wiele liczb pierwszych postaci 4n + 3.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Ilość liczb pierwszych
Twierdzenie (Czebyszew)
Dla dowolnego n > 1 istnieje liczba pierwsza p taka, że
n < p < 2n.
Symbolem Pn oznaczamy zbiór wszystkich liczb pierwszych
mniejszy lub równych n. Symbolem Ą(n) oznaczamy ilość
elementów zbioru Pn.
Twierdzenie
Ä„(n) <" n/ ln n.
Ä„(n) = O(n/ ln n).
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Algorytm
1
Wczytaj n. Wypisz listÄ™ wszystkich liczb naturalnych od 2 do
n. Na początku wszystkie liczby są nieskreślone.
2
Dopóki istnieje nieskreślona jeszcze liczba na naszej liście
"
niewiększa od n powtarzaj: Wez
pierwszą nieskreśloną liczbę
p z listy i dodaj do zbioru znalezionych liczb pierwszych.
Póz
niej skreśl liczbę p z listy i skreśl wszystkie wielokrotności
liczby p, które są jeszcze na liście.
3
Wszystkie pozostałe, nieskreślone liczby z listy dodaj do zbioru
znalezionych liczb pierwszych.
Wystarczy wykreślać wielokrotności liczb pierwszych, niewiększych
"
od n, gdyż jeśli dowolna liczba m n ma nietrywialny dzielnik
(różny od 1 i niej samej), to m ma nietrywialny dzielnik pierwszy,
"
niewiększy od n.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
51 53 55 57 59
61 63 65 67 69
71 73 75 77 79
81 83 85 87 89
91 93 95 97 99
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
51 53 55 57 59
61 63 65 67 69
71 73 75 77 79
81 83 85 87 89
91 93 95 97 99
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7
11 13 17 19
23 25 29
31 35 37 39
41 43 47 49
53 55 59
61 65 67
71 73 77 79
83 85 89
91 95 97
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7
11 13 17 19
23 25 29
31 35 37 39
41 43 47 49
53 55 59
61 65 67
71 73 77 79
83 85 89
91 95 97
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7
11 13 17 19
23 29
31 37 39
41 43 47 49
53 59
61 67
71 73 77 79
83 89
91 97
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7
11 13 17 19
23 29
31 37 39
41 43 47 49
53 59
61 67
71 73 77 79
83 89
91 97
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Sito Eratostenesa
Przykład. Wyznaczamy wszystkie liczby pierwsze mniejsze lub
"
równe od 100. Oczywiście 100 = 10.
2 3 5 7
11 13 17 19
23 29
31 37 39
41 43 47
53 59
61 67
71 73 79
83 89
91 97
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Duże liczby pierwsze
Liczba pierwsza Liczba cyfr Odkrywcy Rok odkrycia
1 230 402 457 - 1 9 152 052 Boone, Cooper, GIMPS 2005
2 225 964 951 - 1 7 816 230 Nowak, GIMPS 2005
3 224 036 583 - 1 7 235 733 Findley, GIMPS 2004
4 220 996 011 - 1 6 320 430 Shafer, GIMPS 2003
5 213 466 917 - 1 4 053 946 Cameron, Kurowski, GIMPS 2001
6 27653 · 29 167 433 - 1 2 759 677 Gordon 2005
7 28433 · 27 830 457 - 1 2 357 207 TeamPrimeRib 2004
8 26 972 593 - 1 2 089 960 Hajratwala, Kurowski, GIMPS 1999
9 5359 · 25 054 502 - 1 1 521 561 Sundquist 2003
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Arytmetyka modularna
Definicja
Mówimy, że dwie liczby a, b " Z przystają do siebie modulo
n " N \ {0} wtedy i tylko wtedy, gdy istnieje k " Z taka, że
a - b = kn.
Fakt przystawania liczb modulo n będziemy oznaczać zamiennie
a a" b (mod n) albo a a"n b.
Przykład.
73 a"10 23, 73 a"10 -7, 73 a"10 3.
Obserwacja
Dla dowolnych a, b, c oraz n > 0 zachodzi:
a a"n a, (zwrotność)
a a"n b wtedy i tylko wtedy, gdy b a"n a, (symetria)
jeśli a a"n b i b a"n c to a a"n c. (przechodniość)
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Arytmetyka modularna
Obserwacja
Dla dowolnych a, b, c, d oraz n > 0 mamy:
jeśli a a"n b i c a"n d, to a + c a"n b + d,
jeśli a a"n b i c a"n d, to a - c a"n b - d,
jeśli a a"n b i c a"n d, to ac a"n bd.
Z powyższych obserwacji wynika, że relacja a"n jest relacją równoważności
w zbiorze Z. Stąd wynika, że dzieli ona zbiór Z na klasy abstrakcji.
Symbolem Zn = {[a]a" | a " Z} oznaczamy zbiór wszystkich klas
n
abstrakcji wyznaczonych przez relacjÄ™ a"n.
Ponieważ [0]a" = {0 + kn| k " Z}
n
[1]a" = {1 + kn| k " Z}
n
.
.
.
[n - 1]a" = {n - 1 + kn| k " Z}.
n
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Arytmetyka modularna
W zbiorze Zn definiujemy działania:
[a]a"n + [b]a"n = [a + b]a"n
[a]a"n - [b]a"n = [a - b]a"n
[a]a"n · [b]a"n = [a · b]a"n
Ponieważ reprezentantami klas abstrakcji są liczby 0, 1, . . . , n - 1,
będziemy pomijać nawiasy kwadratowe pamiętając, że liczby
0, 1, . . . , n - 1 oznaczajÄ… kolejne klasy abstrakcji
[0]a"n, [1]a"n, . . . , [n - 1]a"n.
Obserwacja (Reguła skracania)
Dla n > 0, jeśli ad a"n bd i NWD(d, n) = 1, to a a"n b.
Dowód. Ponieważ NWD(d, n) = 1, rozszerzony algorytm Euklidesa
gwarantuje istnienie x, y " Z takich, że xd + yn = 1, czyli dx a"n 1.
Mnożąc teraz obie strony ad a"n bd przez x, otrzymujemy
adx a"n bdx, czyli a = a1 a"n adx a"n bdx a"n b1 = b.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozwiązywanie równań modularnych
PrzykÅ‚ad. 3 · 5 = 15 a"7 50 = 10 · 5 oraz NWD(3, 7) = 1, to
3 a"7 10.
Obserwacja
Dla a, b " Z, a = 0 rozwiązania równania modularnego z jedną

niewiadomÄ… x:
ax a"n b,
zależą od wielkości NWD(a, n) = 1 w następujący sposób:
jeśli NWD(a, n) = 1, to istnieje nieskończenie wiele rozwiązań;
wszystkie one sÄ… postaci x = x0 + kn, gdzie 0 x0 < n jest jakimÅ›
rozwiÄ…zaniem, a k " Z,
jeśli NWD(a, n) = d > 1, to równanie ma rozwiązanie wtedy i tylko
wtedy, gdy również d|b. W tym przypadku rozwiązania równania
a b
n
ax a"n b pokrywają się z rozwiązaniami równania x a" .
d d
d
Ponadto, jeśli 0 a, b < n, to rozwiązanie 0 x0 < n równania ax a"n b,
lub jego brak, można wskazać wykonując O(lg3n) operacji bitowych.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozwiązywanie równań modularnych
Wniosek
Jeśli p jest liczbą pierwszą, to równania postaci ax a"p b dla
dowolnych 0 < a < p i 0 b < p zawsze majÄ… rozwiÄ…zanie i
można je znalez
ć wykonując O(lg3p) operacji bitowych.
Przykład. Rozwiązujemy równanie 3x a"7 4. Równanie to możemy
zapisać w postaci
3x + 7y = 4.
Znajdujemy NWD(3, 7)
7 = 2 · 3 + 1 Ò! 3 · (-2) + 7 · 1 = 1 Ò! 3 · (-8) + 7 · 4 = 4
StÄ…d x0 = -8, a zatem x = -8 + 7k, k " Z.
Rozwiązujemy równanie 4x a"16 8. Równanie to zapisujemy w postaci
4x + 16y = 8 Ò! x + 4y = 2.
Zauważmy, że x0 = -2 spełnia równanie a zatem x = -2 + 4k, k " Z.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.
Rozwiązywanie równań modularnych
Obserwacja
Niech a, b, m, n " Z, gdzie m, n > 0 i NWD(m, n) = 1. Wtedy
a a"mn b jest równoważne temu, że równocześnie a a"m b i a a"n b.
Dowód. Jeśli a a"mn b, to mn|a - b.
A więc oczywiście m|a - b i n|a - b, z ceo wynika a a"m b i a a"n b.
Dla dowodu implikacji odwrotnej, że jest ona trywialna dla a = b i
wobec tego przyjmijmy (bez straty ogólności), że a > b. Załóżmy
też, że m|a - b i n|a - b.
Ponieważ NWD(m, n) = 1, to rozkłady liczb m i n nie mają
wspólnych czynników pierwszych.
Natomiast rozkład a - b musi zawierać wszystkie liczby pierwsze z
rozkładów m i n w odpowiednio wysokich potęgach. To dowodzi, iż
mn|a - b, czyli a a"mn b.
Matematyka dyskretna, wykład 9 Teoria liczb cz.1.