{"id":1381,"date":"2021-11-07T20:48:10","date_gmt":"2021-11-07T23:48:10","guid":{"rendered":"http:\/\/localhost\/?page_id=1381"},"modified":"2023-01-06T14:45:05","modified_gmt":"2023-01-06T17:45:05","slug":"equacoes-lineares-diofantinas-em-duas-variaveis","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/equacoes-lineares-diofantinas-em-duas-variaveis\/","title":{"rendered":"Equa\u00e7\u00f5es lineares diofantinas em duas vari\u00e1veis"},"content":{"rendered":"
\nUma equa\u00e7\u00e3o linear diofantina em duas vari\u00e1veis tem a seguinte forma geral:
\n\\[
\nax+by=c
\n\\]
\nonde $a,b,c\\in\\Z$. As vari\u00e1veis da equa\u00e7\u00e3o s\u00e3o $x$ e $y$, os n\u00fameros $a$, $b$, $c$ s\u00e3o par\u00e2metros. O termo “diofantina” refere-se ao fato que n\u00f3s procuramos as solu\u00e7\u00f5es no conjunto dos n\u00fameros inteiros. Por exemplo
\n\\[
\n5x+6y=-2
\n\\]
\n\u00e9 uma equa\u00e7\u00e3o linear diofantina em duas vari\u00e1veis. As poss\u00edveis solu\u00e7\u00f5es da equa\u00e7\u00e3o  s\u00e3o n\u00fameros inteiros.<\/p>\n

Dado uma equa\u00e7\u00e3o diofantina $ax+by=c$, n\u00f3s queremos achar respostas principalmente \u00e0s seguintes tr\u00eas perguntas:<\/p>\n

    \n
  1. A equa\u00e7\u00e3o possui solu\u00e7\u00f5es? (Vamos considerar apenas solu\u00e7\u00f5es inteiras.)<\/li>\n
  2. Se sim, ache uma solu\u00e7\u00e3o particular.<\/li>\n
  3. Ache a solu\u00e7\u00e3o geral; ou seja, o conjunto de todas as solu\u00e7\u00f5es.<\/li>\n<\/ol>\n
    Considere a equa\u00e7\u00e3o $5x-15y=6$. Observamos que o MDC dos coeficientes $5$ e $-15$ \u00e9 igual a $5$. Portanto, quaisquer que sejam os n\u00fameros $x,y\\in\\Z$, o n\u00famero  $5x-15y$ ser\u00e1 divis\u00edvel por $5$. Por outro lado, $5$ n\u00e3o divide o n\u00famero $6$ e obtemos que esta equa\u00e7\u00e3o n\u00e3o possui solu\u00e7\u00f5es.<\/div>\n
    Considere a equa\u00e7\u00e3o
    \n\\[
    \n21x-15y=12.
    \n\\]
    \nNeste caso, $\\mdc {21}{-15}=3$ divide 12. De fato vamos ver que esta equa\u00e7\u00e3o possui solu\u00e7\u00f5es e n\u00f3s vamos determinar o conjunto de todas as solu\u00e7\u00f5es.<\/p>\n

    Primeiro vamos achar uma solu\u00e7\u00e3o particular da equa\u00e7\u00e3o
    \n\\[
    \n21x-15y=\\mdc {21}{-15}=3.
    \n\\]
    \nSabe-se do Algoritmo de Euclides que esta equa\u00e7\u00e3o possui solu\u00e7\u00e3o inteira. De fato, usando o Algoritmo de Euclides, fazemos a seguinte sequ\u00eancia de divis\u00f5es:
    \n\\begin{eqnarray*}
    \n21&=&1\\cdot 15+6;\\\\
    \n15&=&2\\cdot 6+3;\\\\
    \n6&=&2\\cdot 3+0.
    \n\\end{eqnarray*}
    \nObtemos ent\u00e3o que $\\mdc {21}{-15}=3$. Al\u00e9m disso, considerando as equa\u00e7\u00f5es acima,
    \n\\begin{eqnarray*}
    \n6&=&21-15;\\\\
    \n3&=&15-2\\cdot 6=15-2\\cdot(21-15)=-2\\cdot 21+3\\cdot 15.
    \n\\end{eqnarray*}
    \nObtivemos ent\u00e3o que
    \n\\[
    \n21\\cdot(-2)-15\\cdot(-3)=3.
    \n\\]
    \nAgora multiplicamos a equa\u00e7\u00e3o acima por $4$ e obtemos que
    \n\\[
    \n21\\cdot(-8)-15\\cdot(-12)=12.
    \n\\]
    \nObtivemos que o par $(x_0,y_0)=(-8,-12)$ \u00e9 uma solu\u00e7\u00e3o particular da equa\u00e7\u00e3o $21x-15y=12$.<\/p>\n

    Vamos agora determinar a solu\u00e7\u00e3o geral da equa\u00e7\u00e3o; ou seja, vamos determinar o conjunto de todas as solu\u00e7\u00f5es. A ideia \u00e9 a seguinte: se $x_1,y_1\\in\\Z$ s\u00e3o tais que
    \n\\[
    \n21x_1-15y_1=0,
    \n\\]
    \nent\u00e3o $(x_0+x_1,y_0+y_1)$ \u00e9 uma outra solu\u00e7\u00e3o da equa\u00e7\u00e3o original e de fato todas as solu\u00e7\u00f5es podem ser obtidas nesta forma.  Esta \u00faltima equa\u00e7\u00e3o \u00e9  equivalente a equa\u00e7\u00e3o
    \n\\[
    \n7x_1=5y_1;
    \n\\]
    \nou seja,
    \n\\[
    \ny_1=\\frac{7 x_1}{5}.
    \n\\]
    \nComo queremos obter apenas as solu\u00e7\u00f5es inteiras, e $\\mdc 75=1$, uma solu\u00e7\u00e3o $x_1$ precisa ser divis\u00edvel por $5$. Ent\u00e3o $x_1=5k$ para algum $k\\in\\Z$ e isto d\u00e1 $y_1=7k$. \u00c9 f\u00e1cil verificar que se $k\\in\\Z$, o par $(x_1,y_1)=(5k,7k)$ \u00e9 de fato uma solu\u00e7\u00e3o da equa\u00e7\u00e3o $21x_1-15y_1=0$. Portanto o conjunto das solu\u00e7\u00f5es da equa\u00e7\u00e3o
    \n\\[
    \n21x_1-15y_1=0
    \n\\]
    \n\u00e9 dado por
    \n\\[
    \n\\{(x_1,y_1)=(5k,7k)\\mid k\\in \\Z\\}.
    \n\\]
    \nFinalmente, obtemos o conjunto das solu\u00e7\u00f5es (ou seja, a solu\u00e7\u00e3o geral) da equa\u00e7\u00e3o
    \n\\[
    \n21x-15y=12
    \n\\]
    \ncomo
    \n\\[
    \n(x,y)=(-8+5k,-12+7k)\\quad\\mbox{onde}\\quad k\\in\\Z.
    \n\\]<\/p>\n<\/div>\n

    A conta que fizemos nos \u00faltimos dois exemplos pode ser feita simbolicamente com uma equa\u00e7\u00e3o geral na forma $ax+by=c$. Isto nos leva ao seguinte teorema.<\/p>\n

    \nConsidere uma equa\u00e7\u00e3o diofantina na forma
    \n\\[
    \nax+by=c
    \n\\]
    \nonde $a,b,c\\in\\Z$ e $(a,b)\\neq (0,0)$. Seja $d=\\mdc ab$.<\/p>\n
      \n
    1. Se $d\\nmid c$ ent\u00e3o a equa\u00e7\u00e3o n\u00e3o possui solu\u00e7\u00e3o inteira.<\/li>\n
    2. Se $d\\mid c$ ent\u00e3o a equa\u00e7\u00e3o possui infinitas solu\u00e7\u00f5es. Seja $(x_0.y_0)$ uma solu\u00e7\u00e3o particular (que pode ser obtida pelo Algoritmo de Euclides). Ent\u00e3o a solu\u00e7\u00e3o geral da equa\u00e7\u00e3o est\u00e1 dada por
      \n\\[
      \n(x,y)=\\left(x_0+k \\frac bd,y_0-k\\frac ad\\right)\\quad \\mbox{onde}\\quad k\\in\\Z.
      \n\\]<\/li>\n<\/ol>\n<\/div>\n
      \n(1) Seja $d=\\mdc ab$. Note que $d\\mid ax+by$ para todo $x,y\\in \\Z$. Portanto, se $d\\nmid c$, ent\u00e3o n\u00e3o existem $x,y\\in\\Z$ tais que $ax+by=c$ e a equa\u00e7\u00e3o n\u00e3o possui solu\u00e7\u00f5es inteiras.<\/p>\n

      (2) Assuma agora que $d\\mid c$. Sabemos pelo algoritmo de Euclides que existem $x_1,y_1\\in\\Z$ tais que
      \n\\[
      \nax_1+by_1=d.
      \n\\]
      \nTomando $x_0=x_1c\/d$ e $y_0=y_1c\/d$, obtemos que $x_0,y_0\\in\\Z$ e
      \n\\[
      \nax_0+by_0=ax_1c\/d+by_1c\/d=(ax_1+by_1)c\/d=c.
      \n\\]<\/p>\n

      Vamos verificar agora que a express\u00e3o $(x,y)$ acima d\u00e1 a solu\u00e7\u00e3o geral da equa\u00e7\u00e3o. Primeiro afirmamos que o par $(x,y)$ dado acima \u00e9 uma solu\u00e7\u00e3o da equa\u00e7\u00e3o para $ax+by=c$ para todo $k\\in\\Z$. De fato, substituindo, obtemos que
      \n\\begin{align*}
      \nax+by&=a(x_0+kb\/d)+b(y_0-ka\/d)\\\\&=ax_0+by_0+akb\/d-bka\/d=c.
      \n\\end{align*}
      \nAgora resta mostrar que toda solu\u00e7\u00e3o da equa\u00e7\u00e3o est\u00e1 na forma dada pelo teorema. Assuma que $(x_1,y_1)\\in\\Z\\times \\Z$ \u00e9 uma solu\u00e7\u00e3o da equa\u00e7\u00e3o. Ent\u00e3o
      \n\\[
      \nax_1+by_1=ax_0+by_0=c,
      \n\\]
      \nou seja
      \n\\[
      \na(x_1-x_0)=b(y_0-y_1).
      \n\\]
      \nA \u00faltima equa\u00e7\u00e3o pode ser dividido por $d$ e obtemos que
      \n\\[
      \n\\frac ad(x_1-x_0)=\\frac bd(y_0-y_1).
      \n\\]
      \nNote que $\\mdc {a\/d}{b\/d}=1$ e isso implica que $x_1-x_0=k(b\/d)$; ou seja
      \n\\[
      \nx_1=x_0+k\\frac bd
      \n\\]
      \ncom algum $k\\in\\Z$. Daqui, tem-se que
      \n\\[
      \ny_0-y_1=\\frac{a(x_1-x_0)}b=\\frac{akb}{db}=\\frac{ak}d;
      \n\\]
      \nou seja
      \n\\[
      \ny_1=y_0-k\\frac ad.
      \n\\]
      \nConsequentemente
      \n\\[
      \n(x_1,y_1)=\\left(x_0+k\\frac bd,y_0-k\\frac ad\\right)
      \n\\]
      \ncomo foi afirmado.<\/p>\n<\/div>\n

      Vamos ver como implementar o procedimento na linguagem Python. Primeiro, precisamos de uma nova vers\u00e3o da fun\u00e7\u00e3o XMDC que aceita tamb\u00e9m n\u00fameros negativos.<\/p>\n

      \n# algoritmo extendido de Euclides\ndef XMDC(a,b):\n\n    assert a != 0 or b != 0 \n\n    # n\u00f3s trabalhamos com n\u00fameros positivos, mas aceitamos argumentos negativos\n    sign_a, sign_b = 1, 1\n    if a < 0: \n        a, sign_a = -a, -1\n    \n    if b < 0: \n        b, sign_b = -b, -1\n        \n    prevu, u = 1, 0; prevv, v = 0, 1 \n    # r_{-1} = a = 1*a + 0*b, r_0 = b = 0*a + 1*b\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, sign_a*prevu, sign_b*prevv\n<\/code>\n<\/pre>\n
      Ora, o procedimento apresentado na demonstra\u00e7\u00e3o do teorema acima pode ser implementado com a seguinte fun\u00e7\u00e3o.<\/p>\n
      \n# Resolver a equa\u00e7\u00e3o ax + by = c\ndef ResolvaDiofantina( a, b, c ):\n    \n    d, x0, y0 = XMDC( a, b )\n    \n    # verificar se a equa\u00e7\u00e3o tem solu\u00e7\u00e3o\n    if c % d != 0:\n        return false\n    \n    # obter uma solu\u00e7\u00e3o particular\n    # temos x0*a + y0*b = d\n    x0, y0 = x0*c\/\/d, y0*c\/\/d\n    \n    # sol(k) \u00e9 a solu\u00e7\u00e3o com par\u00e1metro k\n    sol = lambda k : (x0+k*b\/\/d, y0-k*a\/\/d)\n    \n    return sol\n<\/code>\n<\/pre>\n
      Note que quando a equa\u00e7\u00e3o possui solu\u00e7\u00f5es, ela vai possuir infinitas solu\u00e7\u00f5es, mas a fun\u00e7\u00e3o claramente n\u00e3o pode devolver uma lista infinita. Portanto, a fun\u00e7\u00e3o acima devolve uma express\u00e3o lambda (ou fun\u00e7\u00e3o lambda) que depende de um par\u00e2metro $k$ e para cada $k\\in\\Z$ devolve uma solu\u00e7\u00e3o da equa\u00e7\u00e3o e todas as solu\u00e7\u00f5es podem ser obtidas assim. Resolvemos por exemplo a equa\u00e7\u00e3o
      \n\\[
      \n13x + 9y = 1
      \n\\]
      \nusando nossa fun\u00e7\u00e3o.<\/p>\n
      \n# 13*x + 9*y = 1\n>>> sol = ResolvaDiofantina( 13, 9, 1 )\n>>> sol(-9)\n(-83, 120)\n<\/code>\n<\/pre>\n
      A computa\u00e7\u00e3o acima mostra que $(-83,120)$ \u00e9 uma solu\u00e7\u00e3o particular.<\/p>\n
      Podemos tamb\u00e9m gerar as solu\u00e7\u00f5es da equa\u00e7\u00e3o para os valores $k\\in\\{-5,\\ldots,5\\}$ com o seguinte c\u00f3digo<\/p>\n
      \n>>> lista_sols = [ sol( k ) for k in range(-5, 6 )]\n>>> lista_sols\n[(-47, 68),\n (-38, 55),\n (-29, 42),\n (-20, 29),\n (-11, 16),\n (-2, 3),\n (7, -10),\n (16, -23),\n (25, -36),\n (34, -49),\n (43, -62)]\n<\/code>\n<\/pre>\n
      Cada par da lista em cima \u00e9 uma solu\u00e7\u00e3o de equa\u00e7\u00e3o diofantina $13x + 9y = 1$.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
      Uma equa\u00e7\u00e3o linear diofantina em duas vari\u00e1veis tem a seguinte forma geral: \\[ ax+by=c \\] onde $a,b,c\\in\\Z$. As vari\u00e1veis da equa\u00e7\u00e3o s\u00e3o $x$ e $y$, os n\u00fameros $a$, $b$, $c$ s\u00e3o par\u00e2metros. O termo “diofantina” refere-se ao fato que n\u00f3s procuramos as solu\u00e7\u00f5es no conjunto dos n\u00fameros inteiros. Por exemplo \\[ 5x+6y=-2 \\] \u00e9 uma equa\u00e7\u00e3o linear … Continue reading Equa\u00e7\u00f5es lineares diofantinas em duas vari\u00e1veis<\/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\/1381"}],"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=1381"}],"version-history":[{"count":8,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1381\/revisions"}],"predecessor-version":[{"id":1984,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1381\/revisions\/1984"}],"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=1381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}