B.Bajorska, O.Macedońska
Wykład 4. NWW i Algorytm Euklidesa
Wprowadzimy najpierw pojęcie w pewnym sensie dualne do pojęcia N W D.
Definicja 1. Niech a, b będą niezerowymi liczbami całkowitymi. Liczbę naturalną m nazy-
wamy najmniejszą wspólną wielokrotnością liczb a i b i oznaczamy N W 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 N W W (2 , 5) = 10 , N W W (2 , 4) = 4 , N W W ( − 6 , 10) = 30.
Twierdzenie 1. Jeśli a i b są liczbami naturalnymi, to
N W D( a, b) N W W ( a, b) = ab.
Dowód. Niech d = N W D( a, b). Ponieważ a, b, d są naturalne, to z definicji N W D mamy w szczególności, że istnieją liczby naturalne r, s takie, że a = dr, b = ds. Pokażemy, że liczba
ab
m :=
(1)
d
jest równa N W W ( a, b). Ponieważ m = ads = as oraz m = drb = 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, weźmy naturalne c takie że a|c, b|c. Wtedy istnieją liczby naturalne q, t takie, że c = aq = bt.
(2)
Z własności N W D (Wykład 3, Tw.1) wiemy też, że istnieją liczby całkowite u, v takie, że d = au + bv. Wtedy liczba c jest całkowita, ponieważ korzystając z (1), mamy m
c
(1)
cd
c( au + bv) (2) 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, co dowodzi, że m = ab = N W W ( a, b), skąd ostatecznie N W D( a, b) N W W ( a, b) = ab.
d
Z powyższego Twierdzenia otrzymujemy natychmiast
Wniosek 1. Jeśli a i b są liczbami naturalnymi, to N W W ( a, b) = ab wtedy i tylko wtedy gdy N W D( a, b) = 1 .
2
W dalszej części opiszemy procedurę zwaną Algorytmem Euklidesa. Jest to jeden
z najstarszych i najbardziej znanych algorytmów w teorii liczb.
1
1. Algorytm Euklidesa służy do znajdowania N W D( a, b). Można go również wyko-rzystać do znalezienia przedstawienia N W D( a, b) w postaci kombinacji liniowej a, b czyli do znalezienia takich całkowitych u, v, że N W D( a, b) = au + bv 2. Opis Algorytmu Euklidesa: Niech a, b ∈ Z \ { 0 }, a > b.
(a) Wykonujemy dzielenie z resztą a przez b : ∃r 1 , q 1 a = bq 1 + r 1.
(b) Jeśli r 1 = 0 to N W D( a, b) = b. Jeśli nie, to powtarzamy punkt (a) dla pary b, r 1 i wtedy ∃r 2 , q 2 b = r 1 q 2 + r 2.
(c) Procedura kończy się, gdy dla pewnego n ∈ N rn ̸= 0 ∧ rn+1 = 0 i wtedy N W D( a, b) = rn.
Zapis algorytmu wygląda następująco:
a = b q 1 + r 1
0 < r 1 < b
b = r 1 q 2 + r 2
0 < r 2 < r 1
r 1 = r 2 q 3 + r 3
0 < r 3 < r 2
.
.
.
.
.
..
rn− 2 = rn− 1 qn + rn
0 < rn < rn− 1
rn− 1 = rnqn+1 + 0
rn+1 = 0
= ⇒ rn = NW D( a, b)
3. Poprawność procedury: Aby ją wykazać, udowodnimy najpierw następujący
Lemat 1. Jeśli a = bq + r to N W D( a, b) = N W D( b, r) .
Dowód. Załóżmy, że spełniona jest równość a = bq+ r i oznaczmy d := N W D( a, b) , t := N W D( b, r). Pokażemy dwie nierówności.
( d ≤ t)
Ponieważ d|a, d|b, to z Własności 8 (Wykład 2, Tw.1) mamy d|a − bq czyli
d|r. Zatem d jest wspólnym dzielnikiem b i r, a więc z definicji NW D mamy d ≤ t.
( t ≤ d)
Ponieważ t|b, t|r, to z Własności 8 (Wykład 2, Tw.1) mamy t|bq+ r czyli t|a. Zatem t jest wspólnym dzielnikiem a i b, więc z definicji NW D mamy t ≤ d.
Jako efekt pośredni zastosowania Algorytmu Euklidesa otrzymujemy malejący ciąg
liczb naturalnych r 1 > r 2 > ... (jedną na każdym kroku), zatem zawsze musi to być ciąg skończony (co najwyżej r 1 elementów), co oznacza że algorytm zawsze się
kończy. Ponadto, przy oznaczeniach jak wyżej z Lematu 1 otrzymujemy
N W D( a, b) = N W D( b, r 1) = N W D( r 1 , r 2) = ... = N W D( rn, rn+1) =
= N W D( rn, 0) = rn.
4. Modyfikacja:
(a) Wykonujemy dzielenie z resztą a przez b ⇒ ∃r 1 , q 1 a = bq 1 + r 1. Jeśli r 1 > |b|
2
to zapisujemy a = b( q 1 + 1) − ( b − r 1). Zatem zawsze da się przedstawić liczbę a w postaci bq ± r
.
1
1, gdzie 0 ≤ r 1 ≤ |b|
2
2
(b) Jeśli r 1 = 0 to N W D( a, b) = a. Jeśli nie, to powtarzamy punkt (a) dla liczb b, r 1 otrzymując b = r 1 q ± r
, r
.
2
2, gdzie q 2
2 ∈ Z oraz 0 ≤ r 2 ≤ r 1
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 poprawność
oryginalnego Algorytmu Euklidesa.
Przykład: (137 , 20) = 1, bo
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 N W D( a, b) = au + bv: Efektem pośrednim zastosowania Algorytmu Euklidesa jest ciąg równości.
1) Z przedostatniej równości wyznaczamy N W D( a, b) = rn = rn− 2 − rn− 1 qn, zatem mamy przedstawienie N W 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 up-
roszczeniu otrzymujemy N W D( a, b) w postaci kombinacji rn− 2 i rn− 3.
3) Podstawienia kontynuujemy do momentu, w którym uzyskamy szukane przed-
stawienie N W D( a, b) za pomocą a i b.
Analogiczny schemat działa w przypadku algorytmu zmodyfikowanego.
Przykład: Znaleźć u, v takie, że N W D(137 , 20) = 137 u + 20 v.
Na podstawie zmodyfikowanego algorytmu otrzymujemy
N W 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 N W D( a, b) = 1, tzn. nie ma potrzeby wykonywania ostatniego dzielenia.
3