19
Selanjutnya,
dijelaskan
sebuah
cara
untuk
merepresentasikan
pembagi
persekutuan terbesar bilangan bulat. Diberikan notasi sebagai berikut,
a1
Z
+
a2
Z
+
K
+
a
k
Z
=
{a
1
z1
+
a2 z
2
+
K
+
a
k
z
h
:
z
i
?
Z 1 = i =
,1 = i =
k
}
yaitu himpunan semua kombinasi linear bilangan bulat dari
a
i
,1 = i =
k
.
Contoh 2.1.2.7.
Himpunan semua kombinasi linear dari 4 dan 5 adalah:
4Z + 5Z
=
{4 z
1
+
5z
2
:
z1
,
z
2
?
Z
}
Teorema
2.1.2.4.
(Buchmann,
2000)
Himpunan
semua
kombinasi
linear
dari
bilangan
bulat a dan b adalah himpunan semua bilangan bulat kelipatan
gcd
(a, b)
, yaitu:
aZ + bZ
=
gcd
(a, b)Z .
(2.6)
Bukti:
Untuk
a bZ . Diambil
=
b
=
0
,
persamaan (2.6) benar. Diambil a atau b tidak nol, dibentuk himpunan
I
=
aZ + bZ . Diambil
g
?
I
, yaitu bilangan bulat positif terkecil dalam
I. Diklaim
bahwa
I
=
gZ . Diambil
sebuah elemen tak
nol
c
?
I
.
Akan ditunjukkan bahwa
c
=
qg
untuk
suatu
q
?
Z
.
Menggunakan
algoritma
pembagian,
terdapat
q, r ? Z
dengan
c
=
qg + r
dan
0
=
r
<
g
. Akibatnya,
r
=
c
-
qg ? I . Akan tetapi, karena g adalah
bilangan bulat positif terkecil dalam I, maka I , maka g adalah pembagi persekutuan
r
=
0
dan
c
=
qg . Selanjutnya, akan
ditunjukkan bahwa
g
=
gcd
(a, b) Karena
. Karena
a, b ? I , maka g adalah pembagi persekutuan
dari
a
dan
b.
Karena
g
?
I
,
maka
terdapat
x, y ? Z
dengan
g
=
xa +
yb .
Oleh
karena
itu,
jika
d
adalah
pembagi
persekutuan
dari
a
dan
b,
maka
d
juga
merupakan
pembagi
 |