Algoritma Euklides adalah salah satu algoritma paling kuno dalam matematika yang digunakan untuk menghitung GCD (Greatest Common Divisor), atau FPB (Faktor Persekutuan Terbesar), dari dua bilangan bulat. GCD adalah bilangan terbesar yang dapat membagi kedua bilangan tanpa menyisakan sisa. Algoritma ini dinamakan sesuai dengan matematikawan Yunani kuno, Euclid, yang memperkenalkannya dalam bukunya Elements sekitar abad ke-3 SM.

Selain dikenal karena kesederhanaannya, algoritma ini sangat efisien dan masih digunakan dalam berbagai aplikasi modern seperti kriptografi dan komputasi. Artikel ini akan membahas pengertian GCD, penjelasan langkah-langkah Algoritma Euklides, dan aplikasinya dalam konteks modern.

Pengertian GCD

GCD dari dua bilangan bulat aaa dan bbb adalah bilangan bulat terbesar yang dapat membagi kedua bilangan tersebut tanpa meninggalkan sisa. Misalnya, GCD dari 48 dan 18 adalah 6, karena 6 adalah bilangan terbesar yang membagi 48 dan 18.

Secara formal, jika aaa dan bbb adalah dua bilangan bulat positif, maka GCD(a,b)\text{GCD}(a, b)GCD(a,b) adalah bilangan bulat terbesar ddd sedemikian rupa sehingga:d∣adand∣bd \mid a \quad \text{dan} \quad d \mid bd∣adand∣b

Artinya, ddd membagi aaa dan bbb tanpa sisa.

Algoritma Euklides

Algoritma Euklides bekerja dengan menggunakan sifat dasar GCD: jika aaa dan bbb adalah dua bilangan bulat, maka GCD(a,b)=GCD(b,r)\text{GCD}(a, b) = \text{GCD}(b, r)GCD(a,b)=GCD(b,r), di mana rrr adalah sisa pembagian aaa oleh bbb. Dengan menggunakan sifat ini, algoritma terus mengurangi bilangan sampai salah satu dari bilangan tersebut menjadi nol, dan GCD-nya adalah bilangan lain yang tersisa.

Langkah-langkah Algoritma Euklides

1. Mulai dengan dua bilangan: Misalkan kita memiliki dua bilangan aaa dan bbb, di mana a>ba > ba>b.
2. Lakukan pembagian: Bagi aaa dengan bbb dan peroleh sisanya, r=amod  br = a \mod br=amodb.
3. Perbarui bilangan: Ganti aaa dengan bbb, dan bbb dengan rrr.
4. Ulangi: Ulangi langkah 2 dan 3 sampai b=0b = 0b=0.
5. GCD ditemukan: Ketika b=0b = 0b=0, nilai aaa pada langkah terakhir adalah GCD dari dua bilangan asli.

Contoh Penggunaan Algoritma Euklides

Mari kita hitung GCD dari 48 dan 18 menggunakan Algoritma Euklides:

1. Langkah 1: Mulai dengan 48 dan 18.
2. Langkah 2: Bagi 48 dengan 18, dan sisanya adalah 48mod  18=1248 \mod 18 = 1248mod18=12. Jadi, perbarui a=18a = 18a=18 dan b=12b = 12b=12.
3. Langkah 3: Bagi 18 dengan 12, dan sisanya adalah 18mod  12=618 \mod 12 = 618mod12=6. Perbarui a=12a = 12a=12 dan b=6b = 6b=6.
4. Langkah 4: Bagi 12 dengan 6, dan sisanya adalah 12mod  6=012 \mod 6 = 012mod6=0. Perbarui a=6a = 6a=6 dan b=0b = 0b=0.
5. Hasil: Ketika b=0b = 0b=0, nilai aaa adalah 6, sehingga GCD(48,18)=6\text{GCD}(48, 18) = 6GCD(48,18)=6.

Algoritma ini membutuhkan hanya beberapa langkah sederhana untuk menemukan GCD, bahkan untuk bilangan yang relatif besar. Keefisienannya yang tinggi menjadi salah satu alasan mengapa algoritma ini tetap digunakan hingga hari ini.

Variasi Algoritma Euklides

Ada juga Algoritma Euklides Terbagi (Extended Euclidean Algorithm) yang tidak hanya menemukan GCD dari dua bilangan tetapi juga menghasilkan kombinasi linier dari dua bilangan tersebut. Artinya, algoritma ini memberikan solusi untuk persamaan:GCD(a,b)=ax+by\text{GCD}(a, b) = ax + byGCD(a,b)=ax+by

Di mana xxx dan yyy adalah koefisien bilangan bulat yang memenuhi persamaan di atas. Algoritma ini berguna dalam teori bilangan dan kriptografi, terutama dalam algoritma seperti RSA yang bergantung pada sifat GCD dan invers modular.

Aplikasi Modern Algoritma Euklides

Meskipun ditemukan lebih dari dua milenium yang lalu, Algoritma Euklides tetap relevan dan digunakan dalam berbagai aplikasi modern, terutama di bidang kriptografi, teori bilangan, dan komputasi. Beberapa contoh aplikasinya antara lain:

1. Kriptografi Asimetris (RSA): Algoritma ini digunakan untuk menghitung invers modular yang penting dalam algoritma enkripsi dan dekripsi RSA. Dalam RSA, penghitungan GCD membantu menentukan apakah dua bilangan relatif prima dan dapat menghasilkan kunci publik dan privat.
2. Teori Bilangan: Dalam teori bilangan, Algoritma Euklides digunakan untuk memecahkan masalah-masalah seperti mencari invers modular, menyelesaikan persamaan Diophantine, dan banyak lagi.
3. Sistem Komputer: Banyak sistem komputer yang memanfaatkan algoritma ini untuk tugas-tugas seperti pembagian bilangan besar, penjadwalan, dan pengoptimalan perangkat keras.
4. Sains Data dan Algoritma Pemrograman: Algoritma ini juga digunakan dalam algoritma pemrograman dan struktur data, seperti pencarian pohon biner dan algoritma optimasi.

Kesimpulan

Algoritma Euklides adalah metode sederhana namun sangat efektif untuk menghitung GCD atau FPB dari dua bilangan bulat. Meskipun sangat kuno, algoritma ini terus digunakan hingga hari ini dalam berbagai aplikasi modern, terutama dalam kriptografi dan teori bilangan. Fleksibilitas dan efisiensinya menjadikannya salah satu algoritma terpenting dalam matematika dan komputasi.

sumber : Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers. Oxford University Press.