Materi, Soal, dan Pembahasan – Algoritma Euclides

Algoritma Euclides

Setiap bilangan bulat positif memiliki faktor (pembagi). Misalnya, 8 memiliki faktor 1,2,4, dan dirinya sendiri, yaitu 8. Keempat bilangan ini disebut faktor dari 8 karena membagi habis 8 tanpa sisa. Setelah itu, kita telah dikenalkan dengan faktor persekutuan terbesar (FPB), atau dalam bahasa Inggris, greatest common divisor (GCD), yaitu bilangan terbesar yang menjadi faktor bersama dari dua atau lebih bilangan yang lain. Sebagai contoh, FPB 12 dan 16, ditulis FPB(12,16) adalah 4. Kita tentu sudah diajarkan cara mencari FPB saat masih berada di sekolah dasar. Ada yang menggunakan pohon faktor, ada juga yang menggunakan cara pagar (tabel), dan lain-lain.

Metode Pagar
Metode Pagar

 

Metode Pohon Faktor
Metode Pohon Faktor

Sayangnya, cara-cara ini akan kurang efisien bila kita mencari FPB yang melibatkan bilangan-bilangan besar, mengingat sekolah dasar masih menitikberatkan pada pengenalan dan manipulasi bilangan yang nilainya kecil.

Ada satu teorema dalam ranah teori bilangan yang cukup efisien digunakan untuk mencari FPB bilangan-bilangan besar. Namanya algoritma Euclides. Pencetusnya jelas, Euclid, matematikawan legendaris berkebangsaan Yunani. Ia menuliskan teorema ini di buku maha karyanya, Elements. Algoritma diartikan sebagai langkah/prosedur sistematis untuk menyelesaikan suatu permasalahan.

Euclid
Euclid

Quote by Jean Piaget

Tujuan utama pendidikan di sekolah haruslah menciptakan anak yang mampu melahirkan hal-hal positif yang baru, tidak sekadar mengulangi apa yang telah dilakukan oleh generasi sebelumnya.

Algoritma Euclides mungkin tidak ditemui pada pembelajaran di kelas sekolah menengah, tetapi sering dimunculkan sebagai solusi untuk menyelesaikan soal-soal olimpiade matematika. Selain itu, mahasiswa yang berkecimpung dalam program studi matematika juga akan menemuinya saat mata kuliah Teori Bilangan (atau mungkin mata kuliah lainnya).

Teorema: Algoritma Euclides

Diberikan dua bilangan bulat positif a dan b dengan a>b. FPB(a,b) dapat ditentukan dengan melakukan iterasi (iteration) algoritma pembagian seperti berikut.
a=q1b+r1,0<r1<bb=q2r1+r2,0<r2<r1r1=q3r2+r3,0<r3<r2rn3=qn1rn2+rn1,0<rn1<rn2rn2=qnrn1+rn,0<rn<rn1rn1=qn+1rn+rn+1,rn+1=0Proses dilakukan sampai sisa hasil baginya 0 dan algoritma dihentikan. Nilai rn, yaitu sisa terakhir dari pembagian di atas yang bukan nol merupakan FPB(a,b).


Sebelum membuktikan algoritma Euclides, perlu kita buktikan lema berikut terlebih dahulu.

Lema: Jika a,b,q,rZ dengan a=bq+r, maka FPB(a,b)=FPB(b,r).

Bukti

Bukti Algoritma Euclides
Algoritma berhenti ketika diperoleh suatu rn+1=0. Hal ini dikarenakan sisa suatu pembagian terkecil yang mungkin adalah 0 serta fakta bahwa
r1>r2>>rn1>rn>rn+1=0.Dengan menggunakan lema yang telah dibuktikan di atas bahwa
FPB(a,b)=FPB(r0,r1)=FPB(r1,r2)==FPB(rn1,rn)=FPB(rn,0)=rn,disimpulkan bahwa algoritma Euclides terbukti. ◼


Pada awalnya, pendekatan geometris dipakai Euclid untuk mencari FPB dua buah bilangan seperti tampak pada gambar berikut.

Algoritme Euclid Secara Geometris
Algoritma Euclides Secara Geometris

Jarak satu titik ke titik lain mewakili bilangan yang dimaksud. Misalkan akan dicari FPB dari panjang AB dan CD. Karena CD lebih pendek dari AB, CD dipakai untuk mengukur AB, tetapi cukup sekali saja karena sisanya, EA lebih pendek dari DC. Selanjutnya, EA dipakai untuk mengukur DC, ternyata butuh dua kali (ditandai dengan warna merah), dengan sisa FC. Terakhir, FC dipakai untuk mengukur EA dan tepat 4 kali pengukuran tanpa menghasilkan sisa panjang (ditandai dengan warna biru). Dengan kata lain, EA=4FC. Disimpulkan bahwa FC merupakan FPB yang kita cari.

