Algoritma dan implementasi

Diberikan dua bilangan asli a dan b, periksa apakah b adalah nol. Jika ya, a adalah FPB. Jika tidak, ulangi proses tadi menggunakan b dan sisa setelah a dibagi oleh b (ditulis sebagai a modulus b). Algoritma ini dapat dinyatakan dengan menggunakan rekursi kanan:

Templat:Wikicode

 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

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

a	b	t
1071	1029	42
1029	42	21
42	21	0
21	0

Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritma, kita juga dapat menentukan bilangan bulat p dan q di mana ap + bq = fpb(a, b). Hal ini dikenal sebagai Ekstensi Algoritma Euklidean.

Algoritma ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan. Ini termasuk polinomial cincin dalam suatu medan, juga cincin dari bilangan bulat Gaussian, dan dalam domain Euklidean umum.

Euklid 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