21
Definisi 2.1.2.6. [(Stinson, 1995), (Buchmann, 2000)] Diberikan
a, b ? Z . Jika
gcd
(a, b)
=
1,
maka
a
dikatakan
relatif
prima
dengan
b.
Bilangan
bulat
dikatakan saling relatif prima jika
gcd
(
a1
,
a2 ,K, a
n
)
=
1.
Contoh 2.1.2.8.
Karena gcd(17,30) = 1 , maka 17 relatif prima dengan 30.
a1 , a2 ,K, a
n
Teorema 2.1.2.5. (Fraleigh, 2000)
Jika
bilangan
bulat
a
dan
b
relatif
prima
dan
a
|
bm , maka
a
|
m
.
Bukti:
Diketahui
a
dan
b
relatif
prima,
yaitu
gcd
(a, b)
=
1
dan
a
|
bm .
Menggunakan
Akibat
2.1.2.2 maka terdapat
x, y ? Z
sedemikian
hingga
ax + by = 1
.
Selanjutnya, kedua ruas
dikalikan dengan
m
?
Z
,
diperoleh
axm + bym =
m
.
Karena
a
|
axm
dan
a
|
bym , maka
a
|
m
.
E.
Algoritma Euclide
Berikut ini diberikan sebuah
algoritma
yang
dapat
digunakan
untuk
menghitung
nilai
pembagi
persekutuan
terbesar dari dua bilangan bulat dengan sangat efisien.
Algoritma ini didasarkan pada teorema di bawah ini.
Teorema 2.1.2.6. (Buchmann, 2000) Diberikan
a, b ? Z .
1. Jika
b
=
0
,
maka
gcd
(a, b)
= a .
2. Jika
b
?
0
,
maka
gcd
(a, b)
=
gcd
(b, a mod b)
.
 |