Baca: Materi, Soal, dan Pembahasan – Teorema Sisa Cina

FPB dari tiga bilangan atau lebih dapat dicari dengan mengalikan faktor-faktor prima bersama dengan pangkat terkecil dari bilangan-bilangan itu. Misalnya, karena
18=2×3224=23×336=22×32,
haruslah FPB(18,24,36)=2×3=6.
Selain itu, FPB dari tiga atau lebih bilangan bisa dicari dengan mencari FPB masing-masing pasangan dua bilangan yang ada, yaitu
FPB(18,24,36)=FPB(18,FPB(24,36))=FPB(FPB(18,24),36)=FPB(FPB(18,36),24).
Ini menunjukkan bahwa algoritma Euclides tetap dapat dipakai untuk mencari FPB dari tiga atau lebih bilangan dengan cara melakukan pengelompokkan dua bilangan seperti contoh di atas.


Bagaimana dengan kelipatan persekutuan terkecil (KPK)? Apakah algoritma Euclides dapat dipakai untuk mencari KPK? Nah, jika FPB dari dua bilangan telah ditemukan, maka kita dapat mencari KPK dengan menggunakan FPB. Misalkan diberikan dua bilangan bulat a dan b dengan FPB(a,b)=p. KPK dari a dan b sama dengan hasil kali a dan b dibagi dengan nilai FPB-nya, ditulis KPK(a,b)=a×bFPB(a,b).


Contoh 1:

Kita akan mencari FPB dari 12 dan 16 menggunakan algoritma Euclides.
16=112+4(Iterasi ke-1)12=34+0(Iterasi ke-2)Karena pada iterasi ke-2 sisa hasil baginya 0, FPB dari 12 dan 16 adalah 4, yang merupakan sisa hasil bagi pada iterasi ke-1.
Dari contoh di atas, algoritma Euclides hanya melibatkan beberapa kali iterasi untuk menemukan FPB. Ini dikarenakan nilai bilangan yang terlibat masih tergolong kecil.


Contoh 2:

Kita akan mencari FPB dari 18 dan 63 menggunakan algoritma Euclides.
63=318+9(Iterasi ke-1)18=29+0(Iterasi ke-2)Karena pada iterasi ke-2 sisa hasil baginya 0, FPB dari 18 dan 63 adalah 9, yang merupakan sisa hasil bagi pada iterasi ke-1.
Masih dua iterasi saja, ya, untuk contoh di atas.


Contoh 3:

Kita akan mencari FPB dari 52 dan 124 menggunakan algoritma Euclides.
124=252+20(Iterasi ke-1)52=220+12(Iterasi ke-2)20=112+8(Iterasi ke-3)12=18+4(Iterasi ke-4)8=24+0(Iterasi ke-5)Karena pada iterasi ke-5, sisa hasil baginya 0, FPB dari 52 dan 124 adalah 4, yang merupakan sisa hasil bagi pada iterasi ke-4.
Waduyy! Sudah 5 iterasi, ya, padahal bilangannya baru ratusan.


Contoh 4:

Kita akan mencari FPB dari 321 dan 843 menggunakan algoritma Euclides.
843=2321+201(Iterasi ke-1)321=1201+120(Iterasi ke-2)201=1120+81(Iterasi ke-3)120=181+39(Iterasi ke-4)81=239+3(Iterasi ke-5)39=133+0(Iterasi ke-6)Karena pada iterasi ke-6, sisa hasil baginya 0, FPB dari 321 dan 843 adalah 3, yang merupakan sisa hasil bagi pada iterasi ke-5.


Contoh 5:

Kita akan mencari FPB dari 3.579 dan 4.567 menggunakan algoritma Euclides.
4.567=13.579+988(Iterasi ke-1)3.579=3988+615(Iterasi ke-2)988=1615+373(Iterasi ke-3)615=1373+242(Iterasi ke-4)373=1242+131(Iterasi ke-5)242=1131+111(Iterasi ke-6)131=1111+20(Iterasi ke-7)111=520+11(Iterasi ke-8)20=111+9(Iterasi ke-9)11=19+2(Iterasi ke-10)9=42+1(Iterasi ke-11)2=21+0(Iterasi ke-12)Karena pada iterasi ke-12, sisa hasil baginya 0, FPB dari 3.579 dan 4.567 adalah 1, yang merupakan sisa hasil bagi pada iterasi ke-11. Kita sebut 3.579 dan 4.567 relatif prima karena memiliki FPB 1.


