Na matemática, uma equação diofantina linear é uma equação envolvendo soma de variável ou constante, que só podem assumir valores inteiros. As equações diofantinas possuem menos equações do que variáveis e a sua solução envolve descobrir números inteiros que satisfaçam as equações.
Problema 1 Um cachecol custa, na Rússia, 19 rublos, mas o caso é que o comprador só tem notas de 3, e o caixa, só de 5. Nessas condições, será possível pagar a importância da compra, e de que modo?
Podemos traduzir o seguinte problema para a seguinte equação diofantina 3x – 5y = 19 que possui infinitas soluções inteiras e positivas. A compra pode ser feita utilizando 8 notas de 3 rublos e recebendo 1 nota de 5 rublos de troco. Podemos descrever a solução da seguinte maneira:
3x = 19 + 5y
3x = 19 mod 5
3x = 4 mod 5
x = 8 + 5n , n ∈N
|
5y = 3x – 19
5y = -19 mod 3
5y = 2 mod 3
y = 1 + 3n , n ∈N
|
Exercício 1 Propõe-se a uma pessoa que multiplique a data do dia do seu nascimento, por 12, e o número que indica o mês correspondente, por 31. Com a soma desses produtos é possível calcula a data de aniversário da dita pessoa. Considere, por exemplo, se a pessoa nasceu em 08 de fevereiro:
8*12 = 96 , 2*31 = 62; 96 + 62 = 158.
Como podemos deduzir a data de nascimento da pessoa?
Problema 2 Quantas quadras de basquete e quantas de vôlei são necessárias para que 80 alunos joguem simultaneamente? E se forem 77? Sabendo que o basquete e vôlei são jogados, respectivamente, por duas equipes com 5 e 6 jogadores em cada uma.
A equação que descreve a solução desse problema é 10x + 12y = 80.
10x = 80 – 12y
10x = 80 mod 12
10x = 8 mod 12
x = 8 e y = 0
|
12y = 80 – 10x
12y = 0 mod 10
y = 5 , x = 2
|
A segunda equação 10x + 12y = 77 não tem soluções inteiras.
Problema 3: Para agrupar 13 aviões em filas de 3 ou de 5, quantas filas serão necessárias de cada tipo?
A equação diofantina que traduz o problema é 3x + 5y = 13.
3x = 13 – 5y
3x = 13 mod 5
3x = 3 mod 5
x=1, y=2
|
5y = 13 – 3x
5y = 13 mod 3
5y = 1 mod 3
y=2, x=1
|
Esta equação possui uma única solução.
Resultados de divisibilidade:
· Se um número inteiro d|a, então d|am, para qualquer inteiro m;
· Se d|a e d|b, então d|a+b
· (Teorema de Bézout) Se mdc(a,b) = d, então existem inteiros m e n tais que d = am+bn.
O teorema de Bézout nos oferece um método para descobrir se uma equação diofantina tem ou não solução. A equação ax + by = c tem admite solução?
(1) Se c = mdc(a,b), a equação ax + by = c tem solução x = m e y = n do teorema de Bézout.
(2) Se c = dt, onde d = mdc(a,b) e t é um número inteiro, existem inteiros m e n tais que am+bn= d. Assim, c = dt = (am+bn)t = a(mt) + (bn)t , a solução será x = mt e y = nt.
Podemos enunciar o seguinte teorema:
Teorema Uma equação diofantina ax+by=c , em que a != 0 e b !=0, admite solução se, e somente se, d = mdc(a,b) | c.
Exemplo
10x + 12y = 77 não tem soluções inteiras.
d = mdc(10,12) = 2 não divide 77
10x+12y = 80 tem soluções inteiras.
d = mdc(10,12) = 2 | 80
Como encontrar os números inteiros m e n tais que d = am + bn, onde d = mdc(a,b)?
Um modo de encontrar esses números m e n é através do algoritmo de Euclides para o cálculo do mdc(a,b).
Se a e b são inteiros, com b > 0, existem q e r, com 0<=r<b tais que a = bq + r (algoritmo da divisão). Supondo que x|a e x|b então x | r = a - bq (combinação linear de a e b). Da mesma maneira, se x|b e x|r então x| a = bq + r (combinação linear de b e r). Logo, mdc(a,b) se reduz a encontrar mdc(b,r).
Supondo que rn seja o primeiro resto nulo temos:
mdc(a,b) = mdc(b,r1) = mdc(r1,r2) = … = mdc(rn-1,rn) = rn-1.
a = bq1 + r1 (r1 = a-bq1)
b = r1q2 + r2 (r2 = b – (a-bq1)q2 = b – aq2 + bq1q2 )
….
rn-1 = rnqn (mdc(a,b)=rn-1 = am + bn , m e n inteiros)
Através de um processo de substituição, podemos encontrar o valor de m e n.
(1) 120 = 23*5 + 5
(2) 23 = 5*4 + 3
(3) 5 = 3*1 + 2
(4) 3 = 2*1 + 1
(5) 2 = 1*2 + 0
(1) 5 = 1*120 - 5*23
(2) 3 = 1*23 - 4*5 Substituindo o 5 temos
3 = 1*23 - 4*(1*120 - 5*23)
3 = -4*120 + 21*23
(3) 2 = 1*5 - 1*3 Substituindo o valor de 5 e 3 temos
2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)
2 = 5*120 - 26*23
(4) 1 = 1*3 - 1*2 Novamente substituindo 3 e 2
1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)
1 = -9*120 + 47*23
portanto, m = -9 e n = 47 e temos MDC(120,23) = 120 * ( − 9) + 47 * 23
Algoritmo de Euclides Estendido – Versão 1
int mdc(int a, int b, int *m, int *n) {
int mm, nn, d;
if(b==0) {
*m=1; *n=0;
return a;
}
d = mdc(b, a%b, &xx, &yy);
*m = nn; *n = mm - a/b*nn;
return d;
}
Algoritmo de Euclides Versão 2
int eMcd (int a, int b, int *m, int *n){
int x, yAnt, r, aIni, bIni, sr,q;
aIni = a; bIni = b;
x = 1; yAnt = 0;
while (b != 0){
r = a % b;
q=a/b;
a = b;
b = r;
sr = x - yAnt*q;
x = yAnt;
yAnt = sr;
}
*m = x;
*n = (a – x*aIni)/bIni;
return a;
}
Módulo para número negativos
int mod(int a, int n) {
return (a%n + n)%n;
}
Teorema1 Seja d = mdc(a,b) e ax’ + by’ = d então a equação ax = c mod b tem como uma solução x0 = x’ (c/d) é uma solução da equação.
ax0 = a (x’ (c/d)) mod b
= ax’ (c/d) mod b
= d (c/d) mod b
= c
Teorema2 Suponha ax = b mod c tenha solução e x0 seja uma solução. Então essa equação tem exatamente d soluções distintas, módulo n, dado por xi = x0 + i (b/d)
axi = a (x0 + i (b/d)) mod b
= ax0 +a i/d*b mod b
= ax0
Resolvendo o problema:
Problema 1
3x – 5y = 19
b = 5
a = mod(3,5) = 3
c = mod(19,5) = 4
3x = 4 (mod 5)
mdc(3,5) = 1
3x’ + 5y’ = 1
3(2) + 5*(-1) = 1
x0 = x’ (c/d) = 2*4 = 8
Problema 2
10x + 12y = 80
a = mod(10,12) = 10
c = mod(80,12) = 8
10x + 12y = 8
10x = 8 mod 12
d = mdc(10,12) = 2
10(-1) + 12(1) = 2
x0 = -1*(8/2) = -4
x1 = x0 + 1*(12/2) = -4 + 6 = 2
Nenhum comentário:
Postar um comentário