8
L Faktorkan a dan
b
atas
bilang:L'1-bilangan
prima
dan
lihat faktor-nya
yang
sama
dan
ambil yang memiliki
pangkat
terkecil.
Contoh
:
1728
=
²
632
127008
=
2
534
7²
135
=
3³
5
; gcd (1728, l35)
=
3² =
9
3500 = 22537
;
gcd
(127008,3500)
=
2² 7 =
28
2. Jika bilangan
-
bilangan yang diproses 5&'1gat
besar, tidaklab mudab untuk
menghitung
dengan
cara seperti
no.!
di
atas.
Oleb
sebab
itu
digunakan
algoritma Eudide.
Aigoritma Euclid
:
a
=
q1b
+ r1
b
=
q2r1
+
r2
r1
=
q3r2
+ r3
rk-2
=
qkfk-1
+ rk
rk-1
=
qk
+ 1rk
Sehingga mer,ghasilkan
kesimpulan gcd
(a,b) =
r,
Contoh:
1180
=
2
X
482 + 216
482
-
2x2!6+50
216
4x50+16
50
--
3
X
16 +
2
16
8x2+0
sehingga ged ( 482,1180
)
=
2
 |