16 O algoritmo de Euclides

Sejam \(a,b\in\N_0\) com \(b<a\). O resultado provado no final da página anterior sugere o seguinte processo recursivo para calcular o \(\mbox{mdc}(a,b)\):

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.

Lema 16.1 Se \(a,b\in \N_0\) tais que \(b\neq 0\), então o último resto não nulo \(r_d\) calculado pelo Algoritmo de Euclides é igual a \(\mdc ab\). O algoritmo termina depois de um número finito de passos.

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\).

Corolário 16.1 Se \(a,b\in\Z\) tais que \((a,b)\neq (0,0)\), então existe \(\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.

Teorema 16.1 Sejam \(a,b\in\Z\) com \((a,b)\neq 0\). Então existem \(u,v\in\Z\) tais que \[ \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. \]

Comprovação. Nós podemos assumir sem perda de generalidade que \(0<b<a\). Com esta suposição, podemos executar o algoritmo de Euclides para \(a\) e \(b\).

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