Lihat sumber Algoritma Euklides

Dalam [[matematika]], '''algoritma Euklides''' adalah suatu [[algoritme]] untuk menentukan [[faktor persekutuan terbesar]] (FPB) dari dua [[bilangan bulat]]. Algoritma ini dinamai setelah [[matematikawan]] [[Yunani]] [[Euklides]] menuliskannya dalam Buku VII dan Buku X ''[[Elemen Euklides]]''.

Algoritma Euklides muncul dalam buku ''Elemen'' Euklides sekitar tahun [[300 SM]], menjadikannya salah satu algoritma numerik yang tertua dan masih digunakan secara luas.

Algoritma Euklides tidak memerlukan [[faktorisasi]].

== Deskripsi algoritma ==
# Diberikan dua bilangan asli <math>a</math> dan <math>b</math>, periksa apakah <math>b</math> adalah nol.
# Jika ya, <math>a</math> adalah FPB. Jika tidak, ulangi langkah pertama dengan menggunakan <math>b</math> sebagai <math>a</math> yang baru dan sisa setelah <math>a</math> dibagi oleh <math>b</math> sebagai <math>b</math> yang baru.

== Contoh ==
Sebagai contoh, FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritma ini adalah 21, dengan langkah-langkah sebagai berikut:

{|
| align="right" | ''a''
| align="right" | ''b''
| align="right" | sisa setelah ''a'' dibagi oleh ''b''
|-
| colspan="3" |
----
|-
| align="right" | 1071
| align="right" | 1029
| align="right" | 42
|-
| align="right" | 1029
| align="right" | 42
| align="right" | 21
|-
| align="right" | 42
| align="right" | 21
| align="right" | 0
|-
| align="right" | 21
| align="right" | 0
|}

Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritma, kita juga dapat menentukan bilangan bulat ''p'' dan ''q'' di mana ''ap''&nbsp;+&nbsp;''bq''&nbsp;=&nbsp;fpb(''a'',&nbsp;''b''). Hal ini dikenal sebagai [[perluasan algoritme Euklides]].

== Bukti kebenaran ==
Misalkan <math>a</math> dan <math>b</math> adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari ''<math>a</math>'' oleh <math>b</math> adalah <math>t</math>. Maka <math>a = qb + t</math> di mana <math>q</math> adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari <math>a</math> dan <math>b</math> juga dapat habis membagi <math>t</math> (karena <math>t</math> dapat ditulis sebagai <math>t = a - qb</math>). Dengan cara yang sama, setiap pembagi dari <math>b</math> dan <math>t</math> juga akan habis membagi <math>a</math>. Maka faktor persekutuan terbesar dari <math>a</math> dan <math>b</math> adalah sama dengan FPB dari <math>b</math> dan <math>t</math>. Oleh karena itu, kita cukup meneruskan proses tadi dengan <math>b</math> dan <math>t</math> saja. Karena <math>t</math> lebih kecil dalam nilai mutlak dari <math>b</math>, kita akan mencapai<math>t = 0</math> setelah sejumlah langkah.

== Implementasi ==
Algoritma ini dapat dinyatakan dengan menggunakan [[rekursi kanan]]:

  '''function''' fpb(a, b)
      '''if''' b = 0
          '''return''' a
      '''else'''
          '''return''' fpb(b, a modulus b);

Secara iteratif, fungsi ini dapat ditulis sebagai:

  '''function''' fpb(a, b)
      '''while''' b ≠ 0
          '''var''' t:= b
          b:= a modulus b
          a:= t
      '''return''' a

Euklides pada mulanya merumuskan masalah ini secara geometri, sebagai masalah untuk mencari "satuan" yang dapat dipakai untuk panjang dari dua buah garis, dan algoritmanya berlangsung dengan mengulangi pengurangan dari sisi yang lebih pendek dari sisi yang lebih panjang. Implementasi ini sama dengan implementasi berikut ini, yang cukup tidak efisien dibandingkan dengan cara yang telah dijelaskan di atas:

  '''function''' fpb(a, b)
      '''while''' a ≠ b
          '''if''' a > b
              a:= a - b
          '''else'''
              b:= b - a
      '''return''' a

