20
persekutuan
dari
g.
Menggunakan
Teorema
2.1.2.1
diperoleh
bahwa
|
d
|= g .
Terbukti
bahwa
g
=
gcd
(a, b)
.
Akibat 2.1.2.1. (Buchmann, 2000)
Untuk
setiap
a, b, n ? Z
persamaan
ax + by =
n
mempunyai
penyelesaian
yaitu
bilangan
bulat
x
dan
y
jika
dan
hanya
jika
gcd
(a, b)
membagi n.
Bukti:
?
Misalkan terdapat bilangan bulat x dan y
yang
memenuhi
ax + by =
n
, maka
n
?
aZ + bZ . Menggunakan Teorema 2.1.2.4 diperoleh bahwa
n
?
gcd
(a, b)Z ,
misalkan
n
=
gcd
(a, b)z'
untuk
suatu
z'? Z .
Dari
sini
diperoleh
bahwa
n
adalah
kelipatan
dari
gcd
(a, b)
. Dengan kata lain,
gcd
(a, b)
membagi n.
?
Misalkan
n
adalah
kelipatan
dari
gcd
(a, b)
,
maka
n
?
gcd
(a, b)Z .
Menggunakan
Teorema 2.1.2.4 diperoleh bahwa
n
?
aZ + bZ . Akibatnya terdapat
x, y ? Z
sedemikian
hingga
n
=
ax + by .
Akibat 2.1.2.2. (Buchmann, 2000)
Diberikan
dengan
ax + by = gcd
(a, b)
.
a, b ? Z ,
maka
terdapat
x, y ? Z
Bukti:
Karena
gcd
(a, b)
membagi
dirinya
sendiri,
dengan
menggunakan
Akibat
2.1.2.1
maka
Akibat 2.1.2.2 terbukti.
 |