F-Crown

ALGORITMA EUCLIDEAN
menurut forumbeck Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat. Euclid, penemu algoritma euclidean adalah seorang matematikawan Yunani yang menuliskan Algoritmanya tersebut dalam bukunya yang terkenal “ Element “.
Diberikan dua buah bilangan bulat tak negatif m dan n ( m ≥ n ). Algoritma Euclidean berikut mencari pembagi bersama terbesar dari m dan n.
Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB ( 80, 12) 4.
Teorema 1 ( teorema euclidean ) misalnya m dan n adalah dua buah bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka terdapat dua buah bilangan bulat unik q ( quotient ) dan r ( remainder ), sedemikian sehingga :
m = n . q + r
dengan 0 ≤ r ≤ n
contoh : ( i ) 1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47.
1987 = 97 . 20 + 47
( ii ) – 22 dibagi dengan 3 memberikan hasil bagi – 8 dan sisa 2 :
-22 = 3 ( – 8 ) + 2
Tetapi – 22 = 3 ( – 7 ) – 1 salah, karena r = – 1 tidak memenuhi syarat
0 ≤ r ≤ n.
Pembagi Bersama Terbesar ( PBB )
Misalkan a dan b adalah dua buah bilangan bulat tidak nol pembagi bersama terbesar ( PBB – Greatest Common Divisor atau GCD ) dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini kita nyatakan bahwa PBB ( a, b ) = d.
Contoh :
Faktor Pembagi 45 : 1, 3, 5, 9, 15, 45
Faktor Pembagi 36 : 1, 2, 3, 4, 9, 12, 18, 36
Faktor Pembagi bersama dari 45 dan 36 PBB ( 45, 36 ) = 9