GREATEST COMMON DIVISOR (GCD)

Greatest Common Divisor (GCD)
Pembagi dari 12 adalah 1, 2,3,4,6, dan 12. Pembagi dari 18 adalah 1, 2, 3,
6, 9 dan 18. Maka (1,2,3,6) adalah himpunan pembagi umum dari 12 dan 18.
Asumsikan bahwa a dan b adalah dua buah bilangan bulat tidak 0. Pembagi
bersama terbesar (Greatest Common Divisor) dari a dan b adalah bilangan bulat
terbesar d sedemikian sehingga d a dan d b. Dalam hal ini kita nyatakan bahwa
GCD (a,b) = d.

*Teorema Algoritma Pembagi
Diberikan bilangan bulat tidak negatif a dan b dengan a > b > 0 maka
GCD (a,b) dapat dicari dengan mengulang algoritma pembagi.
a = q1 – b+r, dengan 0 < r1 < b
b = q2 – r1+r2, dengan 0 < r2 < r1
r1 = q3 . r2+r3, dengan 0 < r3 < r2
rn-2 = qn . rn-1+rn, dengan 0 < rn < rn-1
rn-1 = qn+1 . rn+0
Maka rn sisa terakhir dari pembagian diatas yang bukan 0 (nol) merupakan
GCD (a,b). Contoh :
1) GCD (80,12) : 80 > 12 > 0
80 = 6 × 12 + 8
12 = 1 × 8 + 4
8 = 2 × 4 + 0
GCD = 4
2) GCD (4.840, 1.512) : 4.840 > 1.512 > 0
4.840 = 3 × 1.512 + 304
1.512 = 4 × 304 + 296
304 = 1 × 296 + 8
296 = 37 × 8 + 0
GCD = 8

Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relatif prima jika GCD (a,b) =
1. Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian
sehingga
 m x a + n x b = 1
Contoh :
1) GCD (20, 3) : 20 = 6 × 3 + 2
3 = 1 × 2 + 1
2 = 2 × 1 + 0
GCD = 1
2 × 20 + (-13) × 3 = 1
m = 2 n = -13
Bilangan 20 dan 3 adalah relatif prima karena GCD (20,3) = 1.
2) GCD (5, 11) : 11 = 2 × 5 + 1
5 = 5 × 1 + 0
GCD = 1
-2 × 5 + 1 × 11 = 1
m = -2 n = 1
Bilangan 5 dan 11 adalah relatif prima karena GCD (5,11) = 1.

SUMBER : BU WINDIA HADI M.Pd

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA

MATAKULIAH : TEORI BILANGAN