Equações diofantinas
ax + by = c
ax² + by² + cz² = d
ax³ + by³ = c
As equações diofantinas recebem esse nome em homenagem ao matemático grego Diofanto, que viveu em meados do século III. No escopo das equações diofantinas o que nos interessa são as suas soluções no conjunto dos inteiros.
Em nosso estudo iremos focar nas equações diofantinas lineares do tipo ax + by = c, onde a, b e c ∈ ℤ e x, y são as incógnitas que também devem ser inteiras.
Tipos principais
- Lineares: ax + by = c
- Quadráticas: ax² + by² = z²
- De grau superior: xn + yn = zn (Famoso pelo último teorema de Fermat!)
Condições importantes
- Nem toda equação diofantina tem solução.
- Às vezes, há infinitas soluções, ou apenas um conjunto restrito.
- Frequentemente, precisamos analisar divisibilidade, congruências e propriedades dos números.
Exemplo 1
Encontre a solução da equação 2x + 3y = 1.
Passo 1: Checar se há solução.
O mdc(2,3) = 1 e 1|1, logo há solução.
Passo 2: Encontrar uma solução particular.
Isolamos uma variável, por exemplo x.
2x = 1 – 3y
| x = |
|
Para que x seja inteiro, 1 – 3y deve ser par.
Testamos valores para y:
- Se y = 1: x = [1 – 3(1)] / 2 = -1 → solução (x,y) = (-1,1)
- Se y = -1: x = [1 – 3(-1)] / 2 = 2 → solução (x,y) = (2,-1)
Passo 3: Encontramos a solução geral.
| x = | x0 + |
|
* k |
| y = | y0 – |
|
* k |
Aplicando ao nosso caso
Vamos utilizar a solução particular (-1,1).
| x = | -1 + |
|
* k | = | -1 + 3k |
| y = | 1 – |
|
* k | = | 1 – 2k |
Portanto, para qualquer inteiro k, a solução deve satisfazer a equação original.
Exemplo 2
Para colocar 13 abóboras em grupos de 3 ou de 5, quantos grupos serão formados de cada tipo?
Resolver esse problema significa encontrar as soluções inteiras e positivas da equação 3x + 5y = 13.
Passo 1: Checar se há solução.
O mdc(3,5) = 1 e 1|13, logo há solução.
Passo 2: Encontrar uma solução particular.
- Se y = 0, teremos 3x + 5(0) = 13 → 3x = 13 → x = 13/3 que não é inteiro, portanto não serve.
- Se y = 1, teremos 3x + 5(1) = 13 → 3x = 8 → x = 8/3 que não é inteiro, portanto não serve.
- Se y = 2, teremos 3x + 5(2) = 13 → 3x = 3 → x = 3/3 = 1. Solução (x,y) = (1,2)
Passo 3: Encontrar a solução geral.
x = x0 + 5k
y = y0 – 3k
O leitor poderá realizar testes incluindo valores para k e chegará a conclusão de que a única solução possível será (1,2), ou seja, 1 grupo de 3 abóboras e 2 grupos de 5 abóboras.
Exemplo 3
Um laboratório dispõe de 2 máquinas para o processo de examinar amostras de sangue. Uma delas examina 15 amostras a cada processo, a outra examina 25 amostras. Quantas vezes essas máquinas devem ser acionadas para conseguir examinar 1000 amostras de sangue?
Resolver esse problema significa solucionar a equação 15x + 25y = 1000, onde x e y representam os ciclos de funcionamento.
15x + 25y = 1000
3x + 5y = 200
5y = 200 – 3x
| y = |
|
Então, 200 – 3x deve ser divisível por 5 para que y seja inteiro, ou seja, 200 – 3x deve ser um número terminado em zero ou cinco.
Se x = 10
| y = |
|
| y = |
|
= | 34 |
Logo, uma das soluções é (10,34).
Vamos encontrar a solução geral.
x = 10 + 5k
y = 34 – 3k
Para k = 11, temos x = 65 e y = 1, dessa forma a máquina que examina 15 amostras seria usada 65 vezes e a máquina que examina 25 ammostras seria usada 1 vez.
Para k = 3, temos x = 25 e y = 25, dessa forma cada máquina seria utiliza igualmente. Existem ao todo 14 combinações diferentes para serem testadas.
Exemplo 4
Resolva a equação diofantina 252x + 105y = 42.
Passo 1: Encontrar o mdc(105,252) = 21 e verificar se 21 | 42, se sim, a equação possui solução.
Dividimos o maior número 252 pelo menor 105.
252 = 2 . 105 + 42
Em seguida dividimos 105 pelo resto 42
105 = 2 . 42 + 21
Prosseguimos dividindo 42 pelo resto 21
42 = 2 . 21 + 0
Visto que obtivemos resto zero, concluímos pelo teorema de Euclides para o mdc que o mdc(105,252) = 21.
Passo 2:
Escrevemos o mdc(105,252) como combinação linear de 105 e 252.
21 = 105 – 2 . 42
21 = 105 – 2 (252 – 2 . 105)
21 = 105 – 2 . 252 + 4 . 105
21 = 105(1 + 4) + 252(-2)
21 = 105(5) + 252(-2)
21 * 2 = 105(5) + 252(-2) * 2
42 = 252(-4) + 105(10)
Portanto a solução procurada é o par ordenado (-4,10).