Por: Sebastião Vieira do Nascimento (Sebá)
O objetivo do presente trabalho é apresentar um método, de resolução de equações diofantinas lineares, encontrado nos livros de teoria dos números e, além disso, mostrar alguns casos particulares nas equações diofantinas lineares, que é possível resolver algumas delas por meio do método de Sebá, método esse desenvolvido pelo autor deste trabalho.
Inicialmente iremos apresentar dois teoremas referentes a condição de existência de solução inteira das equações diofantinas lineares, e em seguida apresentar alguns exemplos resolvidos por meio do método de Sebá.
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 inteiros.
Todo par de inteiros x0 e y0 tais que ax0 + by0 = c, diz-se que é 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:
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, quaisquer que sejam os valores inteiros de x e y.
De modo geral, a equação diofantina linear ax + by = c não tem solução em inteiros, sempre que d = mdc (a,b) não divide c.
2 – Condição De Existência De Solução
Teorema 1: A equação diofantina linear ax + by = c tem solução se e somente se d divide c, sendo d = mdc (a,b).
3 – Solução Da Equação ax + by = c
Teorema 2: Se d divide c ou seja (d/c), sendo d = mdc(a,b) e se o par de inteiros x0 e y0 é uma solução particular da equação diofantina linear ax = by = c, então, todas as outras soluções dessa equação são dadas pelas fórmulas:
Sendo t um inteiro arbitrário.
Corolário 1: Se o mdc(a,b) = 1 e se x0 e 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:
Sendo t um inteiro arbitrário.
Se você, caro leitor, estiver interessado em ver as demonstrações dos dois teoremas acima, veja em: http://jogoseducativos.tripod.com.br/diofantina.htm.
4 – Exemplos
O exemplo a seguir e a sua resolução foram extraídos de:
OLIVEIRA, Silvio Barbosa de. As equações diofantinas lineares e o livro didático de matemática para o ensino médio. Mestrado em Educação Matemática, PUC/SP, São Paulo, 2006.
Exemplo 1 – Um laboratório dispõe de 2 máquinas para examinar amostras de sangue. Uma delas examina 15 amostras de cada vez, enquanto a outra examina 25. Pergunta-se: quantas vezes essas máquinas devem ser acionadas para examinar 2.000 amostras?
Resolução:
Designando, por x e y, o número de vezes que a primeira e a segunda máquinas, respectivamente, foram acionadas, basta resolver a seguinte equação diofantina linear para responder à pergunta proposta:
Essa equação é equivalente a:
Como o mdc(5, 3) = 1, logo, essa equação diofantina tem solução.
Tem-se agora que encontrar uma solução particular para 3x + 5y = 400.
Primeiramente, podemos encontrar a solução da equação 3x + 5y = 1, pelo algoritmo de Euclides:
Esse algoritmo permite construir as seguintes expressões:
A partir da expressão (3), obtém-se:
A partir da expressão (4):
Substituindo a (6) na (7), vem:
Aplicando a propriedade distributiva, obtém-se:
A expressão (8) indica que x = 2 e y = –1 é uma solução particular da equação 3x + 5y = 1. Multiplicando ambos os membros da expressão (8) por 400, obtemos:
Logo, 800 e –400 é uma solução particular da equação (2) e também será da equação original (1): 15(800) + 25(–400) = 2000. Consequentemente, a solução geral da equação (1) que apresenta mdc(25, 15) = 5, se expressa por:
Considerando o problema que levou a essa equação, vê-se que só interessam respostas não negativas para x e y. Assim, deve-se impor que:
Sendo assim, temos que:
Substituindo os valores de t em (9) e (10), obtém-se 27 soluções (que apresentam valores de x e y inteiros positivos) para o problema, desde a primeira máquina parada e a outra sendo acionada 80 vezes, até o caso em que a primeira trabalha 130 vezes e a outra só 2 vezes.
Soluções Usando O Método Que Consta Na Dissertação:
5 – Resolução Pelo Método De Sebá
Além da condição de d = mdc(a, b) dividir c, o método de Sebá exige as duas seguintes condições:
a) que a seja diferente de b
b) que a ou b (ou ambos) divida c
Resolvendo o exemplo por meio do método de Sebá
Pelas duas condições, temos:
a) Já que a = 15 e b = 25, logo, a ≠ b
b) Como c = 2000 e b = 25, logo, b/c (b divide c)
Sempre que a > b ou b > a, dividem-se ambos os membros da equação diofantina linear por a ou b.
Como no exemplo b > a, dividindo ambos os membros da (1) por 25, obtém-se:
Como a fração, do coeficiente de x, o denominador é 5, logo, para x = 5, temos:
Logo, x = 5 e y = 77 é uma solução particular da equação (1), e conseqüentemente, a solução geral da equação (1) que apresenta mdc(25, 15) = 5, se expressa por:
Considerando o problema que levou a essa equação, vê-se que só interessam respostas não negativas para x e y. Assim, deve-se impor que:
Sendo assim, então:
Substituindo os valores de t em (13) e (14), obtém-se 27 soluções (que apresentam valores de x e y inteiros positivos) para o problema, desde a primeira máquina parada e a outra sendo acionada 80 vezes, até o caso em que a primeira trabalha 130 vezes e a outra só 2.
Soluções Usando O Método De Sebá
Comparando as duas tabelas, constata-se que as soluções obtidas usando o método que consta na dissertação, são as mesmas soluções obtidas usando o método de Sebá.
Exemplo 2 – Resolver a equação diofantina 3x + 5y = 100.
Resolução:
Como o mdc(5, 3) = 1 e 1/100, logo, a equação tem solução em inteiros. Pelas duas condições do método de Sebá, temos:
a) Já que a = 3 e b = 5, logo, a ≠ b
b) Como c = 100 e b = 5, logo, b/c
Como b > a, dividindo ambos os membros por 5, obtém-se:
Como a fração, do coeficiente de x, o denominador é 5, logo, para x = 5, temos:
Logo, x = 5 e y = 17 é uma solução particular da equação. Consequentemente, a solução geral da equação que apresenta mdc(5, 3) = 1, se expressa por:
Considerando t pertencente aos Reais, existem infinitas soluções inteiras para x e y; sendo apenas 6 não negativas.
Exemplo 3 – Resolver a equação diofantina 3x + 6y = 18
Resolução:
Como o mdc(6, 3) = 3 e 3/18, logo, a equação tem solução em inteiros. Pelas duas condições do método de Sebá, temos:
a) Já que a = 3 e b = 6, logo, a ≠ b
b) Como c = 18, a = 3 e b = 6, logo, ambos dividem c
Como b > a, dividindo ambos os membros por 6, obtém-se:
Como a fração, do coeficiente de x, o denominador é 2, logo, para x = 2, temos:
Logo, x = 2 e y = 2 é uma solução particular da equação. Consequentemente, a solução geral da equação que apresenta mdc(6, 3) = 3, se expressa por:
Considerando t pertencente aos Reais, existem infinitas soluções inteiras para x e y; sendo apenas 3 não negativas.
Exemplo 4 – Um comerciante comprou 30 pássaros: perdizes, pardais e pombos. Um perdiz custa 3 moedas de prata, um pombo 2, e um pardal 1/2. Ele pagou 30 moedas. Quantos pássaros de cada espécie o comerciante comprou? (OUTUBRO 2011 SUPER, pg. 69)
Resolução:
Sejam:
x = perdizes
y = pardais
z = pombo
Temos o seguinte sistema de duas equações lineares
Multiplicando ambos os membros da (19) por –1/2 e somando com a (20), obtém-se:
Multiplicando ambos os membros da (21) por 10, obtém-se:
Como o mdc(25, 15) = 5 e 5/100, logo, a equação (22) tem solução em inteiros. Pelas duas condições do método de Sebá, temos:
a) Já que a = 25 e b = 15, logo, a ≠ b
b) Como c = 150, a = 25 e b = 15, logo, ambos dividem c
Como a > b, dividindo ambos os membros por 25, obtém-se:
Como a fração, do coeficiente de y, o denominador é 5, logo, para y = 5, temos:
Logo, x = 3 e y = 5 é uma solução particular da equação (22). Consequentemente, a solução geral da equação que apresenta mdc(25, 15) = 5, se expressa por:
Considerando o problema que levou a essa equação, vê-se que só interessam respostas não negativas para x e y. Assim, deve-se impor que:
Sendo assim, então:
Considerando t pertencente aos Reais, existem infinitas soluções inteiras para x e y; sendo apenas duas não negativas:
Resposta:
Primeira solução: o comerciante comprou: 3 perdizes, 5 pardais e 22 pombos, totalizando 30 pássaros. O comerciante gastou:
Segunda solução: o comerciante comprou: 6 perdizes, 0 pardais e 24 pombos, totalizando 30 pássaros. O comerciante gastou:
Exemplo 5 – Resolver a equação diofantina linear 39x + 26y = 105.
Resoluçã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.
Conclusão:
Quando os coeficientes (a, b) e o terno independente (c) de uma equação diofantina linear se enquadrar nas duas condições exigidas pelo método de Sebá, este, em termos de tempo computacional, é mais eficiente para encontrar as soluções em inteiros de uma equação diofantina linear do que o método utilizado em teoria dos números.
Este artigo foi cedido gentilmente por Sebastião Vieira do Nascimento (Sebá). Professor Titular (por concurso) aposentado da UFCG – PB.
Veja mais:
A Regra de Sinais de Diofanto
Deserto Entre Números Primos
Quantos Número Primos Existem?
Postar um comentário