 |
Até esse ponto, você deve ter se perguntado se existe um método didático e sistemático para encontrar soluções particulares para essas equações, e felizmente existe. Para tal, nós utilizamos o chamado Algoritmo de Euclides de forma estendida. |
O Algoritmo de Euclides Estendido
Um importante processo para se calcular o Máximo Divisor Comum entre dois números é conhecido como o Algoritmo de Euclides. Esse processo é um dos algoritmos mais antigos dos quais se tem conhecimento, datando de cerca de 300 anos A.C. Ele pode ser encontrado no Livro VII da obra “Os Elementos”, de Euclides (sugerimos que dê uma olhadinha nesta página de nossa Biblioteca!). O Algoritmo de Euclides Estendido é uma extensão do algoritmo de Euclides. Dados dois inteiros [tex]a, b\neq 0[/tex], além de calcular [tex]mdc(a,b)[/tex], o algoritmo fornece inteiros [tex]x[/tex] e [tex]y[/tex] tais que [tex]ax + by = mdc(a,b).[/tex]
Algoritmo de Euclides para determinação do MDC.
Selecionamos dois vídeos excelentes para a compreensão do Algoritmo de Euclides Estendido:
Resolvendo Equações Diofantinas Lineares
Vamos relembrar o seguinte resultado, apresentado na sala introdutória:
► Forma geral das soluções:
Se [tex](x_0, y_0)[/tex] for uma solução inteira qualquer da equação diofantina linear [tex]ax + by = c[/tex], então há infinitas soluções, todas elas dadas por:
[tex]\qquad x= x_0 + \dfrac{b}{d} t \ \ \ \text{e} \ \ \ \ y = y_0 -\dfrac{a}{d} t, [/tex]
onde [tex]t [/tex] é um inteiro arbitrário e [tex]d = mdc(a, b)[/tex].
Assim, se uma equação diofantina linear tiver solução, podemos obter uma solução particular utilizando o Algoritmo de Euclides Estendido. As infinitas soluções serão dadas pelo resultado acima.
Para ilustrar o método, considere a seguinte equação:
[tex]\qquad 56x + 72y = 40.[/tex]
Usando o Algoritmo de Euclides, temos:
[tex]\qquad 72=56\times1+16 \ \ \Longrightarrow 16=72−56 \ \ \ \ (I)[/tex]
[tex]\qquad 56=16\times 3+8 \ \ \Longrightarrow 8=56−16\times 3 \ \ \ \ (II)[/tex]
[tex]\qquad 16 = 8 \times 2 + 0.[/tex]
Logo, [tex]mdc(56, 72) = 8[/tex]. Como [tex]8[/tex] é divisor de [tex]40[/tex], a equação possui solução inteira. Daí, substituindo (I) em (II), temos:
[tex]\qquad 8 = 56 − 3 \times 16[/tex]
[tex]\qquad 8 = 56 − 3 \times (72 − 56) [/tex]
[tex]\qquad 8 = 56 − 3 \times 72 + 3 \times 56 [/tex]
[tex]\qquad 8 = 56 \times 4 + 72 \times (−3).[/tex]
Assim, chegamos em uma equação tal que [tex]56m + 72n = 8[/tex], onde [tex]m = 4 [/tex] e [tex]n = −3[/tex]. Porém, como queremos resolver a equação [tex]56x + 72y = 40[/tex], multiplicaremos a última igualdade por [tex]5[/tex]. Assim:
[tex]\qquad 56\times(4\times 5)+72\times(−3\times 5)=8\times 5 [/tex]
[tex]\qquad 56\times 20+72\times (−15)=40.[/tex]
Portanto, encontramos uma solução particular para a equação, sendo ela [tex]x_0 = 20[/tex] e [tex]y_0 = −15[/tex].
Assim, as soluções gerais dessa equação são dadas por [tex]20 + \dfrac{72}{8} t[/tex] e [tex]−15 − \dfrac{56}{8} t[/tex]. Ou seja, temos como conjunto solução geral:
[tex]\qquad S=\{(20+9t, −15−7t):t\in \mathbb{Z}\}.[/tex]
 |
