Algoritma Euclidean untuk mencari PBB

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

Advertisements
Algoritma Euclidean untuk mencari PBB

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s