==Efisiensi algoritma==
Efisiensi komputasional algoritma Euklides telah dipelajari secara menyeluruh.<ref>[https://id.wikipedia.org/w/index.php?title=Algoritma+Euklides&oldid=28365202 sumber pada Wikipedia bahasa Indonesia]</ref> Efisiensi ini bisa diartikan sebagai banyak langkah pembagian yang perlu dilakukan algoritma, dikali dengan harga komputasi setiap pembagian. Analisis tertua yang diketahui tentang algoritma Euklides berasal dari A. A. L. Reynaud pada tahun 1811,<ref>A.-A.-L. Reynaud. [https://archive.org/details/bub_gb_YySjvK7oudIC Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique]. Courcier. 1811. Dikutip oleh .</ref> yang menunjukkan bahwa banyak langkah pembagian yang dilakukan dengan masukan <math>(u,v)</math> tidak mungkin lebih dari <math>v</math>; dia kemudian memperbaiki batas ini menjadi <math>\frac{v}{2} + 2</math>. Kemudian, pada tahun 1841, [[Pierre Joseph Étienne Finck|P. J. E. Finck]] menunjukkan<ref>P.-J.-E. Finck. ''Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales''. Derivaux. 1841.</ref> bahwa banyak langkah pembagian tidak mungkin lebih tinggi dari <math>2 \log_2 v + 1</math>, dan artinya algoritma Euklides berjalan dalam waktu polinomial dari ukuran masukannya.<ref>J. Shallit. ''Origins of the analysis of the Euclidean algorithm''. ''Historia Math''. 1994. Vol. 21. hlm. 401–419. doi:10.1006/hmat.1994.1031.</ref> [[Émile Léger]], pada tahun 1837, mempelajari kasus terburuknya, yaitu ketika masukannya adalah [[bilangan Fibonacci]] yang bersebelahan.<ref>J. Shallit. ''Origins of the analysis of the Euclidean algorithm''. ''Historia Math''. 1994. Vol. 21. hlm. 401–419. doi:10.1006/hmat.1994.1031.</ref> Analisis Finck kemudian diperbaiki oleh [[Gabriel Lamé]] pada tahun 1844,<ref>G. Lamé. ''Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers''. ''Comptes Rendus Acad. Sci''. 1844. Vol. 19. hlm. 867–870.</ref> yang menunjukkan bahwa banyak langkah yang diperlukan untuk menyelesaikan algoritma tidak pernah lebih dari lima kali banyak digit bilangan yang lebih kecil&nbsp;<math>b</math>.<ref>H. Grossman. ''On the Number of Divisions in Finding a G.C.D''. ''The American Mathematical Monthly''. 1924. Vol. 31 (9). hlm. 443. doi:10.2307/2298146.</ref><ref>R. Honsberger. ''Mathematical Gems II''. The Mathematical Association of America. 1976. hlm. 54–57. ISBN 0-88385-302-7.</ref>

== Penggunaan ==
Algoritma ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan. Ini termasuk [[polinomial gelanggang]] dalam suatu [[medan (matematika)|medan]], juga gelanggang dari [[bilangan bulat Gauss]], dan dalam [[ranah Euklides]] umum.

== Bibliografi ==
* 

== Pranala luar ==
* 
*  [http://www.cut-the-knot.org/blue/Euclid.shtml Algoritma Euklides] di cut-the-knot
* 
* [http://www.cut-the-knot.org/blue/binary.shtml Binary Euclid's Algorithm (Java)]
* [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game (Java)]

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Euklides&oldid=28365202 Wikipedia bahasa Indonesia], revisi 28365202 (2025-11-07T03:39:36Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->