Matematyka dyskretna, wykład 9
Teoria liczb cz.1.
Gliwice, 23.04.2009
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.
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).
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
|{z}
∈Z
⇒ a|bc.
2. Jeżeli a|b i b|c wtedy istnieją q
1
, g
2
∈ Z takie, że
b = aq
1
∧ c = bq
2
⇒ c = a q
1
q
2
|{z}
∈Z
⇒ a|c.
3. Jeżeli a|b i a|c wtedy istnieją q
1
, g
2
∈ Z takie, że
b = aq
1
∧ c = aq
2
⇒ b + c = aq
1
+ aq
2
= a (q
1
+ q
2
)
|
{z
}
∈Z
⇒ a|(b + c).
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
|{z}
∈Z
⇒ a|bc.
2. Jeżeli a|b i b|c wtedy istnieją q
1
, g
2
∈ Z takie, że
b = aq
1
∧ c = bq
2
⇒ c = a q
1
q
2
|{z}
∈Z
⇒ a|c.
3. Jeżeli a|b i a|c wtedy istnieją q
1
, g
2
∈ Z takie, że
b = aq
1
∧ c = aq
2
⇒ b + c = aq
1
+ aq
2
= a (q
1
+ q
2
)
|
{z
}
⇒ a|(b + c).
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 6 NWD(a, b) 6 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.
Największy wspólny dzielnik - Algorytm Euklidesa
Algorytm Euklidesa
Wykonujemy następującą procedurę
b
= q
1
a + r
1
,
0 < r
1
< b
a
= q
2
r
1
+ r
2
,
0 < r
2
< r
1
r
1
= q
3
r
2
+ r
3
,
0 < r
3
< r
2
. . .
. . . . . . . . . . . . . . . . . . . . . . . .
r
n−2
= q
n
r
n−1
+ r
n
0 < r
n
< r
n−1
r
n−1
= q
n+1
r
n
+ 0
Procedura musi się zakończyć ponieważ r
1
> r
2
> . . . > r
n
> 0.
Wtedy r
n
= NWD(a, b).
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, r
1
) = NWD(r
1
, r
2
) = · · · = NWD(r
n−1
, r
n
) = NWD(r
n
, 0) = r
n
.
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.
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 przejdź 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
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.
Rozszerzony Algorytm Euklidesa
Rozszerzenie Algorytmu Euklidesa
Załóżmy, że a > b. Niech r
0
= a, r
1
= b, natomiast r
2
. . . , r
n
, r
n+1
będą
kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym
r
n+1
= 0. Wtedy wiemy, że r
n
= NWD(a, b) oraz
r
n−1
= q
n−1
· r
n
,
r
n−2
= q
n−2
· r
n−1
+ r
n
,
r
n−3
= q
n−3
· r
n−2
+ r
n−1
,
..
.
r
1
= q
1
· r
2
+ r
3
,
r
0
= q
0
· r
1
+ r
2
,
dla pewnych q
0
, q
1
, . . . , q
n−1
. Mamy zatem
r
n−2
− q
n−2
· r
n−1
= NWD(a, b). Załóżmy indukcyjnie, dla 0 < i ¬ n − 2,
że istnieją x , y ∈ Z takie, że r
i
· x + r
i +1
· y = NWD(a, b). Ponieważ
r
i +1
= r
i −1
+ q
i −1
· r
i
otrzymujemy:
NWD(a, b)
= r
i
· x + r
i +1
· y
= r
i
· x + (r
i −1
+ q
i −1
· r
i
) · y
= r
i −1
· y + r
i
· (x + q
i −1
· y ).
Rozszerzony Algorytm Euklidesa
A więc możemy zejść z liczbą i do i = 0, co daje pożądane
przedstawienie NWD(a, b) jako r
0
· x + r
1
· 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
| {z }
x
+390 · 7
|{z}
y
= 2.
Rozszerzony Algorytm Euklidesa
A więc możemy zejść z liczbą i do i = 0, co daje pożądane
przedstawienie NWD(a, b) jako r
0
· x + r
1
· 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
| {z }
x
+390 · 7
|{z}
y
= 2.
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 x
0
, y
0
jest pewnym
rozwiązaniem tego równania, to wszystkie rozwiązania dane są
wzorami:
x = x
0
+
b
NWD(a, b)
· t,
y = y
0
−
a
NWD(a, b)
· t,
t ∈ Z.
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
|
{z
}
x
+390 · 7 · 3
|{z}
y
= 6.
x = −186 +
390
2
t = −186 + 195t,
y = 21 −
44
2
t = 21 − 22t.
Przykład. Równanie 44x + 390y = 7 nie posiada rozwiązań ponieważ
NWD(44, 390) = 2 6 |7.
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
.
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.
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 = 2
2
· 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.
Zasadnicze Twierdzenie Arytmetyki
Dowód. Niech n > 1 będzie najmniejszą liczbą naturalną
posiadającą dwa różne rozkłady na liczby pierwsze:
p
1
. . . p
k
= n = q
1
. . . q
m
, gdzie p
1
6 . . . ¬ p
k
oraz q
1
6 . . . ¬ q
m
.
Żadna z liczb p
i
nie może pojawić wśród q
1
, . . . , q
m
(i na odwrót),
gdyż wydzielając obie strony przez p
i
, otrzymalibyśmy mniejszą
liczbę z dwoma różnymi rozkładami.
Liczba pierwsza p
1
dzieli pierwszy iloczyn, a więc też dzieli i drugi:
p
1
|q
1
. . . q
m
.
Zauważmy, że
NWD(p
1
, q
1
) = 1,
gdyż są to dwie, różne liczby pierwsze.
Na mocy Lematu Euklidesa otrzymujemy, iż p
1
|q
2
. . . q
m
. Kolejno
możemy wyeliminować pozostałe liczby q
i
z prawego iloczynu
dochodząc do p
1
|1, sprzeczność.
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
Jeśli n = p
α
1
1
p
α
2
2
. . . p
α
k
k
jest rozkładem liczby n na iloczyn liczb
pierwszych, to każdy jej dzielnik d |n jest postaci d = p
β
1
1
. . . p
β
k
k
,
dla pewnych 0 6 β
i
6 α
i
.
Problem Faktoryzacji
Dowód. Załóżmy niewprost, że w rozkładzie liczby d występuje liczba
pierwsza p, która nie występuje w rozkładzie n = p
α
1
1
p
α
2
2
. . . p
α
k
k
.
Oczywiście p|n, bo d |n. Ponieważ p i p
1
są dwiema różnymi liczbami
pierwszymi, to na mocy Lematu Euklidesa otrzymujemy p|p
α
2
2
. . . p
α
k
k
.
W podobny sposób możemy wyeliminować kolejno liczby p
2
, . . . , p
k
dochodząc do sprzeczności, że p|1.
A więc rozkład liczby d zawiera wyłącznie liczby pierwsze z rozkładu
liczby n, czyli d = p
β
1
1
. . . p
β
k
k
, przy czym wszystkie β
i
są nieujemne, ale
niektóre mogą być zerowe.
Pozostaje pokazać, że β
i
6 α
i
. Załóżmy, że β
i
> α
i
dla pewnego i .
Wtedy
d
p
α
i
i
dzieli
n
p
α
i
i
,
przy czym liczba
d
p
αi
i
ma w swoim rozkładzie czynnik p
i
, a liczba
n
p
αi
i
nie
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.
Problem Faktoryzacji
Wniosek
Jeśli n = p
α
1
1
p
α
2
2
. . . p
α
k
k
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
Jeśli a, b > 0, a = p
α
1
1
p
α
2
2
. . . p
α
k
k
i b = p
β
1
1
p
β
2
2
. . . p
β
k
k
, gdzie
α
i
, β
i
0, to
NWD(a, b) = p
min(α
1
,β
1
)
1
· . . . · p
min(α
k
,β
k
)
k
.
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
Jeśli a, b > 0, a = p
α
1
1
p
α
2
2
. . . p
α
k
k
i b = p
β
1
1
p
β
2
2
. . . p
β
k
k
, gdzie
α
i
, β
i
0, to
NWW(a, b) = p
max(α
1
,β
1
)
1
· . . . · p
max(α
k
,β
k
)
k
.
Obserwacja
NWW(a, b) · NWD(a, b) = ab.
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 = {p
1
, p
2
, . . . , p
n
}. Niech
p = p
1
p
2
· · · p
n
+ 1.
Zauważmy, że p
1
6 |p, p
2
6 |p, . . . , p
n
6 |p oraz p > p
1
, p > p
2
, . . . ,
p > p
n
, a zatem p jest liczbą pierwszą, sprzeczność p 6∈ 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.
Ilość liczb pierwszych
Twierdzenie (Czebyszew)
Dla dowolnego n > 1 istnieje liczba pierwsza p taka, że
n < p < 2n.
Symbolem P
n
oznaczamy zbiór wszystkich liczb pierwszych
mniejszy lub równych n. Symbolem π(n) oznaczamy ilość
elementów zbioru P
n
.
Twierdzenie
π(n) ∼ n/ ln n.
π(n) = O(n/ ln n).
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: Weź pierwszą nieskreśloną liczbę
p z listy i dodaj do zbioru znalezionych liczb pierwszych.
Póź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.
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
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
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
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
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
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
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
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
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
Duże liczby pierwsze
Liczba pierwsza
Liczba cyfr
Odkrywcy
Rok odkrycia
1
2
30 402 457
− 1
9 152 052
Boone, Cooper , GIMPS
2005
2
2
25 964 951
− 1
7 816 230
Nowak, GIMPS
2005
3
2
24 036 583
− 1
7 235 733
Findley , GIMPS
2004
4
2
20 996 011
− 1
6 320 430
Shafer , GIMPS
2003
5
2
13 466 917
− 1
4 053 946
Cameron, Kurowski , GIMPS
2001
6
27653 · 2
9 167 433
− 1
2 759 677
Gordon
2005
7
28433 · 2
7 830 457
− 1
2 357 207
TeamPrimeRib
2004
8
2
6 972 593
− 1
2 089 960
Hajratwala, Kurowski , GIMPS
1999
9
5359 · 2
5 054 502
− 1
1 521 561
Sundquist
2003
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 ≡ b (mod n)
albo
a ≡
n
b
.
Przykład.
73 ≡
10
23,
73 ≡
10
−7,
73 ≡
10
3.
Obserwacja
Dla dowolnych a, b, c oraz n > 0 zachodzi:
a ≡
n
a, (zwrotność)
a ≡
n
b wtedy i tylko wtedy, gdy b ≡
n
a, (symetria)
jeśli a ≡
n
b i b ≡
n
c to a ≡
n
c. (przechodniość)
Arytmetyka modularna
Obserwacja
Dla dowolnych a, b, c, d oraz n > 0 mamy:
jeśli a ≡
n
b i c ≡
n
d , to a + c ≡
n
b + d ,
jeśli a ≡
n
b i c ≡
n
d , to a − c ≡
n
b − d ,
jeśli a ≡
n
b i c ≡
n
d , to ac ≡
n
bd .
Z powyższych obserwacji wynika, że relacja ≡
n
jest relacją równoważności
w zbiorze Z. Stąd wynika, że dzieli ona zbiór Z na klasy abstrakcji.
Symbolem Z
n
= {[a]
≡
n
| a ∈ Z} oznaczamy zbiór wszystkich klas
abstrakcji wyznaczonych przez relację ≡
n
.
Ponieważ
[0]
≡
n
= {0 + kn| k ∈ Z}
[1]
≡
n
= {1 + kn| k ∈ Z}
..
.
[n − 1]
≡
n
= {n − 1 + kn| k ∈ Z}.
Arytmetyka modularna
W zbiorze Z
n
definiujemy działania:
[a]
≡
n
+ [b]
≡
n
= [a + b]
≡
n
[a]
≡
n
− [b]
≡
n
= [a − b]
≡
n
[a]
≡
n
· [b]
≡
n
= [a · b]
≡
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]
≡
n
, [1]
≡
n
, . . . , [n − 1]
≡
n
.
Obserwacja (Reguła skracania)
Dla n > 0, jeśli ad ≡
n
bd i NWD(d , n) = 1, to 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 ≡
n
1.
Mnożąc teraz obie strony ad ≡
n
bd przez x , otrzymujemy
adx ≡
n
bdx , czyli a = a1 ≡
n
adx ≡
n
bdx ≡
Rozwiązywanie równań modularnych
Przykład. 3 · 5 = 15 ≡
7
50 = 10 · 5 oraz NWD(3, 7) = 1, to
3 ≡
7
10.
Obserwacja
Dla a, b ∈ Z, a 6= 0 rozwiązania równania modularnego z jedną
niewiadomą x :
ax ≡
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 = x
0
+ kn, gdzie 0 6 x
0
< 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
ax ≡
n
b pokrywają się z rozwiązaniami równania
a
d
x ≡
n
d
b
d
.
Ponadto, jeśli 0 6 a, b < n, to rozwiązanie 0 6 x
0
< n równania ax ≡
n
b,
lub jego brak, można wskazać wykonując O(lg
3
n) operacji bitowych.
Rozwiązywanie równań modularnych
Wniosek
Jeśli p jest liczbą pierwszą, to równania postaci ax ≡
p
b dla
dowolnych 0 < a < p i 0 6 b < p zawsze mają rozwiązanie i
można je znaleźć wykonując O(lg
3
p) operacji bitowych.
Przykład. Rozwiązujemy równanie 3x ≡
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 x
0
= −8, a zatem x = −8 + 7k, k ∈ Z.
Rozwiązujemy równanie 4x ≡
16
8. Równanie to zapisujemy w postaci
4x + 16y = 8 ⇒ x + 4y = 2.
Zauważmy, że x
0
Rozwiązywanie równań modularnych
Obserwacja
Niech a, b, m, n ∈ Z, gdzie m, n > 0 i NWD(m, n) = 1. Wtedy
a ≡
mn
b jest równoważne temu, że równocześnie a ≡
m
b i a ≡
n
b.
Dowód. Jeśli a ≡
mn
b, to mn|a − b.
A więc oczywiście m|a − b i n|a − b, z ceo wynika a ≡
m
b i 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 ≡
mn
b.
Wyszukiwarka
Podobne podstrony:
Matematyka dyskretna 2004 06 Teoria liczb
Matematyka dyskretna 2004 06 Teoria liczb
Matematyka dyskretna 2002 06 Teoria liczb
Teoria 3, Studia, II sem, Dyskretna - cz. I
Teoria 1, Studia, II sem, Dyskretna - cz. I
Teoria 4, Studia, II sem, Dyskretna - cz. I
Teoria 2, Studia, II sem, Dyskretna - cz. I
matematyka dyskretna w 2 id 283 Nieznany
Denisjuk A Matematyka Dyskretna
wykład 2 cz.1, Teoria i analiza rynku- semestr V
Zadania 2, Studia, II sem, Dyskretna - cz. I
C2, Matematyka studia, Matematyka dyskretna
Matematyka Dyskretna Test#1
Matematyka dyskretna Zadania(1)
algebra z teoria liczb wyk
Matematyka dyskretna id 283281 Nieznany
więcej podobnych podstron