Faktor persekutuan terbesar

Dalam matematika, Faktor Persekutuan Terbesar (FPB atau Faktor Pembagi Terbesar) dari dua bilangan adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan tersebut.

Dalam bahasa Inggris, FPB dikenal dengan Greatest Common Divisor (GCD), sering juga disebut sebagai Greatest Common Factor (GCF) atau Highest Common Factor (HCF).

Dua buah bilangan dikatakan saling prima jika dan hanya jika FPB dari kedua bilangan tersebut bernilai 1.

Notasi

Pada artikel ini, FPB dari dua buah bilangan a dan b ditulis sebagai FPB (a, b). Beberapa penulis menuliskannya sebagai (a, b).

Contoh

Cara sederhana dapat digunakan untuk mencari FPB dari 2 atau 3 bilangan yang tidak terlalu besar, namun untuk bilangan yang lebih besar dapat digunakan cara pemfaktoran.

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 pemfaktoran

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 untuk mendapatkan faktorisasinya:

Faktorisasi 147 = 3¹ x 7²

Faktorisasi 189 = 3³ x 7¹

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

• Contoh soal
  • Ibu Rogu memiliki 96 buah rambutan, 48 buah mangga serta 72 buah apel. Buah-buahan dibagikan secara rata-rata kepada teman-teman Rogu. Berapa banyak anak mendapatkan buah-buahan secara rata? berapa jumlah masing-masing buah yang dibagikan kepada anak-anak?

96 = 2⁵ x 3

48 = 2⁴ x 3

72 = 2³ x 3³

fpb dari 48, 72 dan 96 adalah 2³ x 3 = 24 anak

jadi banyak anak mendapatkan buah-buahan secara rata adalah 24.

untuk masing-masing buah

96/24 = 4; 48/24 = 2; 72/24 = 3

jadi jumlah masing-masing buah yang dibagikan kepada anak-anak adalah 4 buah rambutan, 2 buah mangga serta 3 buah apel.

Algoritme Euklidean

Cara lain untuk mencari FPB adalah dengan menggunakan algoritme Euklidean. Misalkan a dan b adalah 2 bilangan bulat yang tidak sama, maka algoritme 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)

Algoritme tersebut berhenti hingga diperoleh a_i = b_i.

FPB dari a dan b adalah a_i = b_i.

Algoritme ini dapat lebih jauh disederhanakan lagi dengan pembagian Euklidean, yang dideskripsikan sebagai berikut:

$\gcd(a,0)=0$

$\gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)$

dengan $a\,\mathrm {mod} \,b$ adalah operasi modulus.

Pencarian algoritme Euklid dengan pembagian memerlukan sekitar $O(\log(\min(a,b)))$ pembagian.

Lihat pula

• Kelipatan persekutuan terkecil (KPK)