Faktor Persekutuan Terbesar (FPB)

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

Metode Sederhana

Carilah FPB dari bilangan 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 4, maksudnya tidak ada bilangan yang lebih besar dari 4 yang dapat membagi habis bilangan 12 dan 20.

Metode faktorial
Carilah FPB dari bilangan 147 dan 189

1. Buat pohon faktor dari kedua bilangan tersebut

2. Susun bilangan dari pohon faktor utk mendapatkan faktorialnya:
    Faktorial 147 = 3^1  x  7^2  (^ = pangkat)
    Faktorial 189 = 3^3  x  7^1

3. Ambil faktor-faktor yang sekutu (sama) dari ketiga faktorial tersebut, dalam hal ini 3 dan 7.
4. Kalikan faktor-faktor sekutu yang memiliki pangkat terkecil, dalam hal ini 3^1 x 7^1 = 21

Sehingga didapat bahwa FPB dari bilangan 147, 189 adalah 21, maksudnya tidak ada bilangan yang lebih besar dari 21 yang dapat membagi habis bilangan 147 dan 189.

Metode Euclidean
Algoritma Euklidean adalah suatu algoritma untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritma ini adalah salah satu algoritma yang tertua, dan muncul dalam buku Elemen Euklid sekitar 300 SM. Algoritma ini tidak memerlukan faktorisasi.

Bersambung ...