{"id":773,"date":"2020-08-12T19:12:56","date_gmt":"2020-08-12T19:12:56","guid":{"rendered":"http:\/\/localhost\/?page_id=773"},"modified":"2022-04-28T09:03:29","modified_gmt":"2022-04-28T12:03:29","slug":"o-algoritmo-de-euclides","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/o-algoritmo-de-euclides\/","title":{"rendered":"O algoritmo de Euclides"},"content":{"rendered":"
\nSejam $a,b\\in\\N_0$ com $b<a$. O resultado provado no final da p\u00e1gina anterior sugere o seguinte processo recursivo para calcular o $\\mbox{mdc}(a,b)$:<\/p>\n

\nPasso 1:<\/strong> Se $b=0$, ent\u00e3o $\\mdc ab=a$.
\nPasso 2:<\/strong> Se $b \\neq 0$ ent\u00e3o use o Teorema de Divis\u00e3o de Euclides para escrever $a=qb+r$ com $r\\in\\{0,\\ldots,b-1\\}$.
\nPasso 3:<\/strong> $\\mdc ab=\\mdc br$.\n<\/p>\n

O processo funciona, pois no Passo 3., os n\u00fameros $b$ e $r$ s\u00e3o menores que $a$ e $b$. Logo, mais cedo ou mais tarde, o processo vai chegar at\u00e9 uma situa\u00e7\u00e3o quando $b=0$ e neste caso o valor do $\\mdc ab$ ser\u00e1 igual a $a$ pelo Passo 1. Veja o exemplo na p\u00e1gina anterior para uma computa\u00e7\u00e3o detalhada seguindo este processo.<\/p>\n

Este algoritmo pode ser implementado em Julia com a seguinte fun\u00e7\u00e3o recursiva.<\/p>\n

\nfunction MDC_recursivo( a, b )\n            \n    if b == 0\n        return a\n    else\n        return MDC_recursivo( b, a % b )\n\tend\nend\n<\/code><\/pre>\n
Para melhor analisarmos o algoritmo, n\u00f3s escrevemos o processo em uma maneira linear (n\u00e3o recursiva). O processo descrito abaixo \u00e9 chamado Algoritmo de Euclides. Sejam $a,b$ como acima.
\n\\[
\n\\begin{align*}
\nr_{-1}&=a\\\\
\nr_0&=b\\\\
\na=r_{-1}&=q_1b+r_1\\quad 0<r_1<b\\\\
\nb=r_0&=q_2r_1+r_2\\quad 0<r_2<r_1\\\\
\nr_1&=q_3r_2+r_3\\quad 0<r_3<r_2\\\\
\n&\\vdots\\\\
\nr_{i-1}&=q_{i+1}r_{i}+r_{i+1}\\quad 0<r_{i+1}<r_{i}\\\\
\nr_{i}&=q_{i+2}r_{i+1}+r_{i+2}\\quad 0<r_{i+2}<r_{i+1}\\\\
\n&\\vdots\\\\
\nr_{d-2}&=q_{d}r_{d-1}+r_{d}\\quad 0<r_{d}<r_{d-1}\\\\
\nr_{d-1}&=q_{d+1}r_d+0
\n\\end{align*}
\n\\]<\/p>\n
A sequ\u00eancia dos restos calculados satisfaz as desigualdades
\n\\[
\na>b>r_1>r_2>\\cdots>r_i>\\cdots>r_d>r_{d+1}=0.
\n\\]
\nEm outras palavras, a sequ\u00eancia dos restos \u00e9 uma sequ\u00eancia decrescente de n\u00fameros positivos. Note que tal sequ\u00eancia sempre atinge o n\u00famero zero em um n\u00famero finitos de passos; ou seja, existe algum $d$ tal que $r_{d+1}=0$. Pelo racioc\u00ednio acima, obtemos que
\n\\begin{align*}
\n\\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.
\n\\end{align*}<\/p>\n
Isso justifica o seguinte resultado.<\/p>\n
Se $a,b\\in \\N_0$ tais que $b\\neq 0$, ent\u00e3o o \u00faltimo resto n\u00e3o nulo $r_d$ calculado pelo Algoritmo de Euclides \u00e9 igual a $\\mdc ab$. O algoritmo termina depois de um n\u00famero finito de passos.\n<\/div>\n
Note que nos resultados acima, n\u00f3s assumimos que $a,b$ s\u00e3o n\u00fameros n\u00e3o negativos. No entanto, o procedimento pode ser usado mesmo quando $a$ ou $b$ (ou os dois) s\u00e3o negativos, pois neste caso, simplesmente podemos trocar o n\u00famero negativo pelo seu sim\u00e9trico (que vai ser positivo) pelo fato que $\\mdc ab=\\mdc{\\pm a}{\\pm b}$. <\/p>\n
Em particular n\u00f3s finalmente conseguimos concluir o seguinte resultado sobre a exist\u00eancia do $\\mdc ab$.<\/p>\n
\nSe $a,b\\in\\Z$ tais que $(a,b)\\neq (0,0)$, ent\u00e3o existe $\\mdc ab$.\n<\/div>\n
O procedimento acima pode tamb\u00e9m ser implementado em Julia com a seguinte fun\u00e7\u00e3o.<\/p>\n
\nfunction MDC(a,b)\n\n    while b != 0\n        a, b = b, a % b  \n\tend\n    return a\nend\n<\/code>\r\n<\/pre>\n
Uma outra consequ\u00eancia do Algoritmo de Euclides \u00e9 o seguinte resultado extremamente \u00fatil e bem conhecido.<\/p>\n
\nSejam $a,b\\in\\Z$ com $(a,b)\\neq 0$. Ent\u00e3o existem $u,v\\in\\Z$ tais que
\n\\[
\n\\mdc ab=ua+vb.
\n\\]
\nEm particular, se $a$ e $b$ s\u00e3o primos entre si, ent\u00e3o existem $u,v\\in\\Z$ tais que
\n\\[
\n1=ua+vb.
\n\\]\n<\/div>\n
\nN\u00f3s podemos assumir sem perda de generalidade que $0<b<a$. Com esta suposi\u00e7\u00e3o, podemos executar o algoritmo de Euclides para $a$ e $b$. <\/p>\n
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\u00e7\u00e3o por indu\u00e7\u00e3o em $i$. A afirma\u00e7\u00e3o est\u00e1 verdadeira para $i=1$, pois
\n\\[
\nr_1=a-q_1b\\quad\\text{e assim}\\quad u_1=1,\\ v_1=-q_1.
\n\\]
\nAssuma que $i\\geq 1$ e, para $j\\leq i$ existem $u_j,v_j\\in \\Z$ tais que
\n\\[
\nr_j=u_ja+v_jb.
\n\\]
\nOra, segue da equa\u00e7\u00e3o para $r_{i-1}$ que
\n\\begin{align*}
\nr_{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)\\\\&=
\n(u_{i-1}-q_{i+1}u_i)a+(v_{i-1}-q_{i+1}v_i)b.
\n\\end{align*}
\nOu seja, podemos tomar
\n\\[
\nu_{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.
\n\\] <\/p>\n
Agora, temos que
\n\\[
\n\\mdc ab=r_d=u_da+v_db
\n\\]
\ne o teorema est\u00e1 v\u00e1lido com $u=u_d$ e $v=v_d$.\n<\/p><\/div>\n
Note que a demonstra\u00e7\u00e3o acima d\u00e1 um algoritmo para calcular os coeficientes $u,v$ e este algoritmo pode ser executado em paralelo com a computa\u00e7\u00e3o do $\\mdc ab$. O algoritmo que calcula o $\\mdc ab$  junto com os coeficientes $u,v$ tais que
\n\\[
\n\\mdc ab=ua+vb
\n\\]
\n\u00e9 geralmente chamado Algoritmo Estendido de Euclides. A seguinte \u00e9 uma implementa\u00e7\u00e3o simples do Algoritmo Estendido em Julia.<\/p>\n
\r\n\n#algoritmo extendido de Euclides\nfunction XMDC(a,b)\n    x0, x = 1, 0; y0, y = 0, 1\n           \n    while b>0 \n        q, r = a \u00f7 b, a%b\n        a, b = b, r\n        \n        #atualizar x, x0, y, y0\n        x, x0 = x0 - q*x, x\n        y, y0 = y0 - q*y, y\n    end \n    \n    return a, x0, y0\nend\n<\/code>\r\n<\/pre>\n
Para verificarmos que o algoritmos de Euclides \u00e9 um algoritmo pr\u00e1tico, precisamos dar uma estimativa para o n\u00famero dos passos do que ele precisa; ou seja, precisamos limitar o n\u00famero $d$.<\/p>\n
A sequ\u00eancia de Fibonacci \u00e9 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\u00eancia s\u00e3o $1,1,2,3,5,8,13,21,34,\\ldots$<\/p>\n
Denote $\\varphi$ o n\u00famero $(1+\\sqrt 5)\/2$ (n\u00famero \u00e1ureo<\/a>).<\/p>\n
\u00a0
\nMostre, para $i\\geq 1$, que $\\varphi^{i-1}\\leq F_i\\leq\\varphi^i$.\n<\/div>\n
\nSeja $d$ o n\u00famero de passos que precisamos para executar o Algoritmo de Euclides para os n\u00fameros $a$ e $b$ como acima. Ent\u00e3o $d\\leq \\log b\/\\log \\varphi$.\n<\/div>\n
\u00a0
\nPonha $r_{-1}=a$, $r_0=b$, e seja $r_1,\\ldots,r_{d}$ a sequ\u00eancia dos restos na computa\u00e7\u00e3o 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$.<\/p>\n
Afirma\u00e7\u00e3o.<\/em>\u00a0$u_i\\geq F_i$. Provamos a afirma\u00e7\u00e3o por indu\u00e7\u00e3o em $i$. De fato, temos que $u_1\\geq F_1=1$ e $u_2\\geq F_2=2$. Se $i\\geq 3$, ent\u00e3o considere a equa\u00e7\u00e3o
\n\\begin{eqnarray*}
\nu_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.
\n\\end{eqnarray*}
\nCombinando esta conta com o exerc\u00edcio anterior, obtemos que
\n\\[
\nu_i\\geq F_i\\geq \\varphi^{i-1}\\quad\\mbox{para todo}\\quad i\\geq 1.
\n\\]
\nEm 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
\n\\[
\nd\\leq \\frac{\\log b}{\\log\\varphi}
\n\\]\n<\/div>\n
O resultado anterior implica que o n\u00famero de passos no Algoritmo de Euclides \u00e9 limitado por uma fun\u00e7\u00e3o logar\u00edtmica em $b$ que quer dizer que o Algoritmo de Euclides \u00e9 um algoritmo pr\u00e1tico.\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"
Sejam $a,b\\in\\N_0$ com $b<a$. O resultado provado no final da p\u00e1gina anterior sugere o seguinte processo recursivo para calcular o $\\mbox{mdc}(a,b)$: Passo 1: Se $b=0$, ent\u00e3o $\\mdc ab=a$. Passo 2: Se $b \\neq 0$ ent\u00e3o use o Teorema de Divis\u00e3o de Euclides para escrever $a=qb+r$ com $r\\in\\{0,\\ldots,b-1\\}$. Passo 3: $\\mdc ab=\\mdc br$. O processo funciona, … Continue reading O algoritmo de Euclides<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/773"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=773"}],"version-history":[{"count":9,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/773\/revisions"}],"predecessor-version":[{"id":1764,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/773\/revisions\/1764"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/706"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}