Diofantinas

2. Equações lineares

2.1

Equações diofantinas

Comecemos com um exemplo. Exemplo 2.1 Suponhamos que só existiam moedas de 15 e de 7 escudos e que eu queria pagar (em dinheiro) uma certa quantia em escudos. Será que é sempre possível? E se só existissem moedas de 12 e de 30 escudos? No primeiro caso, se conseguirmos pagar 1 escudo então também sabemos pagar qualquer quantia: basta repetir o pagamento de 1 escudos as vezes que forem necessárias. Para pagar 1 escudo podemos usar uma moeda de 15 e receber de troco duas moedas de 7. Deste modo, se quisermos pagar 23 escudos podemos usar 23 moedas de 15 e receber de troco 46 moedas de 7. É claro que seria mais simples pagar com 2 moedas de 15 e receber 1 moeda de 7 de troco. No fundo estamos a encontrar soluções inteiras da equação 7x + 15y = 1. No segundo caso é claro que qualquer quantia que se consiga pagar é necessariamente múltipla de 6, porque 12 e 30 são múltiplos de 6. Por outro lado podemos pagar 6 escudos usando uma moeda de 30 e recebendo de troco duas moedas de 12. Deste modo podemos fazer o pagamento de qualquer quantia que seja múltipla de 6. Chegamos assim à seguinte definição. Definição 2.2 Uma equação nas variáveis inteiras x, y do tipo ax + by = c, diz-se uma equação diofantina. 25 com a, b, c ∈ Z

Equações lineares
A palavra diofantina “vem” de Diophantus da Alexandria, matemático grego do século III. É claro que se a = 0 ou b = 0 a equação tem resolução imediata. Por exemplo, se a = 0 e b = 0 então existe solução se b divide c e, nesse caso a solução geral é dada por x qualquer e y = c . Para os casos “não triviais” temos o seguinte teorema. b Teorema 2.3 Sejam a, b inteiros não ambos nulos, c ∈ Z e d = (a, b). A equação ax + by = c (nas incógnitas inteiras x, y)

tem solução se e só se d divide c. Além disso, se x0 , y0 são tais que ax0 + by0 = c então a solução geral da equação ax + by = c é x = x0 + y = y0 − b dt a d t,

com t ∈ Z.

Demonstração: Se a ou b é igual a 0 o resultado é