Algoritma Euclidean

<<GCD
Di dalam Pembagi Persekutuan Terbesar telah diperlihatkan bahwa untuk mencari GCD dari dua buah bilangan bulat a dan b, mula-mula kita mendaftarkan semua pembagi dari masing-masing a dan b, lalu memilih pembagi persekutuan yang bernilai paling besar.

Pada bagian ini akan diberikan metode untuk menemukan GCD, yang dikenal dengan nama Algoritma Euclidean. Algoritma ini sudah dikenal sejak lama. Euclid, penemu algoritma ini adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.

Algoritma Euclidean didasarkan pada Teorema Algoritma Pembagian  secara berturut-turut sampai kita menemukan sisa pembagian bernilai 0. Secara formal algoritma Euclidean dirumuskan sebagai berikut:

Misalkan a dan b adalah bilangan bulat positif dengan \(a\geq b\). Misalkan \(r_{0}=a\) dan \(r_{1}=b\). Lakukan secara berturut-turut Teorema Algoritma Pembagian untuk memperoleh :

\(r_{0} = r_{1}q_{1}+r_{2}\)             \(0\leq r_{2}\leq r_{1} \)

\(r_{1} = r_{2}q_{2}+r_{3}\)             \(0\leq r_{3}\leq r_{2} \)

.

.

.

\(r_{n-2} = r_{n-1}q_{n-1}+r_{n}\)    \(0\leq r_{n}\leq r_{n-1} \)

\(r_{n-1} = r_{n}q_{n}+0\)

Menurut Teorema Algoritma Euclidean,

\(GCD(a,b)=GCD(r_{0},r_{1})=GCD(r_{1},r_{2})=...=GCD(r_{n-2},r_{n-1})=GCD(r_{n-1},r_{n})=GCD(r_{n},0)=r_{n}\)

Extended GCD.

Bezout Identity>>