Outra forma de resolver equações diofantinas lineares se dá pela aritmética dos restos, também conhecida como congruência modular. Sugerimos que dê uma passadinha pela Sala de Estudos Aritmética dos Restos, com atenção especial ao tópico IV – Equações Diofantinas. |
“Equações Diofantinas” com Coeficientes Racionais
|
Anteriormente, dissemos que esse tipo de equação apresenta apenas coeficientes inteiros. Surge a dúvida: “É possível solucionar equações da mesma forma, porém com coeficientes racionais?” Eu garanto que a resposta é deveras interessante, e bem mais simples do que parece. Basicamente, basta transformarmos os números racionais em números inteiros através de uma multiplicação! |
 |
Exemplo:
Uma pessoa guarda, em um cofrinho, apenas moedas de [tex]R\$ \ 0,25[/tex] e [tex]R\$ \ 0,10[/tex]. Tendo ao menos [tex]6[/tex] moedas de cada valor, quantas moedas são necessárias, no mínimo, para que ela possa pagar por um livro de exatos [tex]R\$ \ 25,00[/tex], sem pedir troco?
Sejam [tex]x[/tex] a quantidade de moedas de [tex]R\$ \ 0,25[/tex] e [tex]y[/tex] a quantidade de moedas de [tex]R\$ \ 0,10[/tex] a serem dadas como pagamento. A equação que descreve o problema é a seguinte:
[tex]\qquad 0, 25x + 0, 10y = 25.[/tex]
Ademais, perceba que:
[tex]\qquad (0,25x+0,10y)\times 20=25\times 20 \ \Longleftrightarrow \ 5x+2y=500.[/tex]
Logo, basta resolvermos a equação [tex]5x + 2y = 500[/tex], e nós já sabemos fazer isso! Como [tex]mdc(5, 2) = 1[/tex], a equação possui solução. Usando o Algoritmo de Euclides Estendido, temos:
[tex]\qquad 5=2\times 2+1[/tex]
[tex]\qquad 1=5\times 1+2\times (-2)[/tex]
[tex]\qquad (5 \times 1 + 2 \times (−2)) \times 500 = 1 \times 500[/tex]
[tex]\qquad 5\times 500+2\times (−1000)=500.[/tex]
Logo, [tex]x_0 = 500[/tex] e [tex]y_0 = −1000[/tex]. Assim, a solução geral da equação é dada por:
[tex]\qquad x=500+2t, \ \text{com} \ t\in \mathbb{Z}[/tex]
[tex]\qquad y=−1000−5t, \ \text{com} \ t\in \mathbb{Z}.[/tex]
Posto isso, calcularemos os limites possíveis do valor inteiro de [tex] t[/tex] que satisfazem a questão. Para
isso, basta utilizar inequações, onde para os valores de [tex]x \geq 6[/tex] o valor de [tex]t[/tex] é dado por:
[tex]\qquad 500+2t\geq 6[/tex]
[tex]\qquad 2t \geq −494[/tex]
[tex]\qquad t\geq−247[/tex] (lembrando que [tex] t[/tex] é um número inteiro).
Analogamente, para os valores de [tex]y \geq 6[/tex], temos:
[tex]\qquad −1000−5t\geq 6[/tex]
[tex]\qquad -5t \geq 1006[/tex]
[tex]\qquad t \leq −\dfrac{1006}{5}[/tex]
[tex]\qquad t \leq−201,2[/tex]
[tex]\qquad t \leq−202[/tex] (lembrando que [tex] t[/tex] é um número inteiro).
Além disso, o número total de moedas é
[tex]\qquad x+y=-500-3t.[/tex]
Assim, devemos ter [tex]−247\leq t \leq−202[/tex] e, para que o total [tex]-500-3t[/tex] de moedas seja mínimo, [tex]t[/tex] deverá ser o maior possível. Logo, devemos fazer [tex]t=-202[/tex], o que fornece
[tex]\qquad x=500+2\times(−202)= 96 \ \text{moedas}[/tex]
[tex]\qquad y=−1000−5\times (−202)= 10 \ \text{moedas}.[/tex]
Por fim, a resposta é dada por [tex] x = 96[/tex] moedas de [tex]R\$ \ 0,25[/tex] e [tex]y = 10[/tex] moedas de [tex]R\$ \ 0,10[/tex], em um total de [tex]106[/tex] moedas.
COM Phidias (EEEFM Maestro José Siqueira – Conceição, PB)
Equipe COM – OBMEP