Daftar isi
Pernahkah mendengar tentang algoritma Euclid? Istilah algoritma Euclid mungkin terasa asing bagi para pelajar yang masih di tingkat pendidikan menengah. Namun bagi mereka yang berkecimpung dengan olimpiade matematika atau bagi mereka yang sudah belajar matematika di perkuliahan tidak akan asing dengan algoritma ini.
Berbeda dengan algoritma Eculid, istilah FPB atau Faktor Persekutuan Terbesar pastinya sudah familiar di telinga kita. Ini karena sejak pendidikan SD kita sudah dikenalkan dengan FPB. Lalu apa ya kaitan antara algoritma Euclid dan FPB? Simak ulasan berikut.
Apa itu Algoritma Euclid?
Sebelum mengenal lebih jauh mengenai algoritma Euclid, kita pahami terlebih dahulu apa itu algoritma. Algoritma dapat diartikan sebagai sederetan alur atau prosedur untuk menyelesaian masalah tertentu.
Sedangkan algoritma Euclid sendiri merupakan sebuah prosedur yang digunakan untuk menentukan nilai FPB dari dua bilangan.
Algoritma ini dinamakan algoritma Euclid sesuai dengan nama pencetusnya yaitu Euclid. Euclid adalah seorang matematikawan terkenal dari Yunani. Euclid menuliskan algoritma Euclid secara lengkap dalam bukunya yang berjudul Elements.
Pembelajaran tentang algoritma Euclid biasanya ada di tingkat perkuliahan khususnya untuk mahasiswa program studi matematika. Dan dipelajari secara mendalam pada mata kuliah Teori Bilangan.
Kegunaan Algoritma Euclid untuk Menentukan FPB
Cara penentuan FPB yang popular adalah dengan menentukan bilangan terbesar dari semua faktor persekutuannya dari bilangan-bilangan tertentu. Jika berbicara mengenai faktor persekutuan tentunya berkaitan dengan bilangan prima.
Proses menentukan faktor persekutuan yang merupakan bilangan prima dikenal juga dengan nama faktorisasi prima. Untuk siswa tingkat SD kemudian akan diajarkan mengenai pohon faktor untuk mempermudah proses faktorisasi prima.
Tidak ada yang salah dengan proses faktorisasi prima untuk menentukan FPB, namun cara ini terbatas pada bilangan kecil saja. Ketika diperlukan untuk menentukan FPB dari bilangan yang besar maka cara faktorisasi prima tidak akan efektif.
Dan permasalahan ini terjawab dengan adanya algoritma Euclid. Algoritma Euclid menggunakan konsep modulo (sisa pembagian) dalam prosesnya.
Prosedur Algoritma Euclid
Prosedur dalam algoritma Euclid secara lengkap dituliskan sebagai berikut.
FPB (a,b) dengan a > b dan a, b merupakan bilangan bulat positif dapat ditentukan dengan melakukan pengulangan algoritma pembagian berikut:
a = q1.b + r1 0 < r1 < b
b = q2.r1 + r2 0 < r2 < r1
r1 = q3.r2 + r3 0 < r3 < r2
⁞ ⁞
rn-2 = qn.rn-1 + rn 0 < rn < rn-1
rn-1 = qn+1.rn + rn+1 rn+1 = 0 Proses pembagian tersebut diulangi hingga sisa hasil baginya 0, dan FPB(a,b) ditentukan dari sisa terakhir dari pembagian di atas yang bukan nol.
Misal akan ditentukan FPB dari 720 dan 246 menggunakan algoritma Euclid, maka algoritma pembagian untuk menentukan FPB adalah sebagai berikut:
720 = 2 x 246 + 228 iterasi 1
246 = 1 x 228 + 18 iterasi 2
228 = 12 x 18 + 12 iterasi 3
18 = 1 x 12 + 6 iterasi 4
12 = 2 x 6 + 0 iterasi 5
Algoritma pembagian selesai ketika iterasi ke-5 karena sisa pembagian mencapai 0, maka FPB(720, 246) yang dimaksud adalah sisa pembagian terakhir sebelum 0 yaitu 6 (pada iterasi ke-4).
Cara di atas merupakan alur penentuan FPB(720, 246) menggunakan algoritma Euclid. Berikut akan dibandingkan dengan cara menentukan bilangan pembaginya.
Bilangan pembagi 720 = 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720
Bilangan pembagi 246 = 1, 2, 3, 41
Bilangan pembagi 720 dan 246 = 1, 2, 3
Maka FPB dari 720 dan 246 adalah 1 x 2 x 3 = 6.
Dari perbandingan kedua cara di atas, algoritma Euclid terbukti lebih efektif untuk menentukan FPB dari bilangan yang besar.
Contoh Soal dan Pembahasan Algoritma Euclid
Agar lebih memahami proses penentuan FPB menggunakan algoritma Euclid maka perhatikan kembali pembahasan dari soal-soal berikut.
Contoh Soal 1
Tentukan FPB dari 615 dan 3579 menggunakan Algoritma Euclid
Pembahasan:
Berikut adalah alur algoritma pembagian untuk menentukan FPB(615, 3579)
3579 = 3 x 988 + 615 iterasi 1
988 = 1 x 615 + 373 iterasi 2
615 = 1 x 373 + 242 iterasi 3
373 = 1 x 242 + 131 iterasi 4
242 = 1 x 131 + 111 iterasi 5
131 = 1 x 111 + 20 iterasi 6
111 = 5 x 20 + 11 iterasi 7
20 = 1 x 11 + 9 iterasi 8
11 = 1 x 9 + 2 iterasi 9
9 = 4 x 2 + 1 iterasi 10
2 = 2 x 1 + 0 iterasi 11
Pada iterasi ke-11, sisa pembagian adalah 0, maka FPB dari 615 dan 3579 ditentukan dari sisa hasil bagi pada iterasi sebelumnya yaitu iterasi ke-10. Sisa pembagian pada iterasi ke-10 adalah 1. Jadi FPB(615, 3579) adalah 1.
Contoh Soal 2
Tentukan FPB dari 534 dan 10587 menggunakan Algoritma Euclid!
Pembahasan:
Berikut adalah alur algoritma pembagian untuk menentukan FPB(534, 10587)
10587 = 19 x 534 + 441 iterasi 1
534 = 1 x 441 + 93 iterasi 2
441 = 4 x 93 + 69 iterasi 3
93 = 1 x 69 + 24 iterasi 4
69 = 2 x 24 + 21 iterasi 5
24 = 1 x 21 + 3 iterasi 6
21 = 7 x 3 + 0 iterasi 7
Iterasi algoritma pembagian berhenti pada iterasi ke-7 karena sisa pembagian adalah 0. Maka FPB dari 534 dan 10587 adalah sisa pembagian pada iterasi ke-6 yaitu 3. Jadi, FPB(534, 10587) adalah 3.
Contoh Soal 3
Tentukan FPB dari 1677, 1157, dan 897 menggunakan Algoritma Euclid!
Pembahasan:
Penentuan FPB menggunakan algoritma Euclid hanya bisa digunakan untuk dua bilangan. Namun bukan berarti kita tidak bisa menggunakan algoritma Euclid ini untuk menentukan FPB. Cara penentuan FPB dari 3 bilangan adalah dengan memilih 2 dari 3 bilangan itu terlebih dahulu.
Misal dipilih terlebih dahulu bilangan 1677 dan 1157, maka iterasi algoritma pembagiannya adalah sebagai berikut.
1677 = 1 x 1157 + 520 iterasi 1
1157 = 2 x 520 + 117 iterasi 2
520 = 4 x 117 + 52 iterasi 3
117 = 2 x 52 + 13 iterasi 4
52 = 4 x 13 + 0 iterasi 5
Pada iterasi ke-5 sisa pembagian sama dengan 0, maka FPB(1677, 1157) adalah sisa pembagian pada iterasi ke-4 yaitu 13. Selanjutnya akan ditentukan FPB dari 897 dan 13 (FPB dari 1677 dan 1157). Algoritma pembagiannya sebagai berikut.
897 = 69 x 13 + 0 iterasi 1
Pada iterasi pertama sisa pembagian sudah sama dengan 0, maka FPB dari 897 dan 13 adalah 13. Jadi bisa disimpulkan bahwa FPB dari 1677, 1157, dan 897 adalah 13. Atau bisa dituliskan FPB(1677, 1157, 897) = 13.