Passo 1: Se $b=0$, então $\mdc ab=a$.
Passo 2: Se $b \neq 0$ então use o Teorema de Divisão de Euclides para escrever $a=qb+r$ com $r\in\{0,\ldots,b-1\}$.
Passo 3: $\mdc ab=\mdc br$.
O processo funciona, pois no Passo 3., os números $b$ e $r$ são menores que $a$ e $b$. Logo, mais cedo ou mais tarde, o processo vai chegar até uma situação quando $b=0$ e neste caso o valor do $\mdc ab$ será igual a $a$ pelo Passo 1. Veja o exemplo na página anterior para uma computação detalhada seguindo este processo.
Este algoritmo pode ser implementado em Python com a seguinte função recursiva.
def MDC_recursivo( a, b ):
if b == 0:
return a
else:
return MDC_recursivo( b, a % b )
Para melhor analisarmos o algoritmo, nós escrevemos o processo em uma maneira linear (não recursiva). O processo descrito abaixo é chamado Algoritmo de Euclides. Sejam $a,b$ como acima.
\[
\begin{align*}
r_{-1}&=a\\
r_0&=b\\
a=r_{-1}&=q_1b+r_1\quad 0<r_1<b\\
b=r_0&=q_2r_1+r_2\quad 0<r_2<r_1\\
r_1&=q_3r_2+r_3\quad 0<r_3<r_2\\
&\vdots\\
r_{i-1}&=q_{i+1}r_{i}+r_{i+1}\quad 0<r_{i+1}<r_{i}\\
r_{i}&=q_{i+2}r_{i+1}+r_{i+2}\quad 0<r_{i+2}<r_{i+1}\\
&\vdots\\
r_{d-2}&=q_{d}r_{d-1}+r_{d}\quad 0<r_{d}<r_{d-1}\\
r_{d-1}&=q_{d+1}r_d+0
\end{align*}
\]
A sequência dos restos calculados satisfaz as desigualdades
\[
a>b>r_1>r_2>\cdots>r_i>\cdots>r_d>r_{d+1}=0.
\]
Em outras palavras, a sequência dos restos é uma sequência decrescente de números positivos. Note que tal sequência sempre atinge o número zero em um número finitos de passos; ou seja, existe algum $d$ tal que $r_{d+1}=0$. Pelo raciocínio acima, obtemos que
\begin{align*}
\mdc ab&=\mdc b{r_1}=\mdc{r_1}{r_2}=\cdots=\mdc{r_i}{r_{i+1}}=\cdots\\&=\mdc{r_{d-1}}{r_d}=\mdc{r_d}0=r_d.
\end{align*}
Isso justifica o seguinte resultado.
Note que nos resultados acima, nós assumimos que $a,b$ são números não negativos. No entanto, o procedimento pode ser usado mesmo quando $a$ ou $b$ (ou os dois) são negativos, pois neste caso, simplesmente podemos trocar o número negativo pelo seu simétrico (que vai ser positivo) pelo fato que $\mdc ab=\mdc{\pm a}{\pm b}$.
Em particular nós finalmente conseguimos concluir o seguinte resultado sobre a existência do $\mdc ab$.
O procedimento acima pode também ser implementado em Python com a seguinte função.
def MDC(a,b):
while b != 0:
a, b = b, a % b
return a
Uma outra consequência do Algoritmo de Euclides é o seguinte resultado extremamente útil e bem conhecido.
\[
\mdc ab=ua+vb.
\]
Em particular, se $a$ e $b$ são primos entre si, então existem $u,v\in\Z$ tais que
\[
1=ua+vb.
\]
Afirmamos que, para todo $i\geq 1$, o resto $r_i$ pode ser escrito como $u_ia+v_ib$ com coeficientes $u_i,v_i\in\Z$. Verificaremos a afirmação por indução em $i$. A afirmação está verdadeira para $i=1$, pois
\[
r_1=a-q_1b\quad\text{e assim}\quad u_1=1,\ v_1=-q_1.
\]
Assuma que $i\geq 1$ e, para $j\leq i$ existem $u_j,v_j\in \Z$ tais que
\[
r_j=u_ja+v_jb.
\]
Ora, segue da equação para $r_{i-1}$ que
\begin{align*}
r_{i+1}&=r_{i-1}-q_{i+1}r_{i}=u_{i-1}a+v_{i-1}b-q_{i+1}(u_{i}a+v_{i}b)\\&=
(u_{i-1}-q_{i+1}u_i)a+(v_{i-1}-q_{i+1}v_i)b.
\end{align*}
Ou seja, podemos tomar
\[
u_{i+1}=u_{i-1}-q_{i+1}u_i\quad\mbox{e}\quad v_{i+1}=v_{i-1}-q_{i+1}v_i.
\]
Agora, temos que
\[
\mdc ab=r_d=u_da+v_db
\]
e o teorema está válido com $u=u_d$ e $v=v_d$.
Note que a demonstração acima dá um algoritmo para calcular os coeficientes $u,v$ e este algoritmo pode ser executado em paralelo com a computação do $\mdc ab$. O algoritmo que calcula o $\mdc ab$ junto com os coeficientes $u,v$ tais que
\[
\mdc ab=ua+vb
\]
é geralmente chamado Algoritmo Estendido de Euclides. A seguinte é uma implementação simples do Algoritmo Estendido em Python.
def XMDC(a,b):
prevu, u = 1, 0; prevv, v = 0, 1
while b != 0:
q = a//b
u, prevu = prevu - q*u, u
v, prevv = prevv - q*v, v
a, b = b, a % b
return a, prevu, prevv