Algoritma Euclid atau dalam bahasa Internasional dikenali dengan Eucladin's Algorithmmerupakan suatu algoritma, atau kesatuan perintah yang terdiri dari simbol (setelah di terjemahkan secara simbolik) yang digunakan untuk menentukan faktor persekutuan terbesar dari dua buah bilangan bulat. Secara historis algortima ini dikenal sebagai algoritma tertua di dunia. Algoritma ini sendiridikutip dari buku Element karya Euclid pada tahun sekitar 300 BC. Ketika mencari faktor persekutuan terbesar (FPB) dari dua buah bilangan denganmenggunakan algoritma Euclid tidak dibutuhkan proses pemfaktoran.
 |
| Contoh Algoritma Euclid |
Penerapan Algoritma Euclid
Sebagai contoh untuk mempermudah pemahaman pengunaan algoritma euclid diperlihatkan oleh contoh di bawah ini. Misalkan diberikan x dan y. Kita akan mencari FPB kedua bilangan tersebut. Lebih sederhananya dalam hal ini kita misalkan x = 1071 dan y = 1021. Demi lebih kerapian kita akan lebih memilih menulis dalam bentuk tabel berikut ini.
x
|
y
| sisa |
1071
|
1029
|
42
|
1029
|
42
|
21
|
42
|
21
|
0
|
Secara umum penjelasan dengan menggunakan formula ini mengunakan prinsip sebagai berikut. Pertama periksa apakah bilangan y nol atau tidak. Jika y adalah nol maka a merupakan fpb. Jika tidak maka diulang lagi proses y, jika setelah x dibagi y lagi (penulisan dibentuk dalam x modulus y). Karena y pada baris pertama bukanlah nol, maka bilanganyang lebih besar dibagi dengan bilangan kedua. Hasil yang diperoleh satu dan bersisa 42. Dalam hal ini biasanya akan ditulis dalam bentuk fungsi modulus. 1071= 1.1029 + 42. Usaha meningat bagian yang ditebalkan, karena ini akan dipakai pada berikutya.
Sekarang kita lanjutkan pada baris ke-dua. Pembagi pada baris pertama (y1) akan mengisi bagian x2. Sementara sisa pada baris pertama akan mengisi ruang pada pembagi (y2) pada baris kedua. Langkah selanjutnya akan dilakukan operasi pembagian yang sama.Pada baris ke dua dilakukan operasi yang sama. 1029 : 42 didapat sisa pembagian 21. Dalam fungsi modulus terbentuk 1029= 24.42+21. Sama dengan sebelumnya pembagi pada baris kedua akan menempati bagian x3 dan sisa baris kedua akan menempati pembagi (y3) pada baris ke 3.
Hal ini terus dilakukan sampai sisa pembagian nol. Pada persoalan kali ini terlihat pada baris ketiga di dapat pembagian 42: 21 bersisa nol. Ini akkirnya proses telah selesai. Maka pembagi akhir yang menyebabka sisa nol tersebut merupakan Faktor Persekutuan Terbesar yang kita cari. Keterangan dari fungsi modulus memiliki bentuk umum Bilangan = (k)x(Pembagi) + Sisa. Jika diperhatikan fungsi modulus di atas maka angka yang berwarna biru adalah pembagi dan berwarna merah adalah sisa pembagian.
Algortima Euclid dalam Bahasa Pemograman
Dengan kecanggihan teknologi, serta perkembangan matematika yang terintegrasi dalam beberapa bahasa pemograman maka algoritma Euclid ini bisa dibuat dalam bentuk program komputasi. Dengan mengunakan bahasa pemograman maka cukup dengan melakukan input bilangan yang akan dicari akan ditemukan langsung FPB dari kedua bilangan tersebut. Berikut salah satu contoh code yang dikutip dari wikicode.if b = 0return aelsereturn fpb(b, a modulus b);Penulisan fungsi dalam bentuk iteratif: function fpb(a, b)Pembuktian kebenaran teori ini secara induktif bisa dilakukan secara pemfaktoran. Sebagaimana contoh yang telah diberikan tadi, bisa diambil angka 1071 dan 1029. Faktor dari 1071 = 3x3x7x17. Sementara penfaktoran 1029= 3x7x7x7. Terlihat jelas faktor persekutuan dari ke dua bilangan tersebut 37= 21.
while b ≠ 0
var t := b
b := a modulus b
a := t
return a
function fpb(a, b)
while a ≠ b
if a > b
a := a - b
else
b := b - a
return a
Sumber
