Wykład 4. NWW, Algorytm Euklidesa, Liczby pierwsze
1 NWW
Wprowadzimy najpierw pojęcie w pewnym sensie dualne do pojęcia NW D.
Definicja 1. Niech a, b będą niezerowymi liczbami całkowitymi. Liczbę naturalną m na-
zywamy najmniejszą wspólną wielokrotnością liczb a i b i oznaczamy NW W (a, b)
jeśli:
1. a|m oraz b|m (wspólna wielokrotność),
2. jeśli c " N jest taką liczbą, że a|c oraz b|c, to m c (najmniejsza).
Przykład NW W (2, 5) = 10, NW W (2, 4) = 4, NW W (-6, 10) = 30.
Twierdzenie 1. Jeśli a i b są liczbami naturalnymi, to
NW D(a, b)NW W (a, b) = ab.
Dowód. Niech d = NW D(a, b). Ponieważ a, b, d są naturalne, to z definicji NW D mamy
w szczególności, że istnieją liczby naturalne r, s takie, że a = dr, b = ds. Pokażemy, że
liczba
ab
m :=
d
ads drb
jest równa NW W (a, b). Ponieważ m = = as oraz m = = br, to m jest naturalna,
d d
a|m oraz b|m, czyli m spełnia pierwszy warunek definicji NW W . Aby sprawdzić warunek
drugi, wez
my naturalne c takie że a|c, b|c. Wtedy istnieją liczby naturalne q, t takie, że
c = aq = bt. Z własności NW D (Wykład 3, Tw.1) wiemy też, że istnieją liczby całkowite
c
u, v takie, że d = au + bv. Wtedy liczba jest całkowita, ponieważ
m
c cd c(au + bv) c c
= = = · u + · v = tu + qv " Z.
m ab ab b a
Z definicji podzielności oznacza to, że m|c, a więc z Własności 1 (Wykład 2, Tw.1) m c,
ab
co dowodzi, że m = = NW W (a, b), skąd ostatecznie NW D(a, b)NW W (a, b) = ab.
d
Z powyższego Twierdzenia otrzymujemy natychmiast
Wniosek 1. Jeśli a i b są liczbami naturalnymi, to NW W (a, b) = ab wtedy i tylko wtedy
gdy NW D(a, b) = 1.
2 Algorytm Euklidesa
W dalszej części opiszemy procedurę zwaną Algorytmem Euklidesa. Jest to jeden z naj-
starszych i najbardziej znanych algorytmów w teorii liczb.
1
1. Algorytm Euklidesa służy do znajdowania NW D(a, b). Można go również wy-
korzystać do znalezienia przedstawienia NW D(a, b) w postaci kombinacji liniowej
a, b czyli do znalezienia takich całkowitych u, v, że NW D(a, b) = au + bv
2. Opis Algorytmu Euklidesa: Niech a, b " Z \ {0}, a > b.
(a) Wykonujemy dzielenie z resztÄ… a przez b : "r1, q1 a = bq1 + r1.
(b) Jeśli r1 = 0 to NW D(a, b) = b. Jeśli nie, to powtarzamy punkt (a) dla pary
b, r1 i wtedy "r2, q2 b = r1q2 + r2.
(c) Procedura kończy się, gdy dla pewnego n " N rn = 0 '" rn+1 = 0 i wtedy

NW D(a, b) = rn.
Zapis algorytmu wygląda następująco:
a = b q1 + r1 0 < r1 < b
b = r1q2 + r2 0 < r2 < r1
r1 = r2q3 + r3 0 < r3 < r2
.
. .
. .
. .
rn-2 = rn-1qn + rn 0 < rn < rn-1
rn-1 = rnqn+1 + 0 rn+1 = 0 =Ò! rn = NW D(a, b)
3. Poprawność procedury: Przypomnijmy najpierw następujący fakt, który udo-
wodniliśmy wcześniej:
Lemat 1. Jeśli a = bq + r to NW D(a, b) = NW D(b, r).
Jako efekt pośredni zastosowania Algorytmu Euklidesa otrzymujemy malejący ciąg
liczb naturalnych r1 > r2 > ... (jedną na każdym kroku), zatem zawsze musi to
być ciąg skończony (co najwyżej r1 elementów), co oznacza że algorytm zawsze się
kończy. Ponadto, przy oznaczeniach jak wyżej z Lematu 1 otrzymujemy
NW D(a, b) = NW D(b, r1) = NW D(r1, r2) = ... = NW D(rn, rn+1) =
= NW D(rn, 0) = rn.
4. Modyfikacja:
|b|
(a) Wykonujemy dzielenie z resztÄ… a przez b Ò! "r1, q1 a = bq1 + r1. JeÅ›li r1 >
2
to zapisujemy a = b(q1 + 1) - (b - r1). Zatem zawsze da się przedstawić liczbę
|b|
a w postaci bq1 Ä… r1, gdzie 0 r1 d" .
2
(b) Jeśli r1 = 0 to NW D(a, b) = a. Jeśli nie, to powtarzamy punkt (a) dla liczb
r1
b, r1 otrzymujÄ…c b = r1 q2 Ä… r2, gdzie q2, r2 " Z oraz 0 r2 .
2
(c) Jeśli dla pewnego n " N rn = 0 '" rn+1 = 0, to NW D(a, b) = rn.

