9467141759

W podobny sposób definiujemy największy wspólny dzielnik liczb całkowitych tą, b₂, ■~b_n z których przynajmniej jedna jest różna od zera. Dzielnik ten oznaczamy symbolem (bi,b₂,...b_n).

Twierdzenie. Jeśli g = (6, c) jest największym wspólnym dzielnikiem liczb całkowitych b i c, to istnieją liczby całkowite xo, yo takie, że

g = bx₀ + cy₀.

Innymi słowy: największy wspólny dzielnik liczb całkowitych b i c jest kombinacją liniową tych liczb o współczynikach całkowitych.

Twierdzenie. Największy wspólny dzielnik liczb całkowitych b i c może być scharakteryzowany w następujący sposob:

(1)    Jako najmniejsza liczba naturalna należąca do zbioru

A = {bx + cy : x, y € Z} .

(2)    Jako wspólny naturalny dzielnik liczb b i c podzielny przez każdy inny wspólny dzielnik tych liczb.

Twierdzenie (Algorytm Euklidesa). Niech b i c będą dwiema liczbami całkowitymi, przy czym c > 0. Największy wspólny dzielnik liczb b i c może być obliczony przy pomocy serii równości:

3102 =	2 • 1044	+	1014,
1044 =	1 • 1014	+	30,
1014 =	33-30	+	24,
30 -	1-24	+	6,
24 =	4-6.

b	= ki ■ c	+	n,	0 < n < c,
c	= h ■ n	+	o,	0 < r2 < ri,
O	= h-r2	+	o,	0 < r3 < r2,
O	= h ■ r3	+	n,	0 < r4 < ^3,
^r3-2 O-i	= kj-r.i-i = kj+1 ■ rs.	+	O.	0 < rj < rj-:

Ostatnia reszta rj jest największym wspólnym dzielnikiem liczb b i c. Przykład. Niech b = 3102, c = 1044. Algorytm Euklidesa daje nam równości

Ostatnia reszta jest równa 6. Zatem (3102,1044) = 6.

Z poprzednich równości otrzymujemy kolejno

6 = 30 - 1 • 24 = 30 - (1014 - 33 • 30) = 34 • 30 - 1014 =

= 34 • (1044 - 1014) - 1014 = 34 • 1044 - 35 • 1014 =

= 34 • 1044 - 35 • (3102 - 2 • 1044) = (-35) • 3102 + 104 • 1044.

2