Penjelasan Algoritma Euclidean untuk GCD

Motivasi

Setiap orang yang pernah belajar untuk OSK/OSP komputer kemungkinan besar mengenal fungsi berikut:

Fungsi yang pendek ini adalah Algoritma Euclidean untuk mencari GCD. Entah mengapa cukup dengan operasi modulo, tiba-tiba didapatkan GCD dari dua bilangan. Padahal jika kita mencari GCD menurut cara anak SD, diperlukan faktorisasi bilangan terlebih dahulu. Bagaimana sebenarnya fungsi ini bekerja?

Ada pembuktian matematis mengapa algoritma ini benar. Sayangnya pembuktian ini bisa jadi sulit dicerna bagi beberapa orang. Ada pendekatan lain untuk memahami bagaimana fungsi ini bekerja, dan akan saya jelaskan pada tulisan ini.

GCD = Memotong Kue

Kita ganti persoalan GCD(a, b) sebagai berikut:
Diberikan kue berbentuk persegi panjang, dengan panjang a dan lebar b. Kue ini hendak dipotong menjadi sejumlah persegi. Tidak boleh ada potongan yang tidak persegi. Tentukan sisi persegi terbesar yang mungkin digunakan!

Sebagai contoh, jika a=30 dan b=21, maka jawabannya adalah 3. Gambar berikut menunjukkan cara pemotongannya:

Jawaban dari masalah ini sama saja dengan GCD(a, b). Sebab kita berusaha mencari nilai terbesar yang habis membagi a dan b.

Alur Algoritma Euclidean untuk Memotong Kue

Secara bertahap, algoritma Euclidean "memangkas" a dengan satuan b sebanyak mungkin. Hal ini dilakukan pada operasi "a modulo b". Jika awalnya kue berukuran 30*21, maka yang berikutnya kita dapatkan adalah kue dengan ukuran 9*21 (sebab 30 mod 21 = 9). Perhatikan bahwa kue berukuran a*b sama saja dengan kue berukuran b*a. Pada algoritma Euclidean sesungguhnya, kue menjadi berukuran 21*9. Namun pada penjelasan ini saya biarkan menjadi 9*21 saja.

Hal yang sama akan diulang. Kini pemangkasan dilakukan pada bagian lebar, menurut panjangnya sebanyak mungkin. Jika tadinya berukuran 21*9, kini menjadi berukuran 3*9 (sebab 21 mod 9 = 3).

Ulangi terus sampai didapatkan kue yang langsung bisa dipotong menjadi persegi-persegi. Dengan kata lain, lebarnya habis membagi panjangnya (atau sebaliknya). Kebetulan hal itu telah tercapai, sebab 3 habis membagi 9. Pada algoritma Euclidean, hal ini dicapai ketika b=0, yang sama saja dengan ditemui a mod b = 0 (b habis membagi a).

Proses "memangkas" ini dijamin berakhir, sebab a dan b merupakan bilangan bulat dan pada kasus terburuk didapatkan kue berukuran 1*1. Lain ceritanya jika a dan b bisa berupa bilangan irasional, yang mana proses ini tidak akan berakhir.

Penutup

Pemahaman ini dapat bermanfaat juga untuk memahami bagaimana algoritma Extended Euclid bekerja untuk menyelesaikan diophantine equation. Coba Anda selidiki bagaimana mencari nilai x dan y, supaya ax + by = gcd(a, b) jika diketahui cara "pemotongan kue"-nya. Pencarian nilai ini bisa dilakukan mulai dari bawah, yaitu ketika b habis membagi a, lalu diteruskan ke atas.

syntax highlighting tutorial