Faktor persekutuan terbesar

Dalam matematika, khususnya teori bilangan, faktor persekutuan terbesar atau dikenal juga sebagai persekutuan bilangan terbesar (dilambangkan  atau  dalam bahasa Indonesia, dan  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  dan . Maka, . 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  dan  bilangan bulat sembarang, notasi faktor persekutuan terbesar dinotasikan sebagai  atau . Dalam versi bahasa Inggris, dinotasikan sebagai  atau . Ada beberapa penulisan notasi faktor persekutuan terbesar, yaitu  atau .

Definisi 
Misalkan  dan  adalah dua bilangan bulat yang diberikan. Misalkan  membagi  dan  dan  bilangan asli terbesar, maka faktor persekutuan terbesar terhadap bilangan bulat  dan  adalah

Lebih umumnya lagi, untuk sebarang bilangan bulat  dan  bilangan asli terbesar yang membagi , maka faktor persekutuan terbesarnya adalah

Sifat 

Berikut adalah sifat-sifat faktor persekutuan terbesar, antara lain:

 Untuk sebarang bilangan bulat positif , bila  membagi  dan , maka .
 Untuk sebarang bilangan bulat positif ,  jika dan hanya jika .
 Untuk sebarang bilangan bulat positif , .
 , sifat ini sangat penting dalam kalkulasi algoritme Euklides

Contoh 
Terdapat cara sederhana mengenai pencarian suatu faktor persekutuan terbesar terhadap dua bilangan. Sebagai contoh, kita ambil contoh bilangan bulat di atas sebelumnya, yakni  dan . Untuk mengetahui mengapa , kita perhatikan faktor-faktor dari kedua bilangan di bawah ini.

 Faktor dari  adalah 
 Faktor dari  adalah 

Karena faktor persekutuan terbesar dua bilangan adalah bilangan bulat terbesar yang membagi setiap bilangan bulat, maka kita simpulkan . 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  dan , maka, , di mana hasilnya adalah .

Visualisasi geometri 
Ada cara lain untuk mengetahui faktor persekutuan terbesar, yaitu melalui visualisasi geometri. Sebagai contoh, pada gambar di samping kanan, kita memperoleh ubin dengan ukuran 24 kali 60. Ubin tersebut kita bagi lagi menjadi 1 kali 1, 2 kali 2, 3 kali 3, 4 kali 4, 6 kali 6, dan terbesarnya adalah 12 kali 12. Jadi, 12 merupakan faktor persekutuan terbesar dari 24 dan 60, karena  dan .

Koprima 

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 . Kita dapat sederhanakan pecahan ini dengan menggunakan faktor persekutuan terbesar. Faktor persekutuan terbesar dari  dan  adalah . Kita tuliskan sebagai
.

Kelipatan persekutuan terkecil 

Selain digunakan untuk menyederhanakan sebuah pecahan, faktor persekutuan terbesar juga dapat diterapkan dalam kelipatan persekutuan terkecil, di mana hubungan keduanya berkaitan dengan rumus berikut.

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:

 a1 = maximum(a,b)-minimum(a,b)
b1 = minimum(a,b)

 a2 = maximum(a1,b1)-minimum(a1,b1)
b2 = minimum(a1,b1)

.
.
.

 ai = maximum(ai-1,bi-1)-minimum(ai-1,bi-1)
bi = minimum(ai-1,bi-1)

Algoritme tersebut berhenti hingga diperoleh ai = bi.

FPB dari a dan b adalah ai = bi.

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

dengan  adalah operasi modulus.

Pencarian algoritme Euklid dengan pembagian memerlukan sekitar  pembagian.

Lihat pula 
 Kelipatan persekutuan terkecil (KPK)

Rujukan 

Matematika