Poprawność algorytmu zmodyfikowanego wynika z tych samych faktów co popraw-
ność oryginalnego Algorytmu Euklidesa.
Przykład: (137, 20) = 1, bo
2
Algorytm standardowy: Algorytm zmodyfikowany:
17>20/2
137 = 20 · 6 + 17 137 = 20 · 6 + 17 =Ò! 137 = 20 · 7 - 3
2>3/2
20 = 17 · 1 + 3 20 = 3 · 6 + 2 =Ò! 20 = 3 · 7 - 1
17 = 3 · 5 + 2 3 = 1 · 3 + 0
3 = 2 · 1 + 1
2 = 1 · 2 + 0
5. Wyznaczanie liczb u, v takich, że NW D(a, b) = au + bv: Efektem pośrednim
zastosowania Algorytmu Euklidesa jest ciąg równości.
1) Z przedostatniej równości wyznaczamy NW D(a, b) = rn = rn-2 - rn-1qn, zatem
mamy przedstawienie NW D(a, b) za pomocÄ… kombinacji rn-1 i rn-2.
2) Za rn-1 podstawiamy liczbę otrzymaną z przed-przedostatniej równości. Po
uproszczeniu otrzymujemy NW D(a, b) w postaci kombinacji rn-2 i rn-3.
3) Podstawienia kontynuujemy do momentu, w którym uzyskamy szukane przedsta-
wienie NW D(a, b) za pomocÄ… a i b.
Analogiczny schemat działa w przypadku algorytmu zmodyfikowanego.
Przykład: Znalez
ć u, v takie, że NW D(137, 20) = 137u + 20v.
Na podstawie zmodyfikowanego algorytmu otrzymujemy
NW D(137, 20) = 1 = 7 · 3 - 20 = 7 · (7 · 20 - 137) - 20 = 48 · 20 - 7 · 137.
(Sprawdzenie: 48 · 20 - 7 · 137 = 960 - 959 = 1). Zatem u = -7, v = 48.
6. Uwagi:
1) Jako, że dla dowolnego całkowitego a = 0 mamy NW D(a, a) = NW D(0, a) = a,

