FPB (Faktor Persekutuan terBesar), bisa juga disebut GCD (Greatest Common Divisor) dari dua atau lebih bilangan bulat positif bukan nol, adalah bilangan bulat positif terbesar yang dapat membagi dua atau lebih bilangan bulat bukan nol tersebut tanpa sisa.
Banyak metode yang dapat digunakan untuk mencari FPB. Metode yang umum digunakan pada saat sebelum kuliah ialah metode pagar dan metode pohon faktor. Metode pagar maupun metode pohon faktor efektif untuk bilangan-bilangan kecil. Jika bilangan yang dicari FPB-nya besar, maka lebih efektif menggunakan algoritma Euclid.
Algoritma Euclid ialah algoritma yang dilaksanakan secara bertahap, step by step, di mana hasil yang didapat dari suatu tahap akan digunakan lagi pada tahapan selanjutnya. Prosedur pada algoritma Euclid ialah mencari sisa (remainder) dari pembagian bilangan yang lebih besar (kita misalkan a) dengan bilangan yang lebih kecil (misalkan b). Anggap sisa a dibagi b sebagai r1. Jika r1 bukan nol, langkah selanjutnya ialah mencari sisa dari b dibagi r1.
Jika sisanya masih bukan nol, maka selanjutnya mencari lagi sisa r1 dibagi r2 (r2 ialah sisa dari b dibagi r1). Jika masih belum nol, maka mencari lagi sisa r2 dibagi r3. Begitu seterusnya sampai sisa pembagian ialah 0. Misalnya ditemukan sisa dari rn-1 dibagi rn ialah 0, maka FPB dari dua bilangan yang tadi dicari (a dan b) ialah rn. Secara matematis, prosedur ini dapat ditulis sebagai :
Banyak metode yang dapat digunakan untuk mencari FPB. Metode yang umum digunakan pada saat sebelum kuliah ialah metode pagar dan metode pohon faktor. Metode pagar maupun metode pohon faktor efektif untuk bilangan-bilangan kecil. Jika bilangan yang dicari FPB-nya besar, maka lebih efektif menggunakan algoritma Euclid.
Algoritma Euclid ialah algoritma yang dilaksanakan secara bertahap, step by step, di mana hasil yang didapat dari suatu tahap akan digunakan lagi pada tahapan selanjutnya. Prosedur pada algoritma Euclid ialah mencari sisa (remainder) dari pembagian bilangan yang lebih besar (kita misalkan a) dengan bilangan yang lebih kecil (misalkan b). Anggap sisa a dibagi b sebagai r1. Jika r1 bukan nol, langkah selanjutnya ialah mencari sisa dari b dibagi r1.
Jika sisanya masih bukan nol, maka selanjutnya mencari lagi sisa r1 dibagi r2 (r2 ialah sisa dari b dibagi r1). Jika masih belum nol, maka mencari lagi sisa r2 dibagi r3. Begitu seterusnya sampai sisa pembagian ialah 0. Misalnya ditemukan sisa dari rn-1 dibagi rn ialah 0, maka FPB dari dua bilangan yang tadi dicari (a dan b) ialah rn. Secara matematis, prosedur ini dapat ditulis sebagai :
(Ingat bahwa jika a mod b = r1 maka bisa diartikan bahwa a = qb + r1 )
Berarti, pada persamaan di atas FPB(a, b) = rn. Yang perlu diingat pada algoritma Euclid ialah bahwa remainder atau sisa tidak boleh negatif, harus bernilai positif (mana ada sisa bernilai negatif, ya nggak? Tapi kalo menggunakan modular, nilai negatif bisa tercipta.)
Sekarang setelah kita tahu teorinya, mari kita praktekkan. Misalnya bilangan yang "kecil" dulu, FPB(3456, 321).
Di sini kita temukan bahwa sisa menjadi nol saat tahap ke-7, yaitu ketika mencari sisa 9 dibagi 3. Ini menandakan bahwa FPB(3456, 321) = 3.
