Euclidean Algoritma

A.Pengertian Euclidean Algoritma

Oleh

Rinaldi

FAKULTAS TEKNOLOGI & INFORMASI KOMPUTER

UNIVERSITAS PRIMA INDONESIA

Algoritma Euclidean adalah salah satu metode yang mangkus dalam mencari Pembagi Bersar Terbesar (greates), disingkat menjadi PBB. Algoritma ini sudah dikenal sejak berabad-abad yang lalu. Euclid, penemu Algoritma Euclidean, adalah seorang matematikawan yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkanal yang berjudul Element. Secara formal algoritma Euclidean dirumuskan sebagai berikut.

Misalkan m dan n adalah bilangan bulat tak negatif dengan m ≥ n. Misalkan r0 = m dan r1 = n , lakukan secara berturut –turut pembagian seperti dibawah ini.

                                                        r0 = r1q1 + r2 0≤ r2 ≤ r1
                                                        r1 = r2q2 + r3 0≤ r3 ≤ r2

Kemudian PBB dari m dan n (PBB(m,n)) adalah sisa terakhir dari pembagian tersebut. Singkatnya algoritma Euclidean akan dituliskan sebagai berikut :
Algoritma Euclidean
1.Jika n = 0 maka m adalah PBB(m,n); stop tetapi jika n ≠ 0 ,lanjutkan ke langkah 2.
2.Bagilah m dengan n dan misalkan r adalah sisanya.
3.Gantilah nilai m dengan nilai n dan nilai n dengan r, lalu ulang kembali ke langkah 1. Catatan : jika m ≤  ` n, maka pertukarkan nilai m dan n.

B.Contoh Soal dan Pembahasannya

Contoh 1:

Tentukan FPB dari 53 dan 7!

Pembahasan:

Bagi 53 dengan 7 –> 53 = 7(7) + 4

Bagi 7 dengan 4 –> 7 = 1(4) +3

Bagi 4 dengan 3 –> 4 = 1(3) +1

Bagi 3 dengan 1 –> 3 = 1(3) + 0 (Karena sisanya sudah 0,maka FPB-nya adalah sisa sebelumnya)

Jadi, FPB(53, 7) = 1

Contoh 2:

Tentukan FPB dari 1398 dan 2058!

Pembahasan:

2058 = 1(1398) + 660

1398 = 2(660) + 78

660 = 8(78) + 36

78 = 2(36) + 6

36 = 6(6) + 0

Jadi, FPB(1398, 2058) = 6

Contoh 3:

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 4:

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.

Sumber: 

• https://aveninataliapanjaitan.wordpress.com/2015/06/03/tugas-matematika-diskrit-algoritma-euclidean/
• http://cheesterzone.blogspot.co.id/2011/09/algoritma-euclidean.html