EQUAÇÕES DIOFANTINAS LINEARES

EQUAÇÕES DIOFANTINAS LINEARES

1. GENERALIDADE:

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 X₀ ,Y₀ tais que ax₀+by₀=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:

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 x₀,y₀ tais que ax₀+by₀=c. Por ser o mdc(a,b)=d, exitsem inteiros r e s tais que a= dr e b=ds, e temos:

c = ax₀ + by₀ = drx₀ + dsy₀ = d(rx₀ + sy₀)

E como rx₀ + sy₀ é 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 x₀ e y0 tais que d=ax₀+by₀ o que implica:

c = dt = (ax₀ + by₀)t = a(tx₀) + b(ty₀), isto é, o par de inteiros :

x = tx₀ = (c/d)x_0, y = ty₀ = (c/d)y₀ é uma solução da equação ax+by=c.

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

TEOREMA: Se d divide c ou seja ( d|c), sendo d=mdc(a,b) e se o par de inteiros x₀,y₀ é 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 = x₀ + (b/d)t_, y = y_{0 -} (a/d)t onde t é um inteiro arbitrário.

Demonstração: Suponhamos que o par de inteiros x₀, y₀ é uma solução particular da equação ax+by=c, e seja x₁, y₁ uma outra solução qualquer desta equação,. Então, temos : ax₀ + by₀ = c = ax₁ + by₁ e portanto _: a(x₁-x₀) = b(y₀-y₁)

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(x₁-x₀)= s (y₀-y₁). Assim sendo r| s (y₀-y₁), e como o mdc(r,s)=1, segue-se que r|(y₀-y₁), isto é:

y₀ -y₁ = rt e x₁-x₀= st, onde t é um inteiro. Portanto, temos as fórmulas:

x₁= x₀ + st = x₀+ (b/d)t

y₀ = y₁ + rt = y₀ - (a/d)t

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

ax₁ + by₁ = a [x₀ + (b/d)t] + b [y₀ - (a/d)t] = (ax₀ + by₀) + (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 x₀,y₀ é 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 = x₀ + bt y = y₀ - 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:

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

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 x₀ = 500, y₀= -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.

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

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 x₀ = 96, y₀ = -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.

                              iii.            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.

Texto extraído do endereço: http://jogoseducativos.tripod.com.br/diofantina.htm