{"id":1330,"date":"2021-10-22T21:34:26","date_gmt":"2021-10-23T00:34:26","guid":{"rendered":"http:\/\/localhost\/?page_id=1330"},"modified":"2023-01-06T14:43:55","modified_gmt":"2023-01-06T17:43:55","slug":"o-algoritmo-de-euclides","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/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

Passo 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$.<\/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 Python com a seguinte fun\u00e7\u00e3o recursiva.<\/p>\n

\ndef MDC_recursivo( a, b ):\n            \n    if b == 0:\n        return a\n    else:\n        return MDC_recursivo( b, a % b ) \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.<\/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$.<\/div>\n
O procedimento acima pode tamb\u00e9m ser implementado em Python com a seguinte fun\u00e7\u00e3o.<\/p>\n
\ndef MDC(a,b):\n\n    while b != 0:\n        a, b = b, a % b  \n\n    return a\n<\/code>\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\\]<\/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$.<\/p>\n<\/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 Python.<\/p>\n
\ndef XMDC(a,b):\n        \n    prevu, u = 1, 0; prevv, v = 0, 1 \n    \n    while b != 0:\n        q = a\/\/b\n        u, prevu = prevu - q*u, u\n        v, prevv = prevv - q*v, v\n        a, b = b, a % b\n   \n    return a, prevu, prevv\n<\/code>\n<\/pre>\n<\/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":1193,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1330"}],"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=1330"}],"version-history":[{"count":11,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1330\/revisions"}],"predecessor-version":[{"id":1979,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1330\/revisions\/1979"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1193"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}