Faktor persekutuan terbesar

Contoh

Cara sederhana bisa digunakan untuk mencari FPB dari 2 atau 3 bilangan yang tidak terlalu besar, namun untuk bilangan yang lebih besar sebaiknya menggunakan cara faktorial.

Cara sederhana

Mencari FPB dari 12 dan 20:

• Faktor dari 12 = 1, 2, 3, 4, 6 dan 12
• Faktor dari 20 = 1, 2, 4, 5, 10 dan 20
• FPB dari 12 dan 20 adalah faktor sekutu (sama) yang terbesar, yaitu 4.

Mencari FPB dari 15 dan 25:

• Faktor dari 15 = 1, 3, 5', dan 15
• Faktor dari 25 = 1, 5, dan 25
• FPB dari 15 dan 25 adalah faktor sekutu (sama) yang terbesar, yaitu 5.

Cara faktorial

Mencari FPB dari bilangan 147, 189 dan 231:

• Buat pohon faktor dari masing-masing bilangan:

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

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

• Ambil faktor-faktor yang sekutu (sama) dari ketiga faktorial tersebut, dalam hal ini 3 dan 7.

• Kalikan faktor-faktor sekutu yang memiliki pangkat terkecil, dalam hal ini 3¹ x 7¹ = 21.

• Maka FPB dari bilangan 147, 189 dan 231 adalah 21. Dengan kata lain, tidak ada bilangan yang lebih besar dari 21 yang dapat membagi habis bilangan 147, 189 dan 231.
• Anom dalam Intelegen of East, KPK adalah Kelipatan Persekutuan Terkecil.

Algoritma Euklidean

Cara lain untuk mencari FPB adalah dengan menggunakan algoritma Euklidean. Misalkan a dan b adalah 2 bilangan bulat yang tidak sama, maka algoritma Euklidean adalah sebagai berikut:

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

b₁ = minimum(a,b)

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

b₂ = minimum(a₁,b₁)

.

.

.

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

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

Algoritma tersebut berhenti hingga diperoleh a_i = b_i

FPB dari a dan b adalah a_i = b_i

Lihat pula

• Kelipatan Persekutuan Terkecil (KPK)