to algorytm Euklidesa można ograniczyć do różnych niezerowych liczb całkowitych,
czyli bez straty ogólności możemy założyć, że rozpatrujemy a, b " Z \ {0}, a > b.
2) Jeśli, przy oznaczeniach jak wyżej, dla pewnego naturalnego n mamy rn = 1 (lub
rn = 1) to NW D(a, b) = 1, tzn. nie ma potrzeby wykonywania ostatniego dzielenia.
3 Podstawowe własności liczb pierwszych
Definicja 2. Liczbę naturalną n większą od 1 nazywamy liczbą pierwszą, jeśli ma ona
tylko dwa dzielniki naturalne 1 oraz n. Każdą liczbę naturalną n większą od 1, która nie
jest pierwsza, nazywamy liczbą złożoną. Zbiór liczb pierwszych oznaczamy przez P.
Przykład 2, 5, 7 " P, 4 " P, bo 2|4.
/
Wniosek 2. Liczba n jest złożona wtedy i tylko wtedy, gdy istnieją liczby całkowite a, b
takie, że
n = ab przy czym 1 < a b < n.
Lemat 2. Każda liczba naturalna większa od 1 ma dzielnik pierwszy.
Dowód. Jeśli n jest liczbą pierwszą, to sama jest swoim dzielnikiem pierwszym. Załóżmy
teraz, że n jest liczbą złożoną. Wtedy na podstawie definicji n ma dzielnik naturalny m
taki, że 1 < m < n. Niech teraz D oznacza zbiór wszystkich naturalnych dzielników liczby
n. Zbiór ten jest niepusty, ponieważ m " D. Wobec Zasady minimum (Wykład 2, Tw.1)
istnieje w D element najmniejszy, powiedzmy p. Pokażemy, że jest to szukany dzielnik
3
pierwszy liczby n. Z definicji zbioru D mamy p|n, a więc wystarczy pokazać, że p jest
liczbą pierwszą. Załóżmy nie wprost, że p " P. Ponieważ p jest liczbą naturalną większą
/
od 1, to p jest liczbą złożoną, więc z definicji istnieje dzielnik d liczby p. Ponieważ p|n,
to Z Własności 6 (Wykład 2, Tw.1) d jest również dzielnikiem liczby n, a zatem d " D,
co daje sprzeczność z minimalnością p. Zatem n ma dzielnik pierwszy.
"
Lemat 3. Każda liczba złożona n ma dzielnik pierwszy p taki, że p n.
Dowód. Na podstawie Wniosku 2 istnieją
"liczby naturalne a, b takie, że 1 < a b < n
"
oraz n = ab. Gdyby a było większe niż n, to także b > n i wtedy n = ab > n,
"
sprzeczność. Tak więc a n i na podstawie Lematu 2, a ma dzielnik pierwszy p.
"
Ponadto, z Własności 1 (Wykład 2, Tw.1) p a n, a z Własności 6 (Wykład 2,
Tw.1) p|n.
Uwaga 1 Z powyższego Lematu wynika elementarna metoda sprawdzania, czy dana liczba
n jest pierwsza: wystarczy sprawdzić, czy dzieli się przez którąkolwiek liczbę pierwszą nie
"
większą niż n.
Uwaga 2 Definicję liczby złożonej można rozszerzyć na liczby ujemne. Liczbą złożoną
nazywalibyśmy wówczas każdą liczbę całkowitą różną od -1, 0 oraz 1, która nie jest liczbą
pierwszÄ… ani liczbÄ… przeciwnÄ… do pewnej liczby pierwszej (inaczej: jest naturalnÄ… liczbÄ…
złożoną lub liczbą przeciwną do pewnej naturalnej liczby złożonej). Dla tak zmodyfiko-
wanej definicji Wniosek 2 oraz Lematy 2 i 3 po odpowiednim przeformułowaniu pozostają
prawdziwe.
4 Sito Eratostenesa
Eratostenes1 wymyślił elementarną metodę znajdowania wszystkich liczb pierwszych mniej-
szych od danej liczby naturalnej n, zwanÄ… sitem Eratostenesa. Procedura wyglÄ…da
następująco:
(1) Wypisujemy wszystkie liczby naturalne od 2 do n - 1.
(2) Najmniejszą nieskreśloną liczbą jest 2 i jest to liczba pierwsza. Wobec tego z ciągu
wykreślamy co drugą liczbę (liczenie rozpoczynamy od 3). W ten sposób wyeliminujemy
wszystkie liczby podzielne 2.
(3) Najmniejszą nieskreśloną liczbą jest teraz 3 i jest to kolejna liczba pierwsza. Wobec
tego z ciągu wykreślamy co trzecią liczbę (liczenie rozpoczynamy od 4). Niektóre liczby
zostaną wykreślone dwa razy (np 6). W ten sposób wyeliminujemy liczby podzielne przez
3. Oznacza to, ze wyeliminowaliśmy wszystkie liczby podzielne przez 2 lub 3.
(4) Powtarzamy proces dla kolejnych nieskreślonych liczb. Algorytm się kończy wtedy,
"
gdy najmniejsza nieskreślona liczba jest większa niż n - 1. Liczby, które pozostaną
nieskreślone to wszystkie możliwe liczby pierwsze mniejsze niż n, co wynika z metody
wykreślania oraz Lematu 3.
Uwaga Sito jest metodą pracochłonną, przez co nieefektywną, ale skuteczną dla małych
liczb. Szukaniem dużych liczb pierwszych w postaci Mersenne a zajmuje się od 1996 roku
zespół ochotników w ramach projektu GIMPS2 (Great Internet Mersenne Prime Search).
Największa znana obecnie liczba pierwsza to 243112609 - 1, ma prawie 13 milionów cyfr.
Została znaleziona przez zespół GIMPS w sierpniu 2008 roku i jest to najprawdopodobniej
czterdziesta siódma liczba pierwsza w postaci Mersenne a.
1
Eratostenes 276-194 p.n.e.
2
Strona www projektu: http://www.mersenne.org/
4