Page 80 - MODUL KSM TEST
P. 80
Contoh
Tentukan (a, b) dan [a, b] jika a = 9800 dan b = 14742
Penyelesaian
Faktorisasi prima dari a dan b adalah a = 2 . 3 . 5 . 7 . 13 dan b = 2 . 3 . 5 . 7 .
2
0
4
2
1
1
0
3
0
13
1
maka
(a, b) = 21 . 30 . 50 . 71. 130 = 14, dan
[a, b] = 23 . 34 . 52 . 72 . 131 = 10319400.
PERSAMAAN DAN SISTEM PERSAMAAN BILANGAN BULAT
Persamaan Diophantine
Suatu persamaan berbentuk ax + by = c dengan a, b , c bilangan bulat dan a, b dua-
duanya bukan nol disebut persamaan linier Diophantine. Jika penyelesaiannya
dicari untuk bilangan-bilangan bulat.
Contoh : Tentukan semua solusi dari persamaan Diophantine
56x + 72y = 40
Penyelesaian.
Dengan menerapkan algoritma Euclid untuk menentukan (72,56), kita peroleh
72 = 1 . 56 +16
56 = 3 . 16+8
16 = 2 . 8
Dengan demikian (56, 72) = 8. Setiap bilangan yang berbentuk 56x + 72y
merupakan kelipatan 8. Karena 8 | 40 maka persamaan di atas mempunyai
solusi. Dengan membalikkan urutan pengerjaan, kita peroleh:
8 = 56 – 3.16
= 56 – 3 – (72-56)
= 4 . 56 – 3.72
Dengan mengalikan kedua ruas dengan 5, kita peroleh 20 . 56 – 15 . 72 = 40
Jadi x = 20 dan y = – 15 merupakan salah satu solusinya. Solusi umumnya berbentuk
x = 20 + (72/8) t = 20 + 9t
y = –15 – (56/8) t= –15 – 7t
