Greatest Common Divisor

Greatest Common Divisor atau sering disingkat GCD adalah operasi yang sering digunakan dalam manipulasi bilangan bulat (bilangan yang tidak memiliki angka dibelakang koma, bukan tergolong bilangan riil) dan banyak digunakan dalam banyak operasi terapan misalnya dalam ilmu kriptografi dan hash table. GCD atau juga dikenal sebagai FPB (Faktor Persekutuan terBesar), mencari nilai factor pembagi bersama yang paling besar dari dua nilai masukkan.
Misalnya :
GCD(80, 12)
*Faktor pembagi dari 80 adalah 1, 2, 4, 5, 8, 10, 16, 20, 40 dan 80 itu sendiri
*Faktor pembagi dari 12 adalah 1, 2, 3, 4, 6 dan 12 itu sendiri
*Faktor pembagi bersama untuk nilai 80 dan 12 adalah 1, 2 dan 4
*dari faktor pembagi bersama tersebut yang terbesarnya adalah 4, jadi GCD(80, 12) = 4

Ada cara lain untuk mencari nilai GCD, selain dengan cara mencari masing-masing faktor pembagi dan kemudian menentukan factor pembagi bersamanya dan mengambil nilai yang terbesar, yaitu dengan menggunakan algoritma Euclidean, namun sebaiknya kita harus mengerti terlebih dahulu konsep tentang Pembagian Bilangan Bulat. Namun sebelumnya berikut definisi untuk GCD dengan pola pembagian bilangan bulat

DEF: 2.0
Misalkan m dan n adalah bilangan bulat dengan syarat n lebih dari nol, sedemikian sehingga
m = nq + r, 0 <= r < n
maka GCD(m, n) = GCD(n, r)

Contohnya GCD(80, 12) memberikan urutan penyelesaian sebagai berikut :
* GCD(80, 12) : 80 div 12 menghasilkan hasil bagi 6 dan sisa 8 => 80 = 12*6 + 8
* GCD(12, 8) : 12 div 8 menghasilkan hasil bagi 1 dan sisa 4 => 12 = 8*1 + 4
* GCD(8, 4) : 8 div 4 menghasilkan hasil bagi 2 dan sisa 0 => 8 = 4*2 + 0
* karena 4 habis membagi 8 (4 | 8) maka tentunya sisa bagi sama dengan nol dan GCD ditemukan yaitu dengan nilai 4

Algoritma Euclidean yang ditemukan oleh mbah Euclid (Ilmuan Yunani yang lahir tahun 350 sebelum Masehi) ini didasarkan pada DEF:2.0 dan berikut definisinya : misalkan m dan n adalah bilangan bulat tak negatif dengan syarat m lebih dari atau sama dengan n, misalkan r0 = m dan r1 = n, lakukan secara terus-menerus, selama sisa pembagian tidak bernilai nol.
NOTE : {…} → kurung kurawal menandakan subscript
r{0} = r{1}*q{1} + r{2}, 0<=r{2}<=r{1}
r{1} = r{2}*q{2} + r{3}, 0<=r{3}<=r{2}
…...
r{n-2} = r{n-1}*q{n-1} + r{n}, 0<=r{n}<=r{n-1}
r{n-1} = r{n}*q{n} + 0

atau sesuai DEF:2.0 berbentuk :
GCD(m, n) = GCD(r0, r1) = GCD(r1, r2) = … = GCD(r{n-2}, r{n-1}) =
GCD(r{n-1}, r{n}) = GCD(r{n}, 0) = r{n}
Jadi GCD (m, n) adalah sisa terakhir yang tidak bernilai nol (r{n}) dari runtunan pembagian tersebut.

Algoritma Euclidean dapat dijelaskan dengan algoritma abstrak berikut ini.
1) Selama n tidak sama dengan 0 lakukan langkah 2 dan langkah 3, namun jika sama dengan nol maka langsung kerjakan langkah 4;
2) Ambil sisa dari pembagian m dengan nilai n, dan simpan di r;
3) Ganti nilai m lama dengan n lama dan ganti nilai n yang lama dengan r (sisa bagi), kemudian kerjakan lagi langkah 2;
4) Pada langkah ini nilai m adalah GCD-nya asalkan nilai n sudah bernilai 0.

dan untuk fungsi terapannya dalam bahasa C adalah sebagai berikut.

# include

int gcd (int m, int n)
{
int r;
while (n > 0) {
r = m % n;
m = n;
n = r;
}
return m;
}

int main (void)
{
int A, B, M;
A = 45;
B = 36;
fprintf(stdout,"\nInt_gcd = %d ; M=%d\n", ( M=gcd(A, B) ), M );
return 0;
}
sumber  Zoe Daemon