Teori bilangan

Faktor Persekutuan Terbesar ( Greastet Common Divisor )

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

Contoh soal :

Teorema 

1. Tentukan GCD dari (80,12)!

Jawab : GCD dari (80,12) =

             80  = 6 . 12 + 8

             12  = 1. 8 + 4

              8   = 2. 4 + 0

maka GCD (80,12) = 4

2. Tentukan GCD dari (4840,1512)!

Jawab : GCD dari (4840, 1512) =

             4840  =  3. 1512 + 304

             1512  =  4. 304 +  296

               304 = 1 . 296 + 8 

               296 = 37. 8 + 0

maka GCD dari (4840, 1512) = 8

3. Tentukan GCD dari (738, 621)!

Jawab : GCD dari (738, 621)

             738 = 1. 621 + 117

             621 = 5. 117 + 36

             117 = 3.   36 + 9 

               36 = 4. 9 + 0

maka GCD dari (738 , 621) = 9

sumber : catatan mata kuliah teori bilangan