Mostrar código-fonte de O algoritmo de Euclides

<span style="font-size:8pt"><b>Referência : </b> Tavares, J., (2018) O algoritmo de Euclides, ''[http://rce.casadasciencias.org Rev. Ciência Elem.]'', V6(3):056
<br>
<span style="font-size:8pt"><b>Autor</b>: <i>[[Usu&aacute;rio:Jntavar|João Nuno Tavares]]</i></span><br>
<span style="font-size:8pt"><span style="font-size:8pt"><b>Editor</b>: <i>[[Usu&aacute;rio:Jfgomes47|José Ferreira Gomes]]</i></span><br>
<span style="font-size:8pt"><b>DOI</b>: <i>[[http://doi.org/10.24927/rce2018.056 http://doi.org/10.24927/rce2018.056]]</i></span><br>
<html><a href="https://rce.casadasciencias.org/rceapp/pdf/2018/056/" target="_blank">
                <img src="https://rce.casadasciencias.org/static/images/layout/pdf.png" alt="PDF Download"></a></html>
----


<html>
<p class='mainText'>Consideremos uma fração, por exemplo,\(\frac{1876434}{983451}\) . Será irredutível? Isto é, o
        numerador e o denominador
        admitem, como divisor comum, apenas o número 1?</p>
    <p class='mainText'>Para responder a esta questão, podemos pensar em enumerar todos os divisores, quer do numerador,
        quer do denominador, e depois ver quais os que são comuns. No entanto, para números muito grandes, a enumeração
        dos seus divisores pode ser um problema complicado. De facto, não se conhece um algoritmo eficiente que o faça!
    </p>
    <p class='mainText'>Surpreendentemente, é muito mais fácil calcular os divisores comuns a dois números dados a e b,
        e, portanto, calcular o maior deles, - o chamado Máximo Divisor Comum de \(a\) e \(b\): MDC(\(a\), \(b\)). Para
        simplificar a
        discussão vamo-nos restringir a números inteiros positivos \(a\) e \(b\).</p>
    <p class='mainText'>O método foi proposto por Euclides, e, por isso, chama-se o algoritmo de Euclides, e foi
        exposto, há mais de 2000 anos, na sua grande obra <em>Os Elementos</em>, Livro VII, proposição 2. Em que
        consiste?
        Sumariamente, Euclides propõe, nas suas próprias palavras, subtrair sucessivamente o menor número do maior. Mais
        formalmente, para calcular, por exemplo, MDC(15, 9) fazemos</p>
    <br>
<center>
    <p class='mainText centered'>MDC(15, 9) = MDC(9, 6) = MDC(6, 3) = MDC(3, 3) = 3</p>
</center>
    <br>
    <p class='mainText'>Algoritmo de Euclides: <em>dados dois números inteiros positivos \(a\) e \(b\), com \(a\) >
        \(b\), para calcular
        MDC(\(a\), \(b\)), substituímos o par (\(a\), \(b\)) por (\(b\), \(a\) - \(b\)), e repetimos sucessivamente esta
        operação as vezes
        necessárias até obter um par de números iguais. Este número comum é a solução.</em></p>

</div>
<div class="article-body">

    <p class='mainText'>Este algoritmo pode ser implementado através de um dos códigos seguintes:</p>


<center>
    <table border="1">
        <tr>
            <th><div align="center">M é o máximo divisor comum</div></th>
            <th><div align="center">Código da função MDC(<em>a</em>, <em>b</em>)</div></th>
        </tr>
        <tr>
            <td bgcolor="#BDBDBD">
                <div align="left"> u := a; v := b;<br>
                while u ≠ v do
                <br>
                &nbsp; &nbsp; &nbsp; begin
                <br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if u > v then u := u - v
                <br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else v := v - u
                <br>
                &nbsp; &nbsp; &nbsp; end
                <br>
                M := u</div>
            </td>
            <td bgcolor="#BDBDBD">
                <div align="left">
                if a = b then M = a<br>
                &nbsp; &nbsp; &nbsp; else<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; begin<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if a > b then M := MDC(a - b; b)<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else M := MDC(a; b - a)<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; end
                    </div>
            </td>
        </tr>
    </table>
</center>
    <br>
    <p class='mainText'>Para provar que este algoritmo funciona, observamos os factos seguintes:</p>
    <br>
    <ol type="1">
        <li>Se d é um divisor comum dos inteiros positivos \(a\) e \(b\), com \(a\) > \(b\), então d é também um
            divisor comum dos inteiros positivos \(b\) e \(a\) - \(b\).
        </li>
        <li>O algoritmo produz sucessivamente inteiros positivos cada vez mais pequenos, e, portanto, termina com um
            numero inteiro ≥ 1.
        </li>
    </ol>
    <br>

    <p class='mainText'>O algoritmo de Euclides, tal como ele o enunciou nos Elementos, pode não ser muito eficiente.
        Por exemplo, se tentarmos encontrar MDC(101, 10<sup>100</sup> + 1) por subtração repetida, teremos que subtrair
        101 de
        10<sup>100</sup> + 1 quase 1098 vezes, o que não é, evidentemente, muito rápido.</p>
    <p class='mainText'>No entanto, subtrair repetidamente \(b\) de \(a\), até que a diferença, \(r\) = \(a\) - \(b\),
        seja menor do que \(b\),
        é o mesmo que dividir (\(a\) por \(b\) e obter o resto \(r\), como se ilustra na figura seguinte.</p>

    <br>
<center>
    <figure class="image-big">
        <img src="https://rce.casadasciencias.org/static/images/articles/2018-056-01.png" width="550">
    </figure>
</center>
    <br>
    <p class='mainText'>Isto dá origem ao seguinte algoritmo de divisão Euclideana: Dados dois números naturais \(a\) e
        \(b\),
        com \(a\) > \(b\) e \(b\) ≠ 0, existem números naturais \(q\) e \(r\), “quociente” e “resto”, tais que:</p>
    <br>
<center>
    <p class='mainText centered'>\(a = qb + r\) onde \(0 ≤ r < b\)</p>
</center>
    <br>
    <p class='mainText'>A propriedade de divisão é visualmente óbvia, como se ilustra na figura acima, porque qualquer
        número natural a deve estar entre múltiplos sucessivos de \(b\) - na figura, entre \(qb\) e (\(q + 1\))b. Em
        particular, a
        sua distância \(r\), ao múltiplo menor, \(qb\), e menor do que a distância \(b\) entre eles.</p>
    <p class='mainText'>A vantagem do algoritmo de divisão euclideana, é que, em geral, é muito mais rápido do que a
        subtração repetida. Cada divisão de um número natural \(b\) por um número \(a < b\), com \(k\) algarismos,
        “cancela” cerca
        de \(k\) algarismos em \(b\), e conduz a um resto \(r\) com no máximo \(k\) algarismos. Portanto, o número de
        divisões e no
        máximo igual ao número total de dígitos dos números com que começámos. Resumindo</p>
    <br>
<center>
    <p class='mainText centered'>MDC(\(a, b\)) = MDC(\(b, r\)), onde \(a = qb + r\)</p>
</center>
    <br>
    <p class='mainText'>Por exemplo</p>
    <br>
  <center>
  <p class='mainText centered'>MDC(1345, 24) = MDC(24, 1) = 1</p>
</center>
    <br>
    <p class='mainText'>já que 1345 = 24 × 56 + 1. Em geral, podemos calcular M = MDC(\(a\), \(b\)) através do código
        seguinte:</p>



<center>
    <table boder="1">
        <tr>
            <td bgcolor="#BDBDBD">
                 <div align="left">
                     u := a; v := b;<br>
                while v > 0 do<br>
                 &nbsp; &nbsp; &nbsp; begin<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r := u mod v;<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; u := v;<br>
                &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; v := r;<br>
                 &nbsp; &nbsp; &nbsp; end<br>
                M := u</div>
            </td>
        </tr>
    </table>
</center>
</html>


----


Recursos relacionados disponíveis na [http://www.casadasciencias.org Casa das Ciências]:<br>
# [https://www.casadasciencias.org/recurso/6319 og@r ao m.d.c. e ao m.m.c. com o GeoGebra].<br>


---- <br>Criada em 20 de Setembro de 2018<br> Revista em 22 de Setembro de 2018<br> Aceite pelo editor em 4 de Outubro de 2018<br>
[[Category:Matemática]]