|
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, …
Karena a dan b berhingga, maka tentu akan ada n sehingga rn=0. Dengan demikiangcd(a,b)=gcd(b,r)=gcd(r,r1)=…=gcd(rn-1,rn)=gcd(rn-1,0)=rn-1
Untuk contoh 4 dan 6, karena a>b diambil a=6 dan b=4 (gcd(a,b)=gcd(b,a))
Sehingga 6=4q+r, diperoleh q=1 dan r=2, karena r=2≠0 maka dilakukan langkah yang sama yaitu 4=2q1+r1, diperoleh q1=2 dan r1=0 karena r1=0 maka gcd(6,4)=gcd(4,2)=gcd(2,0)=2.
Kelipatan Persekutuan Terkecil (KPK) dari dua bilangan adalah bilangan bulat positif terkecil yang dapat dibagi habis oleh kedua bilangan itu. KPK juga telah dikenalkan pada saat Sekolah Dasar dan cara untuk mencarinya juga dengan menggunakan faktorisasi prima. KPK dari dua bilangan a dan b dapat ditulis [a,b].
Sebagai contoh 4 dan 6
4=22
6=2.3
Sehingga didapat KPK dari 4 dan 6 adalah [4,6]=22.3=12 (diambil factor yang berbeda dan factor yang sama dengan pangkat tertinggi). Apabila dicari KPK dari dua bilangan yang cukup besar tentu sulit apabila menggunakan faktorisasi prima.
Ada sebuah teorema yang mengatakan bahwa
Jika a dan b adalah bilangan bulat yang tidak keduanya nol, maka
[a,b]=ab/gcd(a,b)
Sebagai contoh a=4 dan b=6, karena gcd(4,6)=gcd(6,4)=2, maka diperoleh [4,6]=4.6/2=12.
Selanjutnya apabila dibuat program dalam bahasa pascal adalah sebagai berikut.
Dan untuk beberapa input, hasilnya adalah sebagai berikut.
Atau dalam format txt dapat diunduh di sini.
