GREATEST COMMON DIVISOR

GCD atau faktor persekutuan terbesar dari a dan b adalah bilangan bulat yang memenuhi d|a dan d|b. Nilai terbesar d disebut faktor persekutuan terbesar (GCD) dari a dan b ditulis GCD(a,b)= d

A. TEOREMA ALGORITMA PEMBAGI

Diberikan bilangan bulat a dan b dengan a>b>0 maka GCD (a,b) dapat dicari dengan mengulang algoritma pembagi

B. RELATIF PRIMA

Dua buah bilangan bulat a dan b dikatakan relatif prima jika GCD(a,b)=1 maka terdapat bilangan bulat m dan n sehingga sedemikian sehingga m.a + n.b = 1

Contoh 1 :

• GCD (10,12)...
• GCD (12,15)...
• GCD (16,20)...

Jawaban :

Contoh 2 :

• GCD (80,12)...
• GCD (4840,1512)...

Jawaban :

Contoh 3:

• GCD (5314, 2512)dan apakah relatif prima ?
• GCD (112378,3054) dan apakah relatif prima ?

Jawaban : 

SUMBER :  BU WIINDIA HADI M.Pd
DOSEN UNIVERSITAS PROF DR.HAMKA