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.
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 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 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...
Langkah Pertama, bentuk persamaan berikut.
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
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...