|
Faktor Persekutuan Terbesar (FPB) dari dua bilangan adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan itu. FPB juga disebut dengan Greatest Common Divisor (GCD). Pada saat Sekolah Dasar, telah dipelajari bagaimana cara mencari FPB dari dua bilangan positif, yaitu dengan faktorisasi prima.
Sebagai contoh 4 dan 6
4=22
6=2.3
Sehingga FPB dari 4 dan 6 adalah 2 (karena 2 merupakan faktor yang sama dari kedua bilangan). Lalu bagaimana dengan bilangan yang ratusan bahkan ribuan? Tentu sulit apabila mencari FPB dengan cara faktorisasi prima. Untuk itu perlu dipelajari cara lain dalam mencari FPB dua bilangan positif, yaitu dengan algoritma euclide.
Apabila dicari gcd(a,b) dengan a dan b bilangan asli dan a>b, maka berdasarkan algoritma pembagian, akan terdapat bilangan bulat positif q dan r sehingga a=bq+r atau r=a-bq. Dari r=a-bq dapat diketahui bahwa setiap faktor persekutuan dari a dan b merupakan pembagi dari r. Untuk itu dapat disimpulkan bahwa gcd(a,b)=gcd(b,r). Jika r=0 maka gcd(a,b)=gcd(b,0)=b. Apabila r≠0, maka dapat dilakukan langkah yang sama pada b dan r yaitu terdapat bilangan bulat positif q1 dan r1 sehingga b=rq1+r1. Dengan alasan yang sama dapat disimpulkan bahwa gcd(b,r)=gcd(r,r1). Jika r1=0, maka gcd(b,r)=gcd(r,0)=r. Jika tidak, lakukan langkah diatas hingga diperoleh barisan r1, r2, …
, atau dengan kata lain 
dinotasikan 
.
