Untuk menghitung \(\gcd(a,b) = d\text{,}\) kita menggunakan pembagian berulang untuk memperoleh barisan menurun bilangan bulat positif \(r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}\) yaitu,
\begin{align*}
b & = a q_1 + r_1\\
a & = r_1 q_2 + r_2\\
r_1 & = r_2 q_3 + r_3\\
& \aatavdots{=}\\
r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\
r_{n - 1} & = r_n q_{n + 1}\text{.}
\end{align*}
Untuk mencari \(r\) dan \(s\) sedemikian sehingga \(ar + bs = d\text{,}\) kita mulai dengan persamaan terakhir ini dan menyubstitusikan hasil yang diperoleh dari persamaan-persamaan sebelumnya:
\begin{align*}
d & = r_n\\
& = r_{n - 2} - r_{n - 1} q_n\\
& = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\
& = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}\\
& \aatavdots{=}\\
& = ra + sb\text{.}
\end{align*}
Algoritma yang baru saja kita gunakan untuk mencari faktor persekutuan terbesar \(d\) dari dua bilangan bulat \(a\) dan \(b\text{,}\) serta menuliskan \(d\) sebagai kombinasi linear dari \(a\) dan \(b\text{,}\) dikenal sebagai algoritma Euklides.