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

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

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 bilangan terbesar terhadap bilangan bulat $a$ dan $b$ adalah

$\operatorname {FPB} (a,b)=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$.

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)