plik

Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedońska

Wykład 3.

Największy wspólny dzielnik

Definicja 1. Niech a, b ∈ Z i przynajmniej jedna z tych liczb jest różna od 0.
Liczbę naturalną d nazywamy największym wspólnym dzielnikiem liczb
a i b i oznaczamy NW D(a, b) jeśli:

1. d|a oraz d|b (wspólny dzielnik),
2. jeśli c ∈ Z jest taką liczbą, że c|a oraz c|b, to c ≤ d (największy).

Przykład NW D(3, 7) = 1, NW D(2, 4) = 2, NW D(4, 0) = 4.

Uwaga Wprost z definicji mamy

NW D(a, b) = NW D(−a, b) = NW D(a, −b) =

= NW D(−a, −b) = NW D(b, a) = NW D(|a|, |b|).

Twierdzenie 1. ( NW D jako kombinacja liniowa )
Dla a, b ∈ Z nie równych jednocześnie zeru istnieją u, v ∈ Z takie, że

NW D(a, b) = au + bv.

Dowód. Rozważmy zbiór wszystkich dodatnich kombinacji liniowych liczb
a i b, tzn. zbiór

S = {ax + by; x, y ∈ Z} ∩ N.

Zauważmy najpierw, że liczba a

+ b

jest dodatnia, ponieważ a i b nie są

jednocześnie równe zeru. Wobec tego a

+ b

∈ S, czyli zbiór S nie jest pusty,

zatem na podstawie Zasady Minimum (Wykład 1, Tw.1) istnieje w S liczba
najmniejsza. Oznaczmy tę liczbę przez t oraz liczby x, y które ją definiują
odpowiednio przez u, v, czyli mamy równość t = au + bv. Pokażemy, że
t = NW D(a, b) sprawdzając kolejno własności w definicji.

Pokażemy najpierw, że t dzieli a, to znaczy, że reszta przy dzieleniu a

przez t jest zerem. Na podstawie Twierdzenia Euklidesa (Wykład 2, Wn.1)
istnieje dokładnie jedna para liczb q, r ∈ Z takich że

a = tq + r,

0 ≤ r < t.

Wynika stąd, że

r = a − tq = a − (au + bv)q = a(1 − qu) + b(−vq),

(∗)

czyli r jest kombinacją liniową a i b. Ponieważ r < t oraz t jest najmniejszą
dodatnią kombinacją liniową a i b, to r /

∈ S, a więc r nie jest liczbą dodatnią.

Wobec tego r = 0 i z (∗) wynika, że a = tq. Ponieważ q ∈ Z, to znaczy, że t
dzieli a.

W podobny sposób możemy pokazać, że t dzieli b, co oznacza, że t jest

wspólnym dzielnikiem a i b.

Dla sprawdzenia drugiej własności załóżmy, że c też jest wspólnym dziel-

nikiem a i b, czyli c|a oraz c|b. Wtedy dla pewnych liczb całkowitych r, s
mamy a = cr, b = cs. Wynika stąd, że

t = au + bv = (cr)u + (cs)v = c(ru + sv).

Ponieważ ru + sv ∈ Z, to z powyższej równości otrzymujemy c|t, a z Własno-
ści 1 (Wykład 2, Tw.1) mamy dalej |c| ≤ |t|. Ponieważ t > 0, to jeśli c < 0,
to oczywiście mamy c ≤ t. Jeśli c > 0 to c = |c| ≤ |t| = t. Zatem t spełnia
też drugą własność, czyli ostatecznie t = NW D(a, b).

Uwaga Para u, v w powyższym Twierdzeniu nie jest określona w sposób
jednoznaczny. Np. dla a = 2, b = 3 mamy 1 = (−1) · 2 + 1 · 3, ale mamy też
1 = 2·2+(−1)·3. Co więcej, takich par jest nieskończenie wiele – zauważmy,
że dla dowolnego t ∈ Z para postaci u = 1 + 3t, v = 1 − 2t spełnia równanie
2u + 3v = 1.

Wniosek 1. Niech a, b ∈ Z i przynajmniej jedna z tych liczb jest różna od 0.
Liczba naturalna d jest równa NW D(a, b) wtedy i tylko wtedy gdy:

Dowód. Pokażemy dwie implikacje. Zauważmy, że warunek 1 jest dokładnie
taki jak w definicji NW D, pozostaje więc tylko sprawdzić równoważność
warunku 2 z drugim warunkiem w definicji NW D.

(=⇒)

Niech d = NW D(a, b). Z powyższego Twierdzenia wynika, że

dla pewnych u, v ∈ Z mamy d = au + bv. Niech c ∈ Z będzie taką liczbą,
że c|a, c|b. Wobec tego z Własności 8 (Wykład 1, Tw.1) w szczególności
wynika, że c|au + bv, czyli c|d.

(⇐=)

Niech liczba naturalna d spełnia warunek 2, tzn. że dla dowolnie

wybranej liczby całkowitej c takiej, że c|a oraz c|b mamy c|d. Wtedy na
podstawie Własności 1 (Wykład 2, Tw.1) |c| ≤ |d|. Ponieważ d > 0, to jeśli
c < 0, to oczywiście mamy c ≤ d. Jeśli c > 0 to c = |c| ≤ |d| = d. Zatem d
spełnia drugi warunek w definicji NW D.

Z Twierdzenia 1 oraz powyższego Wniosku wynika następujący

