FPB DAN ALOGARITMAPEMBAGIAN

Faktor Persekutuan dari a dan b adalah bilangan bulat d yang memenuhi d a dan d b. Nilai terbesar dari d disebut faktor persekutuan terbesar (FPB) dari a dan b, ditulis (a, b) = d.

Contoh : (10,12) = 2, ( 12, 15 ) = 3, ( 16, 20 ) = 4.

Jika a dan b dua buah bilangan bulat positif dan (a, b ) = 1 maka dikatakan a dan b saling prima atau a relatif prima terhadap b.

TEOREMA ( ALGORITMA PEMBAGIAN )

Jika a dan b bilangan-bilangan bulat dengan b > 0, maka ada dengan tunggal pasangan bilangan-bilangan bulat q dan r yang memenuhi a = qb + r, dengan 0 ≤ r < b.

Selanjutnya FPB dari a dan b dapat dicari dengan mengulang-ulang algoritma pemabgian ini.

CONTOH

1.  Tentukan (4840, 1512) Jawab :

4840 = 3 × 1512 + 304

1512 = 4 × 304 + 296

7

304=1×296+8

296=37×8+0

Jadi (4840, 1512) = 8

2.  Buktikan bahwa jika ( a, b ) = 1 dan a bc , maka a c. Bukti :

( a, b ) = 1 ⇒ terdapat m dan n sedemikian sehingga 1 = ma + nb.

a     bc ⇒ terdapat k sedemikian sehingga bc = ak.

Diperoleh        1 = ma + nb

c . 1 = mac + nbc

c = mac + nak

c = a ( mc + nk ) ⇔ a      c