22
Bukti:
1. Dengan sendirinya langsung terbukti, sebab
gcd
(a, b)
=
gcd
(a,0)
= a .
2. Misalkan
d
=
gcd r .
(a, b)
dan
r
=
a
mod b . Menurut Teorema 2.1.2.2, terdapat
q
?
Z
dengan
a
=
qb + r .
Karena
r
=
a
-
bq
maka
d
|
r
.
Akan
ditunjukkan
bahwa
d
=
gcd
(b, r
)
.
Diambil
sebarang
bilangan
bulat
t
sedemikian
hingga
t | b
dan
t | r ,
yaitu
terdapat t
n, m ? Z
sedemikian
hingga
b
=
nt
dan
r
=
mt .
Diperoleh
bahwa
a
=
ntq + mt = t
(nq +
m
)
atau
t | a .
Diketahui
d
=
gcd
(a, b)
,
karena
t | a
dan
t | b
maka
t
=
d
dan
t
|
d
. Terbukti bahwa
d
=
gcd
(a, b)
=
gcd
(b, a mod b)
.
Misal
diberikan
bilangan
bulat
positif
r
0
dan
r1
,
dengan
r
0
=
r1 .
Selanjutnya
dihitung menggunakan algoritma pembagian sebagai berikut:
r
0
=
q1r1
+
r2 ,
0
<
r2 <
r1
r1 = q2
r2 + r3 ,
0
<
r3 <
r2
M
r
n
-
2
=
q
n
-1
r
n-¹
+
r
n
,
0
<
r
n
<
r
n
-1
r
n-¹
=
q
n
r
n
.
Menggunakan
Teorema
2.1.2.6,
dapat
ditunjukkan
bahwa
gcd
(r
0
,
r1
) = gcd(r
1
,
r2
) =
K
=
gcd
(r
n-¹
,
r
n
) = gcd(r
n
,0
)
=
r
n
.
Jika
diberikan
bilangan
bulat
a
dan b dengan
a
=
b , maka dengan
menentukan
r
0
= a
dan
r1 = b , Teorema 2.1.2.6
dapat
disajikan
sebagai
algoritma
yang
dapat
digunakan
untuk
menghitung
nilai
gcd
(a, b)
. Algoritma ini disebut dengan algoritma Euclide.
 |