EQUAÇÕES DIOFANTINAS LINEARES

  1. GENERALIDADE:

    2. O tipo mais simples de equações diofantinas é a equação diofantina linear com duas incógnitas x e y. Onde ax + by = c sendo a, b e c são inteiros dados, sendo ab ¹ 0.

    Todo par de inteiros X0 ,Y0 tais que ax0+by0=c diz se uma solução inteira ou apenas uma solução da equação ax + by = c. Seja, por exemplo, a equação diofantina linear com duas incógnitas:

    3x+6y=18, temos

    3.(4)+6.(1)=18

    3.(-6)+6.(6)=18

    3.(10)+6.(-2)=18, Logo, os pares de inteiros: 4 e 1, -6 e 6, 10 e -2 são soluções da equação 3x+6y=18.

    Existem equações diofantinas lineares com duas incógnitas que não tem solução. Assim, por exemplo, a equação diofantina linear: 2x+4y=7 não tem solução, porque 2x+4y é um inteiro par quaisquer que sejam os valores inteiros de x e y, enquanto que 7 é um inteiro ímpar ( observe que 2 = mdc(2,4), não divide 7)

    De modo geral, a equação diofantina linear ax+by=c não tem solução todas as vezes que d = mdc (a,b) não divide c.

  2. CONDIÇÃO DE EXISTÊNCIA DE SOLUÇÃO:

    3. TEOREMA: A equação diofantina linear ax+by=c tem solução se e somente se d divide c, sendo d= mdc (a,b).

    Demonstração: ( ===> ) Suponha que a equação ax+by=c tem uma solução, isto é, que existe um par de inteiros x0,y0 tais que ax0+by0=c. Por ser o mdc(a,b)=d, exitsem inteiros r e s tais que a= dr e b=ds, e temos:

    c = ax0 + by0 = drx0 + dsy0 = d(rx0 + sy0)

    E como rx0 + sy0 é um inteiro, segue-se que d divide c ( d|c).

    ( <=== ) Reciprocamente, suponhamos que d divide c (d|c), ito é, que c= dt, onde t é um inteiro. Por ser o mdc(a,b)=d, existem inteiros x0 e y0 tais que d=ax0+by0 o que implica:

    c = dt = (ax0 + by0)t = a(tx0) + b(ty0), isto é, o par de inteiros :

    x = tx0 = (c/d)x0, y = ty0 = (c/d)y0 é uma solução da equação ax+by=c.

  3. SOLUÇÃO DA EQUAÇÃO ax + by = c.

    4. TEOREMA: Se d divide c ou seja ( d|c), sendo d=mdc(a,b) e se o par de inteiros x0,y0 é uma solução particular da equação diofantina linear ax = by=c, então todas as outras soluções desta equação são dadas pelas fórmulas:

    x = x0 + (b/d)t, y = y0 - (a/d)t onde t é um inteiro arbitrário.

    Demonstração: Suponhamos que o par de inteiros x0, y0 é uma solução particular da equação ax+by=c, e seja x1, y1 uma outra solução qualquer desta equação,. Então, temos : ax0 + by0 = c = ax1 + by1 e portanto : a(x1-x0) = b(y0-y1)

    Por ser o mdc(a,b)=d, existem inteiros r e s tais que a= dr e b= ds, com r e s primos entre si. Substituindo estes valores de a e b na igualdade anterior e cancelando o fator com d, obtemos: r(x1-x0)= s (y0-y1). Assim sendo r| s (y0-y1), e como o mdc(r,s)=1, segue-se que r|(y0-y1), isto é:

    y0 -y1 = rt e x1-x0= st, onde t é um inteiro. Portanto, temos as fórmulas:

    x1= x0 + st = x0+ (b/d)t

    y0 = y1 + rt = y0 - (a/d)t

    Estes valores de x1 e y1 satisfazem realmente a equação ax+by=c, qualquer que seja o inteiro t, pois temos:

    ax1 + by1 = a [x0 + (b/d)t] + b [y0 - (a/d)t] = (ax0 + by0) + (ab/d - ab/d)t = c+0.t = c

    Como se vê, se d= mdc(a,b) divide c (d|c), então a equação diofantina linear ax+ by = c admite um número infinito de soluções, uma para cada valor do inteiro arbitrário t.

    COROLÁRIO : Se o mdc(a,b)=1 e se x0,y0 é uma solução particular da equação diofantina linear ax+by=c, então todas as outras soluções desta equação são dadas pelas fórmulas: x = x0 + bt y = y0 - at onde t é um inteiro arbitrário.

    NOTA: Uma solução da equação diofantina linear se obtém por tentativa ou pelo ALGORITMO DE EUCLIDES.

  4. EXERCÍCIOS RESOLVIDOS:

    1. Determinar todas as soluções da equação diofantina linear ; 172x + 20y = 1000

      2. Solução: Determinamos inicialmente o mdc(172,20) pelo algoritmo de Euclides:

      172 = 20 * 8 + 12

      20 = 12 * 1 + 8

      12 = 8 * 1 + 4

      8 = 4 * 2

      Portanto, o mdc(172,20)= 4 e como 4|1000, segue-se que a equação dada tem solução. Cabe-nos obter a expressão do inteiro 4 como combinação linear de 172 e 20, para que o que basta eliminar sucessivamente os restos 8 e 12 entre as três primeiras igualdades anteriores do seguinte modo:

      4 = 12 - 8 = 12 (20 - 12) = 2 * 12 - 20 = 2 (172 - 20 * 8) - 20 = 172 * 2 + 20 (-17), isto é

      4 = 172 * 2 + 20 * (-17), multiplicando ambos os membros desta igualdade por 1 000/4 = 250, obtemos:

      1000 = 172 * 500 + 20 (-4250) Portanto, o par de inteiros x0 = 500, y0= -4250 é uma solução particular da equação proposta, e todas as outras soluções são dadas pelas fórmulas:

      x = 500 + (20/4)t = 500 + 5t y = -4250 - (172/4)t = -4250 - 43t, onde t é um inteiro arbitrário.

    2. Determinar todas as soluções inteiras e positivas da equação diofantina linear 18x + 5y = 48

      3. Solução: Determinamos inicialmente o mdc(18,5) pelo algoritmo de Euclides:

      3

      1

      1

      2

      18

      5

      3

      2

      1

      3

      2

      1

      0

      18 = 5 * 3 + 3

      5 = 3 * 1 + 2

      3 = 2 * 1 + 1

      2 = 1 * 2

      Portanto, o mdc(18,5)=1 e a equação dada tem solução. E para exprimir 1 como combinação linear de 18 e 5 basta eliminar os restos 2 e 3 entre as três primeiras igualdades anteriores do seguinte modo:

      1 = 3 - 2 = 3 - ( 5 - 3) = 2 * 3 - 5 = 2 ( 18 - 5 * 3) - 5 = 18 * 2 + 5 (-7), isto é:

      1= 18.(2)+ 5.(-7), multiplicando os termos por 48, obtemos: 48=18.(96) + 5 (-336), logo, o par de inteiros x0 = 96, y0 = -336 é uma solução particular da equação proposta, e todas as demais soluções são dadas pelas fórmulas: x = 96 + 5t e y = -336 - 18t, onde t é um inteiro arbitrário. As soluções inteiras e positivas se acham escolhendo t de modo que sejam satisfeitas as desigualdades:

      96 + 5t > 0 è t < -19/5 e -336 - 18t > 0 è t < -336/18 implicando t = -19 e, portanto x = 96 + 5 (-19 ) = 1 e y = -336 - 18 (-19) = 6. Assim, o par de inteiros x = 1, y = 6 é a única solução inteira e positiva da equação 18x + 5y = 48.

    3. Resolver a equação diofantina linear 39x + 26y = 105

Solução: O mdc(39,26)=13 e como 13 não divide 105, segue-se que a equação dada não tem solução.