Contoh 6

Kita akan mencari FPB dari 897, 1.157, dan 1.677 menggunakan algoritma Euclides.
Mengingat bahwa algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, maka kita harus memilih 2 dari 3 bilangan tersebut untuk dicari FPB-nya terlebih dahulu.
Misalkan di sini kita memilih bilangan 1.157 dan 1.677. Akan dicari FPB(1.157,1.677) menggunakan algoritma Euclides.
1.677=11.157+520(Iterasi ke-1)1.157=2520+117(Iterasi ke-2)520=4117+52(Iterasi ke-3)117=252+13(Iterasi ke-4)52=413+0(Iterasi ke-5)Karena pada iterasi ke-5, sisa hasil baginya 0,, FPB dari 1.157 dan 1.677 adalah 13, yang merupakan sisa hasil bagi pada iterasi ke-4.
Langkah selanjutnya adalah mencari
FPB(897,FPB(1.157,1.677)) =FPB(897,13), yaitu

897=6913+0(Iterasi ke-1)Karena sisa hasil baginya 0 pada iterasi pertama, FPB(897,13)=13.
Jadi, kita simpulkan bahwa FPB dari 897, 1.157, dan 1.677 adalah 13


Contoh 7:

Kita akan mencari FPB dari 1.058, 1.564, dan 2.323 menggunakan algoritma Euclides.
Karena algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, kita harus memilih 2 dari 3 bilangan tersebut untuk dicari FPB-nya terlebih dahulu.
Misalkan kita memilih bilangan 1.564 dan 2.323. Akan dicari FPB(1.564,2.323) menggunakan algoritma Euclides.
2.323=11.564+759(Iterasi ke-1)1.564=2759+46(Iterasi ke-2)759=1646+23(Iterasi ke-3)46=223+0(Iterasi ke-4)Karena pada iterasi ke-4, sisa hasil baginya 0, FPB dari 1.564 dan 2.323 adalah 23, yang merupakan sisa hasil bagi pada iterasi ke-3.
Langkah selanjutnya adalah mencari
FPB(1.058,FPB(1.564,2.323)) =FPB(1.058,23), yaitu

1.058=4623+0(Iterasi ke-1)Karena sisa hasil baginya 0 pada iterasi pertama, FPB(1.058,23)=23.
Jadi, kita simpulkan bahwa FPB dari 1.058, 1.564, dan 2.323 adalah 23


Contoh 8:

Kita akan mencari FPB dari 1.015, 2.001, 2.871, dan 3.915 menggunakan algoritma Euclides.
Karena algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, kita harus membentuk pasangan dua bilangan untuk dicari FPB-nya terlebih dahulu.
Pertama, misalkan kita memilih bilangan 1.015 dan 2.001. Akan dicari FPB(1.015,2.001) menggunakan algoritma Euclides.
2.001=11.015+986(Iterasi ke-1)1.015=1986+29(Iterasi ke-2)986=3429+0(Iterasi ke-3)Karena pada iterasi ke-3, sisa hasil baginya 0, FPB dari 1.015 dan 2.001 adalah 29, yang merupakan sisa hasil bagi pada iterasi ke-2.
Setelah itu, cari FPB(29,2.871,3.915). Dapat diperiksa bahwa 2.871 dan 3.915 habis dibagi 29. Oleh karena itu, dapat kita simpulkan bahwa FPB(29,2.871,3.915)=29, mengimplikasikan bahwa FPB(1.015,2.001,2.871,3.915)=29

Baca: Materi, Soal, dan Pembahasan – Kongruensi Modulo

Di sini kita seharusnya menyadari bahwa bagian yang “sulit” dalam algoritma Euclides adalah membuat kombinasi dua bilangan untuk dikalikan, lalu dijumlahkan dengan bilangan lain. Contohnya, 124 sama dengan 52 dikali berapa, lalu ditambah berapa. Ya, jawabannya 52 dikali 2, hasilnya 104, lalu ditambah 20, supaya hasilnya jadi 124. Cara tebak-tebak seperti ini sebenarnya sudah diterapkan saat kita menggunakan pembagian bersusun.

Teorema ini selanjutnya dipakai sebagai dasar untuk mengenal identitas Bézout dan menyelesaikan persamaan Diophantine. Kedua materi tersebut akan dibahas pada pos terpisah.

Baca: Materi, Soal, dan Pembahasan – Persamaan Diophantine