Page 77 - MODUL KSM TEST
P. 77
Teorema (Lemma Euclid)
Jika a | bc dengan (a, b) = 1 maka a | c.
Lemma
Jika a = qb + r maka (a, b) = (b, r)
Algoritma Euclid
Misalkan kita ingin menentukan pembagai sekutu terbesar dari bilangan bulat a
dan b. Jika keduanya nol, maka pembagi sekutu terbesarnya tidak ada. Jika salah
satunya nol, misalkan b = 0, maka pembagi sekutu terbesarnya adalah |a|. Jadi
sekarang kita cukup meninjau untuk kasus a, b yang keduanya tidak nol. Tanpa
mengurangi keberlakuan secara umum, kita bisa misalkan |b| ≤ |a|. Dengan
menerapkan teorema pembagian pada a dan b, kita peroleh q1 sehingga
a = q1|b| + r1 dengan ≤ r1 < |b|
Dengan menerapkan kembali algoritma pembagian terhadap |b| dan r1 kita
dapatkan q2 sehingga
b = q2r2 + r2 dengan ≤ r2 < rl
Kemudian seperti diatas, berturut-turut kita dapatkan q3, q4,..., qn+1 dan r3 , r4, ...,
rr, sehingga dengan menggunakan lemma sebelumnya kita peroleh
(a, b) = (a, |b|) = (|b|, r1) = (r1, r2) = ... = (rn-1, rn) = rn
CONTOH
Tentukan pembagi sekutu terbesar dari 12378 dan 3054.
Penyelesaian.
Dengan menggunakan algoritma Euclid, kita peroleh
12378 = 4 . 3054 + 162
3045 = 18 . 162 + 138
162 = 1.138 +24
138 = 5 . 24 +18
24 =1.18+6
18 =3.6+0
Dengan demikian (12378, 3054) = (18, 6) = 6.
KELIPATAN PERSEKUTUAN TERKECIL (KPK)
