RSS

Mencari FPB dengan Algoritma Euclides

25 Nov

FPB adalah istilah Matematika yang merupakan singkatan dari Faktor Persekutuan Terbesar, atau dalam Bahasa Inggris disebut GCD (Greatest Conmmon Divisor).
FPB dari dua bilangan adalah sebuah bilangan bulat positif terbesar yang dapat membagi kedua bilangan tersebut.
Misalkan terdapat 2 bilangan, 24 dan 32.
Bilangan yang dapat membagi 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24
Bilangan yang dapat membagi 32 adalah : 1, 2, 4, 8, 16, 32
1, 2, dan 4, ketiga bilangan ini dapat membagi 24 maupun 32, dan yang dimaksud dengan FPB dari 24 dan 32 adalah 4, karena merupakan bilangan terbesar dari bilangan-bilangan yang dapat membagi kedua bilangan itu.

Banyak metode yang dapat digunakan untuk mencari FPB. Di SD / SMP, metode yang umum digunakan ialah metode pagar dan metode pohon faktor. Metode pagar maupun metode pohon faktor efektif untuk bilangan-bilangan kecil. Jika bilangan yang dicari FPB-nya besar, maka lebih efektif menggunakan algoritma Euclid.

Algoritma Euclid merupakan algoritma yang digunakan untuk mencari FPB dari dua buah bilangan. Algoritma ini ditemukan oleh Euclid ahli matematika yunani yang tertulis pada bukunya Elements. Algoritma ini memanfaatkan sifat-sifat dari sisa pembagian atau modulo. Langkah-langkah algoritma Euclid adalah sebagai berikut.
Jika a, b elemen dari bilangan bulat, maka dengan menerapkan algoritma euclides, pembagian berkali-kali diperoleh :

 

 

 

 

 

 

 

 

 

Contoh:

1. Tentukan FPB(9.800, 180)

Jawab:

9800 = 180*54+80

180   = 80*2+20

80     = 20*4

Jadi FPB(9.800, 180) = 20

2. Tentukan FPB(10.587, 534)

Jawab:

10.587 = 534*19+441

534     = 441*1+93

441     = 93*4+69

93       = 69*1+24

69       = 24*2+21

24       = 21*1+3

21       = 3*7

Jadi FPB(10587, 534) = 3

Sebagai latihan tentukan FPB dari pasangan bilangan berikut :

  1. 6.409 dan 3.536
  2. 1.587.645 dan 6.755
  3. 12.345 dan 9.999

Tentang Greatest Common Divisor dan Euclidean Algorithm di Wikipedia, silahkan klik disini.

Siapakah Euclides? Silahkan klik disini.

 
Leave a comment

Posted by on November 25, 2012 in Amazing Math

 

Tags: , , ,

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

 
%d bloggers like this: