25
n
-
n+¹
n+
n
n
n
n
Dari
pembahasan
tentang
algoritma
Euclide,
diketahui
bahwa
r
n
+1
=
r
n
-1
-
q
n
r
n
.
Oleh
karena itu,
r
n
+1
=
r
n
-1
-
q
n
r
n
=
((-1)
n
-1
(
x
)a + (-1)
n
(
y
n
-1
)b
)- q
((-1)
n
(
x
)a + (-1)
n+¹
(
y
)b
)
=
(
(-1)
n
-1
(
x
n
-1
)
-
q
n
(-1)
n
(
x
)
)
a
+
(
(-1)
n
(
y
n
-1
)
-
q
n
(-1)
n
+1
(
y
)
)
b
=
(
(-1)
n
+1
(
x
n
-1
)
+
q
n
(-1)
n+¹
(
x
)
)
a
+
(
(-1)
n+ 2
(
y
n
-1
)
+
q
n
(-1)
n
+
2
(
y
)
)
b
=
(- 1)
(x
n
-1
+
q
n
x
n
)a + (- 1)
(
y
n
-1
+
q
n
y
n
)b
=
(- 1)
n
+1
(
x
n+¹
)a +
(- 1)
n
+
2
(
y
n+¹
)b
dengan demikian Teorema 2.1.2.7 terbukti.
Contoh 2.1.2.10. (Buchmann, 2000)
Seperti
pada
Contoh (3)(35) = 5 , diperoleh hasil yang sama pada Contoh 2.1.2.9.
2.1.2.9,
akan
dihitung
nilai
gcd(100,35).
Dimana
gcd
(100,35)
=
(-1)(100) + (3)(35) = 5 , diperoleh hasil yang sama pada Contoh 2.1.2.9.
Tabel 2.2. Perhitungan x dan y menggunakan Teorema 2.1.2.7
 |