Algoritma Euclidean

Algoritma Euclidean merupakan salah satu algoritma yang ditemukan oleh seorang matematikawan Yunani bernama Euclid untuk mencari FPB dari dua buah bilangan bulat.

Misalkan a dan b adalah bilangan bulat tak negatif dengan a ≥ b maka proses Algoritma Euclidean adalah sebagai berikut.

a = b.q1 + r1 , 0 ≤ r1 ≤ b
b = r1.q2 + r2 , 0 ≤ r2 ≤ r1

r1 = r2.q3 + r3 , 0 ≤ r3 ≤ r2
r2 = r3.q4 + r4 , 0 ≤ r4 ≤ r3
...
...

rn-2 = rn-1.qn + rn , 0 ≤ rn ≤ rn-1
rn-1 = rn.qn+1 + 0                    -----> sudah tidak bersisa (sisa 0)

Maka diperoleh FPB(a,b) = rn

Keterangan:
q = hasil bagi (quotient)
r = sisa pembagian (remainder)

Contoh

Carilah FPB dari 175 dan 245 !

245 = 175 . 1 + 70
175 = 70 . 2 + 35
70   = 35 . 2                -----> tidak bersisa
FPB(175 , 245) = 35

Jadi, FPB dari 175 dan 245 adalah 35.

Contoh

Tentukan FPB dari 437 dan 621 !

621 = 437 . 1 + 184
437 = 184 . 2 + 69
184 = 69 . 2 + 46
69   = 46 . 1 + 23
46   = 23 . 2               -----> tidak bersisa
FPB(437 , 621) = 23

Jadi, FPB dari 437 dan 621 adalah 23.

Contoh

Berapakah FPB dari 3087 dan 6958 ?

6958 = 3087 . 2 + 784
3087 = 784 . 3 + 735
784   = 735 . 1 + 49
735   = 49 . 15                 -----> tidak bersisa
FPB(3087 , 6958) = 49

Jadi, FPB dari 3087 dan 6958 adalah 49.

Bisa ditarik kesimpulan, Algoritma Euclidean sangat berguna untuk mencari FPB dari dua bilangan bulat terutama bilangan yang besar (ribuan, puluh ribuan, dsb).

Soal latihannya ada di sini.

Semoga bermanfaat. :-)