16/12/2011

Método de Sebá para Resolução Alguns Casos Particulares Nas Equações Diofantinas Lineares

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:

clip_image002

clip_image004

clip_image006

clip_image008

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:

clip_image010

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:

clip_image012

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:

clip_image014

Essa equação é equivalente a:

clip_image016

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:

image Esse algoritmo permite construir as seguintes expressões:

clip_image018

clip_image020

clip_image022

A partir da expressão (3), obtém-se:

clip_image024

A partir da expressão (4):

clip_image026

Substituindo a (6) na (7), vem:

clip_image028

Aplicando a propriedade distributiva, obtém-se:

clip_image030

clip_image032

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:

clip_image034

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:

clip_image036

clip_image038

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:

clip_image040

clip_image042

clip_image044

clip_image046

clip_image048

clip_image050

Sendo assim, temos que:

clip_image052

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:

image 

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, ab

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:

clip_image054

Como a fração, do coeficiente de x, o denominador é 5, logo, para x = 5, temos:

clip_image056

clip_image058

clip_image060

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:

clip_image062

clip_image064

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:

clip_image066

clip_image068

Sendo assim, então:

clip_image070

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á

image 

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, ab

b) Como c = 100 e b = 5, logo, b/c

Como b > a, dividindo ambos os membros por 5, obtém-se:

clip_image072

Como a fração, do coeficiente de x, o denominador é 5, logo, para x = 5, temos:

clip_image074

clip_image076

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:

clip_image078

clip_image080

Considerando t pertencente aos Reais, existem infinitas soluções inteiras para x e y; sendo apenas 6 não negativas.

clip_image082

clip_image084

clip_image086

clip_image088

clip_image090

clip_image092

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, ab

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:

clip_image094

Como a fração, do coeficiente de x, o denominador é 2, logo, para x = 2, temos:

clip_image096

clip_image098

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:

clip_image100

clip_image102

Considerando t pertencente aos Reais, existem infinitas soluções inteiras para x e y; sendo apenas 3 não negativas.

clip_image104

clip_image106

clip_image108

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

clip_image110

clip_image112

Multiplicando ambos os membros da (19) por –1/2 e somando com a (20), obtém-se:

clip_image114

Multiplicando ambos os membros da (21) por 10, obtém-se:

clip_image116

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, ab

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:

clip_image118

Como a fração, do coeficiente de y, o denominador é 5, logo, para y = 5, temos:

clip_image120

clip_image122

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:

clip_image124

clip_image126

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:

clip_image128

clip_image130

Sendo assim, então:

clip_image132

Considerando t pertencente aos Reais, existem infinitas soluções inteiras para x e y; sendo apenas duas não negativas:

clip_image134

clip_image136

clip_image138

clip_image140

clip_image142

clip_image144

Resposta:

Primeira solução: o comerciante comprou: 3 perdizes, 5 pardais e 22 pombos, totalizando 30 pássaros. O comerciante gastou:

clip_image146

Segunda solução: o comerciante comprou: 6 perdizes, 0 pardais e 24 pombos, totalizando 30 pássaros. O comerciante gastou:

clip_image148

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?

0 Comentários:

Postar um comentário

Por favor, leiam antes de comentar:

▪ Escreva um comentário apenas referente ao tema;

▪ Para demais, utilize o formulário de contato;

▪ Comentários ofensivos ou spans não serão publicados;

▪ Desde o dia 23/07/2013, todos os comentários passaram a ser moderados. Para maiores detalhes, veja a nota de moderação aqui;

▪ É possível escrever fórmulas em $\LaTeX$ nos comentários deste blog graças a um script da Mathjax. Para fórmulas inline ou alinhadas à esquerda, escreva a fórmula entre os símbolos de $\$$; Para fórmulas centralizadas, utilize o símbolo duplo $\$\$$.

Por exemplo, a^2 + b^2 = c^2 entre os símbolos de $\$\$$, gera:
$$a^2+b^2=c^2$$
▪ Para visualizar as fórmulas em $\LaTeX$ antes de publicá-las, acessem este link.

Redes Sociais

Arquivo do Blog

Related Posts Plugin for WordPress, Blogger...