FPB Dan Algoritma Pembagian

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
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