24
k
algoritma
Euclide
diketahui
bahwa
diperoleh
barisan
sisa
yaitu
r
0
,
r1 ,K, r
n
dan
barisan
hasil bagi yaitu
q1 , q2 ,K, q
n
.
Selanjutnya, dikontruksi dua barisan
(x
k
)
dan
(
y
k
) yang diperoleh dari barisan
sisa dan
hasil bagi sedemikian
hingga pada
iterasi
terakhir diperoleh
x
=
(- 1)
n
(
x
n
)
dan
y
=
(- 1)
n
(
y
n
)
.
Pertama, ditentukan nilai awal yaitu
x
0
=
1
,
x1 = 0 ,
y
0
=
0
dan
y1 = 1 .
Selanjutnya, diberikan persamaan
x
k
+1
=
q
k
x
k
+
x
k
-1
dan
y
k
+1
=
q
k
y
k
+
y
k
-1
,
0
=
k
=
n
.
Teorema 2.1.2.7.(Buchmann, 2000)
Jika dengan
x
0
=
1
,
x1 = 0 ,
y
0
=
0
,
y1 = 1 dengan
x
k
+1
=
q
k
x
k
+
x
k
-1
dan
y
k
+1
=
q
k
y
k
+
y
k 1)
-1
, maka:
r
k
=
(- 1) ( x
k
)a +
(- 1)
k
+1
(
y
k
)b , untuk
0
=
k
=
n
+
1
Bukti:
Akan dibuktikan menggunakan induksi.
Untuk k = 0 diperoleh
r
0
=
a
=
(1)a - (0)b =
x
0
a
-
y
0
b
.
Selanjutnya,
r1 = b =
-
(
0
)
a
+
(
1
)
b
=
-
x1
(a) +
y1
(b)
Misalkan pernyataan benar untuk
k 1) ( x
=
n
, maka pernyataan benar untuk k = n yaitu:
r
n
=
(- 1) ( x
n
)a +
(- 1)
n
+1
(
y
n
)b .
Akan dibuktikan bahwa pernyataan benar untuk k = n + 1, yaitu:
r
n
+1
=
(- 1)
n
+1
(
x
n
+1
)a +
(- 1)
n+ 2
(
y
n
+1
)b .
 |