Faktor persekutuan terbesar

Dalam matematika, **faktor persekutuan terbesar** (FPB) dari dua bilangan bulat adalah bilangan bulat terbesar yang sama-sama membagi habis kedua bilangan bulat tersebut. Sebagai contoh, faktor persekutuan terbesar 24 dan 60 adalah 12.

Dua bilangan atau lebih disebut saling prima jika FPB bilangan-bilangan tersebut sama dengan 1. Sebagai contoh, karena FPB bilangan 9 dan 28 sama dengan 1, maka bilangan 9 dan 28 adalah saling prima (walaupun masing-masingnya bukan bilangan prima)

Faktor persekutuan terbesar (FPB) dan sekawannya, kelipatan persekutuan terkecil (KPK), menjadi pembahasan yang penting dalam aritmetika dan teori bilangan.

## Definisi
Suatu bilangan c disebut faktor persekutuan bilangan a dan b jika c habis membagi bilangan a dan b sekaligus.

Suatu bilangan d disebut faktor persekutuan terbesar bilangan jika:

* d faktor persekutuan bilangan a dan b; dan
* jika c faktor persekutuan bilangan a dan b maka berlaku c\leq d

bilangan d ditulis sebagai FPB(a,b) atau (a,b).

### Peristilahan
Secara bahasa, kata "persekutuan" berarti hal bersama-sama dan kata "faktor" berarti 'pembagi'. Maka dari itu, sebagian penulis menggunakan istilah lain untuk FPB, seperti **pembagi persekutuan terbesar,** atau **pembagi bersama terbesar**, dilambangkan dengan \text{PBT}(a,b). Dalam penulisan matematika kadang dipakai juga notasi \text{gcd}(a,b), berasal dari bahasa Inggris **greatest common divisor**.

## Contoh

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

Faktor persekutuan 12 dan 20 adalah 1, 2, 4. Karena 4 adalah bilangan terbesar di antara faktor persekutuan itu, maka disimpulkan \operatorname{FPB}(12,20) = 4.

## Perhitungan FPB

### Faktorisasi prima
FPB dari beberapa bilangan dapat ditentukan dengan mencari faktorisasi prima bilangan-bilangan itu kemudian mengalikan faktor-faktor primanya yang sama dengan pangkat terkecil. Sebagai contoh, akan ditentukan FPB dari 24 dan 60. Dengan pohon faktor

diperoleh 60 = {\color{red}{2}}^2 \times {\color{red}{3}} \times 5 dan 24 = {\color{red}{2}}^3 \times {\color{red}{3}}. Dengan mengambil faktor prima yang sama dengan pangkat maka, \operatorname{FPB}(60,24) = 2^2 \times 3 = 12.

### Algoritma Euklides

Euclid menemukan sebuah algoritma untuk mencari FPB. Misalkan a dan **<math>b</math>** adalah 2 bilangan bulat yang tidak sama, maka FPB dua bilangan itu dapat dicari dengan algorirma sebagai berikut:
```
1. masukkan nilai a dan b;
2. misalkan u:=a dan v:=b;
3. selama u ≠ v, ulangi
   u = maximum (u,v) - minimum (u,v)
   v = minimum (u,v);
4. FPB(a,b)=u;
```


## Sifat
Untuk sebarang bilangan bulat a,b,c, dengan |a| adalah nilai multak dari a, berlaku:

* Sifat komutatif, yaitu \operatorname{FPB}(a,b)=\operatorname{FPB}(b,a).
* Sifat asosiatif, yaitu \operatorname{FPB}(a,b,c)=\operatorname{FPB}(a,\operatorname{FPB}(b,c))=\operatorname{FPB}(\operatorname{FPB}(a,b),c).
* Sifat distributif, yaitu \operatorname{FPB}(ac,bc) = c \cdot \operatorname{FPB}(a,b)
* Jika c faktor persekutuan a dan b, maka c \mid \operatorname{FPB}(a,b), dan \operatorname{FPB}\left(\frac{a}{c},\frac{b}{c}\right)=\frac{\operatorname{FPB}(a,b)}{c}, sehingga jika d=\operatorname{FPB}(a,b) maka \operatorname{FPB}\left(\frac{a}{d},\frac{b}{d}\right)=1
* \operatorname{FPB}(\pm a,\pm b)=\operatorname{FPB}(b,a)
* \operatorname{FPB}(a,b)=\operatorname{FPB}(a,b-a)=\operatorname{FPB}(a,b+a)=\operatorname{FPB}(a,b-ca)
* \operatorname{FPB}(a,0) = |a|
* \operatorname{FPB}(a,1) = 1
* Untuk sebarang bilangan bulat positif a,b, \operatorname{FPB}(a,b) = b jika dan hanya jika **<math>b</math>** habis membagi a.

## 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, pecahan \frac{4}{8} dapat disederhanakan 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{2 \times 2}{2 \times 4} = \frac{1}{2}.

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

## Lihat pula
* Kelipatan persekutuan terkecil (KPK)
## Rujukan