ALGORITMA EUCLIDEAN

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.
 Algoritma Euclidean
1. Jika n = 0 maka
m adalah PBB ( m, n ) ;
stop.
Tetapi jika n ≠ 0
Lanjutkan ke langkah kedua :
2. Bagilah m dengan n dan misalkan r adalah sisanya.
3. Ganti nilai m dengan nilai dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1.
Contoh : m = 80, n = 12 dan di penuhi syarat m ≥ n

m = n . q + r
80 = 12.6 + 8
12 = 8 . 1 + 4
8 = 4 . 2 + 0
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