Faktor persekutuan terbesar

Dari Wikipedia Indonesia, ensiklopedia bebas berbahasa Indonesia.

Dalam matematika, faktor persekutuan terbesar dari dua bilangan, atau yang lebih sering disingkat menjadi FPB (atau GCD dan HCF dalam bahasa Inggris) adalah bilangan bulat terbesar yang dapat membagi kedua bilangan itu.

Contoh:

Mencari FPB dari bilangan 147, 189 dan 231

Langkah 1 : Buat pohon faktor dari masing-masing bilangan

             147         189             231
              /\          /\              /\
             3 49        3  63           3  77
               /\           /\              /\
              7  7         7  9            7  11
                              /\
                             3  3

Langkah 2 : Susun bilangan dari pohon faktor utk mendapatkan faktorialnya

Faktorial 147 = 3 x 7²

Faktorial 189 = 3³ x 7

Faktorial 231 = 3 x 7 x 11

Untuk mendapatkan FPB, cari bilangan-bilangan yang berulang (saja) dari ketiga faktorial, kemudian ambil bilangan dari masing-masing bilangan tersebut yang perulangannya paling sedikit, dari faktorial diatas maka bilangan yang dimaksud adalah 3 & 7. Maka didapat FPB dari bilangan 147, 189 dan 231 adalah 3 x 7 = 21. Dengan kata lain, tidak ada bilangan yang lebih besar dari 21 yang dapat membagi bulat bilangan 147, 189 dan 231.

Euclid menemukan sebuah algoritma untuk mencari FPB dari dua buah bilangan misalnya a dan b dengan a tidak sama dengan b, yaitu :

a₁ = maximum(a,b)-minimum(a,b)

b₁ = maximum(a,b)

a₂ = maximum(a₁,b₁)-minimum(a₁,b₁)

b₂ = maximum(a₁,b₁)

.

.

.

a_i = maximum(a_i-1,b_i-1)-minimum(a_i-1,b_i-1)

b_i = maximum(a_i-1,b_i-1)

algoritma tersebut berhenti hingga diperoleh a_i = b_i

Sedangkan untuk mencari Kelipatan Persekutuan Terkecil (KPK) adalah mencari nilai yang terbesar yaitu 3³ x 7² x 11 = 14553

lihat juga Kelipatan Persekutuan Terkecil (KPK).