ALGORITMA EUCLID

Algoritma Euclid merupakan suatu algoritma yang digunakan untuk mencari FPB dari dua bilangan. Salah satu kelebihan dari cara ini adalah tidak perlu mencari faktor prima dari kedua bilangan tersebut, hal ini tentu akan sangat membantu terutama saat mencari FPB dari bilangan-bilangan yang sangat besar.

So, Let’s take a look!

Secara ringkas, caranya adalah dengan membagi bilangan yang lebih besar (misalkan a) dengan bilangan yang lebih kecil (b), pembagian tersebut akan menghasilkan hasil bagi q1 dan sisa r1. Jika r = 0, maka FPB nya adalah b. Tetapi bila r tidak sama dengan 0, maka prosesnya diulang lagi dengan membagi b dengan r1. Pembagian tersebut akan menghasilkan hasil bagi q2 dan sisa r2. Jika r2 = 0, maka FPB nya adalah r1 (sisa pembagian sebelumnya), jika r2 bukan 0, maka lakukan pembagian r1 dengan r2.

a : b = q1 + r1 –> a = q1(b) + r1

b : r1 = q2 + r2 –> b = q2(r1) + r2

r1 : r2 = q3 + r3 –> r1 = q3(r2) + r3

. .

. .

. .

Demikian seterusnya hingga didapatkan sisa pembagian 0 dan FPB nya adalah sisa pembagian sebelumnya.

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

Algoritma Euclid ini dapat digunakan untuk menyelesaikan Persamaan Linear Diophantine yang akan dibahas pada postingan lain. 
Untuk berlatih, cobalah gunakan algoritma euclid untuk mencari FPB dari 6105 dan 3443! Cari pula FPB dari 1557 dan 1211! Selamat mencoba!!!have fun...