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 Julia com a seguinte função recursiva.
function MDC_recursivo( a, b )
if b == 0
return a
else
return MDC_recursivo( b, a % b )
end
end
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 Julia com a seguinte função.
function MDC(a,b)
while b != 0
a, b = b, a % b
end
return a
end
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 Julia.
#algoritmo extendido de Euclides
function XMDC(a,b)
x0, x = 1, 0; y0, y = 0, 1
while b>0
q, r = a ÷ b, a%b
a, b = b, r
#atualizar x, x0, y, y0
x, x0 = x0 - q*x, x
y, y0 = y0 - q*y, y
end
return a, x0, y0
end
Para verificarmos que o algoritmos de Euclides é um algoritmo prático, precisamos dar uma estimativa para o número dos passos do que ele precisa; ou seja, precisamos limitar o número $d$.
A sequência de Fibonacci é definida com a seguinte regra. Tomemos $F_0=F_1=1$, e para $i\geq 2$, definimos $F_i=F_{i-1}+F_{i-2}$. Os termos da sequência são $1,1,2,3,5,8,13,21,34,\ldots$
Denote $\varphi$ o número $(1+\sqrt 5)/2$ (número áureo).
Mostre, para $i\geq 1$, que $\varphi^{i-1}\leq F_i\leq\varphi^i$.
Ponha $r_{-1}=a$, $r_0=b$, e seja $r_1,\ldots,r_{d}$ a sequência dos restos na computação acima. Defina $u_1=r_d$, $u_2=r_{d-1}$, $u_3=r_{d-2},\ldots,u_{d-1}=r_{2}$, $u_{d}=r_1$, $u_{d+1}=r_0=b$, $u_{d+2}=r_{-1}=a$.
Afirmação. $u_i\geq F_i$. Provamos a afirmação por indução em $i$. De fato, temos que $u_1\geq F_1=1$ e $u_2\geq F_2=2$. Se $i\geq 3$, então considere a equação
\begin{eqnarray*}
u_i&=&r_{d-i+1}=r_{d-i+2}q_{d-i+2}+r_{d-i+3}\geq r_{d-i+2}+r_{d-i+3}\\&=&u_{i-1}+u_{i-2}\geq F_{i-1}+F_{i-2}=F_i.
\end{eqnarray*}
Combinando esta conta com o exercício anterior, obtemos que
\[
u_i\geq F_i\geq \varphi^{i-1}\quad\mbox{para todo}\quad i\geq 1.
\]
Em particular $b=u_{d+1}\geq \varphi^{d}$. Tomando o logaritmo isso implica que $\log_{\varphi}b\geq d$. Passando para o logaritmo natural, tem-se que
\[
d\leq \frac{\log b}{\log\varphi}
\]
O resultado anterior implica que o número de passos no Algoritmo de Euclides é limitado por uma função logarítmica em $b$ que quer dizer que o Algoritmo de Euclides é um algoritmo prático.