Info Matematika: Algoritma Euclid dan FPB

Pernah ingat materi FPB? Pasti ingat donk, itu adalah salah satu materi yang ada di dalam matematika khususnya di tingkat Sekolah Dasar. Materi itu tentang mencari faktor persekutuan terbesar antara dua bilangan bulat ya. Kalau kita telaah lagi, mungkin cara yang sering kita gunakan adalah dengan menggunakan pohon faktor. Usut punya usut, ternyata matematikawan zaman dahulu itu juga punya suatu cara yang dapat digunakan untuk menyelesaikan masalah FPB, terlebih lagi kalau dua bilangan itu cukup besar, kita dapat menggunakan cara ini. Matematikawan yang dimaksud itu adalah Euclid.

Cara yang digunakan oleh Euclid tersebut dikenal dengan istilah Algoritma Euclid. Lalu bagaimana cara menggunakan algoritma Euclid tersebut?

Saya akan berikan penjelasan secara umumnya, namun jangan panik dulu ya, kkarena Saya juga akan memberikan gambaran singkatnya dengan contoh, jadi pembaca sekalian tidak akan begitu pusing melihatnya (Harapannya sih..).

Secara matematis, algoritma Euclid dijelaskan sebagai berikut.

Misalkan terdapat dua buah bilangan bulat yaitu a dan b yang akan dicari FPB-nya, serta dapat diasumsikan bahwa a ≥ b > 0.
Langkah Pertama, bentuk persamaan berikut.

di mana


Oke, maksudnya itu begini, misalkan akan dicari FPB dari 546 dan 320, maka kalau kita melihat bentuk umum yang di atas, maka dapat kita bentuk persamaan

546 = 1 . 320 + 226

Paham kan??
546 itu ya nilai a
320 kan nilai b
1 dan 226 darimana?? gampangnya begini, 546 dibagi 320 itu kan hasilnya 1 tetapi masih ada sisa, sisanya itu kan 226, ya ga??
Paham ya..

Langkah Kedua, jika bertemu kasus bahwa


maka berarti b membagi habis a sehingga FPB antara a dan b adalah b. Namun jika kasusnya adalah


dengan membentuk persamaan berikutnya yaitu

di mana

Kalau dilihat dari persamaan yang pertama, ternyata bilangan dibagian ujung itu kan bukan 0, tetapi 226, jadi berdasarkan penjelasan tersebut maka dibentuk lagi persamaan berikut.

320 = 1 . 226 + 94

Paham lagi donk?
320 itu kan b
226 itu n1 atau sisa yang pertama tadi
320 dibagi 226 kan hasilnya 1 tetapi masih ada sisa 94

Langkah Selanjutnya, melakukan seperti langkah dua hingga bertemu nilai 0 di bagian akhirnya.
226 = 2 . 94 + 38
lanjutkan..
94 = 2 . 38 + 18
lanjutkan..
38 = 2 . 18 + 2
Lanjutkan..
18 = 9 . 2 + 0
Karena bagian akhir sudah 0, maka  yang diambil adalah nilai n terakhir, yaitu 2.
Jadi FPB dari 546 dan 320 adalah 2.

Oke, sampai disini semoga jelas ya…
Semoga bermanfaat…

4 Replies to “Info Matematika: Algoritma Euclid dan FPB”

    1. Terima kasih , penjelasannya dapat membantu saya mempelajari ilmu matematika .
      Cukup efisien dan mudah untuk di ingat .
      Saya mencatat ringkasan materi sudah
      di ajarkan . Saya bisa paham .

Leave a Reply

Your email address will not be published. Required fields are marked *