Faktor persekutuan terbesar

Dalam matematika, khususnya teori bilangan, faktor persekutuan terbesar atau dikenal juga sebagai persekutuan bilangan terbesar (dilambangkan $\operatorname {FPB}$ atau $\operatorname {PBT}$ dalam bahasa Indonesia, dan $\gcd$ dalam bahasa Inggris, abreviasi dari kata greatest common divisor) terhadap bilangan adalah bilangan bulat terbesar yang membagi setiap bilangan bulat. Sebagai contoh, diberikan bilangan bulat $12$ dan $20$. Maka, $\operatorname {FPB} (12,20)=4$. Mengenai cara-cara dan metode akan dijelaskan di bawah.

Gagasan faktor persekutuan terbesar dapat diperluas melalui polinomial, lihat faktor persekutuan terbesar polinomial atau persekutuan bilangan terbesar polinomial untuk melihat lebih lanjut.

Notasi

Untuk $a$ dan $b$ bilangan bulat sembarang, notasi faktor persekutuan terbesar dinotasikan sebagai $\operatorname {FPB} (a,b)$ atau $\operatorname {PBT} (a,b)$. Dalam versi bahasa Inggris, dinotasikan sebagai $\gcd(a,b)$ atau $\operatorname {GCD} (a,b)$. Ada beberapa penulisan notasi faktor persekutuan terbesar, yaitu $\operatorname {g.c.d} (a,b)$ atau $(a,b)$.

Definisi

Misalkan $a$ dan $b$ adalah dua bilangan bulat yang diberikan. Misalkan $d$ membagi $a$ dan $b$ dan $d$ bilangan asli, maka faktor persekutuan terbesar terhadap bilangan bulat $a$ dan $b$ adalah

$\operatorname {FPB} (a,b)=d$.

Lebih umumnya lagi, untuk sebarang bilangan bulat $a_{1},\dots ,a_{n}$ dan $d$ bilangan asli yang membagi $a_{1},\dots ,a_{n}$, maka faktor persekutuan terbesarnya adalah

$\operatorname {FPB} (a_{1},\dots ,a_{n})=d$.

Contoh

Terdapat cara sederhana mengenai pencarian suatu faktor persekutuan terbesar terhadap dua bilangan. Sebagai contoh, kita ambil contoh bilangan bulat di atas sebelumnya, yakni $12$ dan $20$. Untuk mengetahui mengapa $\operatorname {FPB} (12,20)=4$, kita perhatikan faktor-faktor dari kedua bilangan di bawah ini.

• Faktor dari $12$ adalah $1,2,3,{\color {red}{4}},6,12$
• Faktor dari $20$ adalah $1,2,{\color {red}{4}},5,10,20$

Karena faktor persekutuan terbesar dua bilangan adalah bilangan bulat terbesar yang membagi setiap bilangan bulat, maka kita simpulkan $\operatorname {FPB} (12,20)=4$. Terdapat cara lain untuk mengerjakan ini.

Pohon faktor

Sebagai contoh, tinjau kedua bilangan di atas. Kita buatkan pohon faktor dari masing-masing bilangan:

             12         20
             /\         /\
            3  4       2  10
              /\          /\
             2  2        2  5

Kita memperoleh $12={\color {red}{2^{2}}}\times 3$ dan $20={\color {red}{2^{2}}}\times 5$, maka, $\operatorname {FPB} (12,20)=2^{2}$, di mana hasilnya adalah $4$.

Koprima

Artikel utama: Koprima (bilangan)

Dua buah bilangan dikatakan koprima, atau relatif prima, atau saling prima jika dan hanya jika faktor persekutuan terbesar dari kedua bilangan tersebut bernilai 1.

Penerapan

Menyederhanakan pecahan

Salah satu penerapan terhadap faktor persekutuan terbesar adalah menyederhanakan pecahan. Sebagai contoh, tinjau pecahan ${\frac {4}{8}}$. Kita dapat sederhanakan pecahan ini dengan menggunakan faktor persekutuan terbesar. Faktor persekutuan terbesar dari $4$ dan $8$ adalah $\operatorname {FPB} (4,8)=2$. Kita tuliskan sebagai

${\frac {4}{8}}={\frac {1}{2}}$.

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)