Teoria liczb 2010, sem.IV,

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

m :=

ab

d

(1)

jest równa N W W (a, b). Ponieważ m =

ads

d

= as oraz m =

drb

d

= br, to m jest naturalna,

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

m

jest całkowita, ponieważ korzystając z (1), mamy

c

m

(1)

=

cd

ab

=

c(au + bv)

ab

(2)

=

c

b

· u +

c

a

· v = tu + qv ∈ Z.

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

d

= N W W (a, b), skąd ostatecznie N W D(a, b)N W W (a, b) = ab.

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 r

n

̸= 0 ∧ r

n+1

= 0 i wtedy

N W D(a, b) = r

n

.

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

..

.

..

.

r

n

−2

= r

n

−1

q

n

+ r

n

0 < r

n

< r

n

−1

r

n

−1

= r

n

q

n+1

+ 0

r

n+1

= 0

=

⇒ r

n

= N W 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(r

n

, r

n+1

) =

= N W D(r

n

, 0) = r

n

.

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

1

± r

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

2

± r

2

, gdzie q

2

, r

2

∈ Z oraz 0 ≤ r

2

≤

r

1

2

.

(c) Jeśli dla pewnego n

∈ N r

n

̸= 0 ∧ r

n+1

= 0, to N W D(a, b) = r

n

.

Poprawność algorytmu zmodyfikowanego wynika z tych samych faktów co poprawność
oryginalnego Algorytmu Euklidesa.

Przykład: (137, 20) = 1, bo

Algorytm standardowy:

Algorytm zmodyfikowany:

137 = 20

· 6 + 17

137 = 20

· 6 + 17

17>20/2

=

⇒ 137 = 20 · 7 − 3

20 = 17

· 1 + 3

20 = 3

· 6 + 2

2>3/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) = r

n

= r

n

−2

− r

n

−1

q

n

, zatem

mamy przedstawienie N W D(a, b) za pomocą kombinacji r

n

−1

i r

n

−2

.

2) Za r

n

−1

podstawiamy liczbę otrzymaną z przed-przedostatniej równości. Po up-

roszczeniu otrzymujemy N W D(a, b) w postaci kombinacji r

n

−2

i r

n

−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) = 137u + 20v.

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 r

n

= 1 (lub

r

n

= 1) to N W D(a, b) = 1, tzn. nie ma potrzeby wykonywania ostatniego dzielenia.

3