Wniosek 2. (Równoważne definicje NW D)
Niech a, b ∈ Z i przynajmniej jedna z tych liczb jest różna od 0. Liczbę
naturalną d nazywamy NW D(a, b) jeśli

(Definicja 1)

1. d|a, d|b

2. jeśli c ∈ Z jest taką liczbą, że c|a, c|b, to c ≤ d.

lub

(Definicja 2)

1. d|a, d|b,

2. jeśli c ∈ Z jest taką liczbą, że c|a, c|b, to c|d.

lub

(Definicja 3)

d jest najmniejszą dodatnią liczbą postaci au + bv, gdzie u, v ∈ Z.

Definicja 2. Liczby całkowite a i b nazywamy względnie pierwszymi, jeśli
NW D(a, b) = 1.

Przykład 3 i 2, 3 i 4, 9 i 4 są względnie pierwsze, 4 i 6 nie.

Twierdzenie 2. Liczby a, b ∈ Z są względnie pierwsze wtedy i tylko wtedy
gdy istnieją u, v ∈ Z takie że

1 = au + bv.

Dowód. Pokażemy dwie implikacje.

(=⇒)

Jeśli liczby a i b są względnie pierwsze, to NW D(a, b) = 1 i na

podstawie Twierdzenia 1, istnieją u, v ∈ Z takie że 1 = au + bv.

(⇐=)

Niech dla pewnych całkowitych u, v zachodzi równość 1 = au+bv.

Oznaczmy d = NW D(a, b), wtedy d|a, d|b i na podstawie Własności 8
(Wykład 2, Tw.1) d|au + bv, czyli d|1. Ponieważ d jest liczbą dodatnią, to
z Własności 3 (Wykład 2, Tw.1) mamy d = NW D(a, b) = 1.

Wniosek 3. Jeśli d = NW D(a, b) to liczby

a
d

są względnie pierwsze.

Dowód. Jeśli d = NW D(a, b), to istnieją liczby całkowite p, q takie, że
a = pd, b = qd. Wobec tego liczby

a
d

są całkowite, chociaż mają postać

ułamków. Ponadto, na podstawie Twierdzenia 1, istnieją u, v ∈ Z takie że
d = au + bv. Dzieląc stronami przez d otrzymujemy

1 =

a
d

u +

więc na podstawie Twierdzenia 2 wnioskujemy, że liczby całkowite

a
d

są

względnie pierwsze.

Następujące dwa Lematy związane są z wprowadzonymi pojęciami i na-

zywane są Lematami Euklidesa.

Lemat 1. Niech a, b, c ∈ Z. Jeśli a|c i b|c i NW D(a, b) = 1, to ab|c.

Dowód. Z dwóch pierwszych założeń wynika, że istnieją liczby całkowite r, s
takie, że c = ar, c = bs. Ponadto, z trzeciego założenia oraz Twierdzenia 1
dla pewnych całkowitych u, v mamy, że 1 = au + bv, a stąd

c = cau + cbv = (bs)au + (ar)bv = ab(su + rv),

gdzie su + rv ∈ Z, co oznacza, że ab|c.

Lemat 2. Niech a, b, c ∈ Z. Jeśli a|bc i NW D(a, b) = 1, to a|c.

Dowód. Z drugiego założenia oraz Twierdzenia 1 wynika, że dla pewnych
całkowitych u, v mamy 1 = au + bv, a stąd c = acu + bcv. Ponieważ z pierw-
szego założenia a|bc, to z Własności 8 (Wykład 2, Tw.1) w szczególności
wynika, że a|a(cu) + (bc)v, czyli a|c.

Poniższa definicja stanowi uogólnienie pojęcia NW D:

Definicja 3. Niech a

, a

, ..., a

∈ Z i przynajmniej jedna z tych liczb jest

różna od 0. Liczbę naturalną d nazywamy największym wspólnym dziel-
nikiem liczb a

, a

,..., a

i oznaczamy NW D(a

, a

, ..., a

) jeśli:

1. ∀ i = 1, 2, ..., n

d|a

(wspólny dzielnik).

2. jeśli istnieje taka liczba b ∈ Z, że b|a

dla każdego i = 1, 2, ..., n, to

b ≤ d

(największy).

Przykład NW D(3, 12, 9) = 1, N W D(6, 4, 10) = 2, NW D(5, 4, 7, 0) = 1.

Lemat 3. Niech a, b, c ∈ Z i przynajmniej jedna z liczb a, b jest różna od 0.
Wtedy NW D(a, b, c) = NW D(NW D(a, b), c)

Dowód. Wprowadzamy oznaczenia:

m = NW D(a, b, c), d = NW D(a, b), k = NW D(NW D(a, b), c) = NW D(d, c).

Pokażemy dwie nierówności: m ≤ k oraz k ≤ m, skąd wynika, że m = k

(m ≤ k)

Ponieważ z Definicji 3 w szczególności wynika, że m|a, m|b,

to z drugiej definicji NW D (Wniosek 2) mamy, że m|d. Skoro także m|c, to
z warunku 2 w definicji NW D mamy, że m ≤ k.

(k ≤ m)

Z definicji NW D mamy, że k|c i k|d oraz d|a i d|b.

Z trzech ostatnich podzielności i z Własności 6 (Wykład 2, Tw.1) wynika, że
k|a oraz k|b. Uwzględniając to, że k|c otrzymujemy z uogólnionej definicji
NW D, że k ≤ m.