{"id":1583,"date":"2022-01-16T15:04:41","date_gmt":"2022-01-16T18:04:41","guid":{"rendered":"http:\/\/localhost\/?page_id=1583"},"modified":"2023-01-06T14:51:03","modified_gmt":"2023-01-06T17:51:03","slug":"o-mdc-de-dois-polinomios-e-o-algoritmo-de-euclides","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/o-mdc-de-dois-polinomios-e-o-algoritmo-de-euclides\/","title":{"rendered":"O MDC de dois polin\u00f4mios e o Algoritmo de Euclides"},"content":{"rendered":"
\nNesta p\u00e1gina $\\F$ \u00e9 um corpo. Por exemplo, pode tomar $\\Q$, $\\R$, $\\C$, ou $\\Z_p$ ($p$ sendo primo) como $\\F$.<\/p>\n
\nSejam $f(x),g(x)\\in\\F[x]$. Dizemos que $d(x)\\in\\F[x]$ \u00e9 maior divisor comum<\/strong> de $f(x)$ e $g(x)$ se<\/p>\n
    \n
  1. $d(x)$ \u00e9 m\u00f4nico;<\/li>\n
  2. $d(x)\\mid f(x)$ e $d(x)\\mid g(x)$;<\/li>\n
  3. se $c(x)\\in\\F[x]$ tal que $c(x)\\mid f(x)$ e $c(x)\\mid g(x)$, ent\u00e3o $c(x)\\mid d(x)$.<\/li>\n<\/ol>\n<\/div>\n
    \nAs seguintes afirma\u00e7\u00f5es s\u00e3o v\u00e1lidas:<\/p>\n
      \n
    1. Se o maior divisor comum de $f(x)$ e $g(x)$ existe, ent\u00e3o ele \u00e9 \u00fanico.<\/li>\n
    2. Se existe o maior divisor comum de $f(x)$ e $g(x)$ e $\\alpha,\\beta\\in\\F\\setminus\\{0\\}$, ent\u00e3o existe o maior divisor comum de $\\alpha f(x)$ e $\\beta g(x)$ e \u00e9 igual a maior divisor comum de $f(x)$ e $g(x)$.<\/li>\n
    3. Se $f(x)\\neq 0$ e $g(x)=0$, ent\u00e3o o maior divisor comum de $f(x)$ e $g(x)$ \u00e9 $(1\/\\alpha)f(x)$ onde $\\alpha\\in\\F$ \u00e9 o coeficiente l\u00edder de $f(x)$.<\/li>\n<\/ol>\n<\/div>\n
      \n(1) Assuma que $d_1(x)$ e $d_2(x)$ s\u00e3o maiores divisores comuns de $f(x)$ e $g(x)$. Ent\u00e3o $d_1(x)\\mid f(x)$ e $d_1(x)\\mid g(x)$ (segunda propriedade), e assim $d_1(x)\\mid d_2(x)$ (terceira propriedade). Trocando os pap\u00e9is de $d_1(x)$ e $d_2(x)$, obtemos que $d_2(x)\\mid d_1(x)$. Como $\\F$ \u00e9 um corpo (e em particular, $\\F$ \u00e9 um dom\u00ednio), obtemos por um resultado anterior que $d_2(x)=\\beta d_1(x)$ com $\\beta\\in\\F\\setminus\\{0\\}$. Usando a primeira propriedade, temos que $d_1(x)$ e $d_2(x)$ s\u00e3o polin\u00f4mios m\u00f4nicos e temos que $\\beta=1$ e que $d_1(x)=d_2(x)$.<\/p>\n

      (2)-(3) Exerc\u00edcio.<\/p>\n<\/div>\n

      A primeira afirma\u00e7\u00e3o no lema anterior diz que o maior divisor comum, quando existir, \u00e9 \u00fanico. Este fato nos permute escrever o maior divisor comum de dois polin\u00f4mios $f(x),g(x)\\in\\F[x]$ como $\\mdc{f(x)}{g(x)}$. Neste momento n\u00e3o sabemos que o mdc de fato existe, mas provaremos isso usando o mesmo argumento que foi aplicado no caso de n\u00fameros inteiros.<\/p>\n

      \nSejam $f(x),g(x),h(x)\\in\\F[x]$. Temos que existe o mdc de $f(x)$ e $g(x)$ se e somente se existe o mdc de $g(x)$ e $f(x)+h(x)g(x)$. Al\u00e9m disso,
      \n\\[
      \n\\mdc{f(x)}{g(x)}=\\mdc{g(x)}{f(x)+h(x)g(x)}.
      \n\\]<\/div>\n
      \nAssuma primeiro que $d(x)=\\mdc{f(x)}{g(x)}$. Afirmamos que $d(x)$ \u00e9 mdc de $g(x)$ e $f(x)+h(x)g(x)$. Primeiro, $d(x)$ \u00e9 m\u00f4nico, pois ele \u00e9 um mdc. Al\u00e9m disso, $d(x)\\mid g(x)$ e $d(x)\\mid f(x)+h(x)g(x)$. Assuma que $c(x)\\mid g(x)$ e $c(x)\\mid f(x)+h(x)g(x)$ com algum $c(x)\\in\\F[x]$. Ent\u00e3o
      \n\\[
      \nc(x)\\mid (f(x)+h(x)g(x))-h(x)g(x)=f(x);
      \n\\]
      \nou seja $c(x)\\mid f(x)$ e $c(x)\\mid g(x)$. Como $d(x)=\\mdc{f(x)}{g(x)}$ temos que $c(x)\\mid d(x)$. Ent\u00e3o temos que $d(x)=\\mdc{g(x)}{f(x)+h(x)g(x)}$.<\/p>\n

      Para provar a volta, s\u00f3 observe que $f(x)=(f(x)+h(x)g(x))-h(x)g(x)$ e aplique a afirma\u00e7\u00e3o da ida para $f_1(x)=g(x)$, $g_1(x)=f(x)+h(x)g(x)$ e $h_1(x)=-h(x)$.<\/p>\n<\/div>\n

      Usaremos o lema anterior em combina\u00e7\u00e3o com o Teorema de Divis\u00e3o para Polin\u00f4mios.<\/p>\n

      \nSeja $f(x),g(x)\\in\\F[x]$ com $g(x)\\neq 0$. Escreva, usando o Teorema de Divis\u00e3o, $f(x)=q(x)g(x)+r(x)$ onde $r(x)=0$ ou $\\grau{r(x)} < \\grau{g(x)}$. Ent\u00e3o existe mdc de $f(x)$ e $g(x)$ se e somente se existe o mdc de $g(x)$ e $r(x)$ e
      \n\\[
      \n\\mdc{f(x)}{g(x)}=\\mdc{g(x)}{r(x)}.
      \n\\]<\/div>\n
      \nSegue do lema anterior.<\/div>\n

      O resultado anterior implica que o mdc de dois polin\u00f4mios pode ser calculado similarmente ao mdc de dois n\u00fameros inteiros usando o algoritmo de Euclides. O algoritmo funciona na mesma maneira como funcionou para n\u00fameros inteiros. Repetimos a divis\u00e3o de Euclides at\u00e9 o resto fica igual a zero. O processo termina depois de um n\u00famero finito de passos, pois a grau do resto se diminui em cada passo executado. Se $r(x)$ \u00e9 o \u00faltimo resto n\u00e3o nulo, ent\u00e3o $\\alpha^{-1}r(x)$ \u00e9 o mdc de $f(x)$ e $g(x)$ onde $\\alpha$ \u00e9 o coeficiente l\u00edder de $r(x)$. A multiplica\u00e7\u00e3o por $\\alpha^{-1}$ \u00e9 necess\u00e1rio, pois o mdc \u00e9 um polin\u00f4mio m\u00f4nico.<\/p>\n

      O c\u00f3digo do procedimento em Python \u00e9 o seguinte.<\/p>\n

      \nfrom sympy.polys.polytools import LC\ndef MDC(a,b):\n\n    while b != 0:\n        a, b = b, a % b  \n\n    return a\/\/LC(a)\n<\/code>\n<\/pre>\n
      \nSe $f(x),g(x)\\in\\F[x]$ n\u00e3o simultaneamente nulos, ent\u00e3o existe $\\mdc{f(x)}{g(x)}$. Al\u00e9m disso, existem polin\u00f4mios $u(x),v(x)\\in \\F[x]$ tais que
      \n\\[
      \nu(x)f(x)+v(x)g(x)=\\mdc{f(x)}{g(x)}.
      \n\\]<\/div>\n
      \nAmbas afirma\u00e7\u00f5es seguem do algoritmo de Euclides.<\/div>\n
      O Algoritmo Extendido de Euclides que devolve o mdc e os dois polin\u00f4mios $u(x)$ e $v(x)$ no resultado anterior funciona na mesma forma<\/p>\n
      \nfrom sympy.polys.polytools import LC\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    c = LC(a)\n    return a\/\/c, prevu\/\/c, prevv\/\/c\n<\/code>\n<\/pre>\n
      \nDois polin\u00f4mios $f(x),g(x)\\in\\F[x]$ s\u00e3o primos entre si<\/strong> ou coprimos<\/strong> se $\\mdc{f(x)}{g(x)}=1$.<\/div>\n
      \nDois polin\u00f4mios $f(x),g(x)\\in\\F[x]$ s\u00e3o primos entre si se e somente se existem $u(x),v(x)\\in\\F[x]$ tais que
      \n\\[
      \nu(x)f(x)+v(x)g(x)=1.
      \n\\]<\/div>\n
      \nVamos calcular $\\mdc{f(x)}{g(x)}$ onde $f(x)=x^6-2x^2+x-1$ e $g(x)=x^4-1$ em $\\Q[x]$. Primeiro, escrevemos
      \n\\[
      \nf(x)=q_1(x)g(x)+r_1(x)=x^2g(x)+(-x^2+x-1).
      \n\\]
      \nDepois
      \n\\[
      \ng(x)=q_2(x)r_1(x)+r_2(x)=(-x^2-x)r_1(x)+(-x-1).
      \n\\]
      \nNo pr\u00f3ximo passo, obtemos
      \n\\[
      \nr_1(x)=q_3(x)r_2(x)+r_3(x)=(x-2)r_2(x)+(-3).
      \n\\]
      \nFinalmente,
      \n\\[
      \nr_2(x)=q_4(x)r_3(x)+r_4(x)=(1\/3x+1\/3)r_3(x)+0.
      \n\\]
      \nO \u00faltimo resto n\u00e3o nulo foi $-3$ (considerando como um polin\u00f4mio de grau zero). Como o mdc precisa ser um polin\u00f4mio m\u00f4nico,
      \n$$
      \n\\mbox{mdc}(f(x),g(x))=1.
      \n$$
      \nEm particular, $f(x)$ e $g(x)$ s\u00e3o primos entre si.<\/p>\n
      A computa\u00e7\u00e3o pode ser usada tamb\u00e9m para obter que
      \n\\begin{align*}
      \n-3&=r_3(x)=r_1(x)-q_3(x)r_2(x)\\\\&=f(x)-q_1(x)g(x)-q_3(x)(g(x)-q_2(x)r_1(x))\\\\
      \n&=f(x)-q_1(x)g(x)-q_3(x)(g(x)-q_2(x)(f(x)-q_1(x)g(x)))\\\\
      \n&=(1+q_2(x)q_3(x))f(x)+(-q_1(x)-q_3(x)-q_1(x)q_2(x)q_3(x))g(x).
      \n\\end{align*}
      \nCalculando os coeficientes explicitamente, obtemos que
      \n\\[
      \n-3 = (-x^3+x^2+2x+1)f(x)+(x^5-x^4-2x^3-x^2-x+2)g(x)
      \n\\]
      \ne que
      \n\\begin{align*}
      \n&\\mdc{f(x)}{g(x)}=1 \\\\&= \\frac 13(x^3-x^2-2x-1)f(x)-\\frac 13(x^5-x^4-2x^3-x^2-x+2)g(x)
      \n\\end{align*}<\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
      Nesta p\u00e1gina $\\F$ \u00e9 um corpo. Por exemplo, pode tomar $\\Q$, $\\R$, $\\C$, ou $\\Z_p$ ($p$ sendo primo) como $\\F$. Sejam $f(x),g(x)\\in\\F[x]$. Dizemos que $d(x)\\in\\F[x]$ \u00e9 maior divisor comum de $f(x)$ e $g(x)$ se $d(x)$ \u00e9 m\u00f4nico; $d(x)\\mid f(x)$ e $d(x)\\mid g(x)$; se $c(x)\\in\\F[x]$ tal que $c(x)\\mid f(x)$ e $c(x)\\mid g(x)$, ent\u00e3o $c(x)\\mid d(x)$. As … Continue reading O MDC de dois polin\u00f4mios e 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\/1583"}],"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=1583"}],"version-history":[{"count":13,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1583\/revisions"}],"predecessor-version":[{"id":2005,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1583\/revisions\/2005"}],"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=1583"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}