Gilda de La Rocque
João Bosco Pitombeira
PUC, Rio de Janeiro

Um caso de equação diofantina aparece naturalmente em certos problemas de agrupamentos como por exemplo:

   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.  Quantas vezes essas máquinas devem ser acionadas para examinar 2 mil amostras?

    Quantas quadras de basquete e quantas de vôlei são necessárias para que 80 alunos joguem simultaneamente?   E se forem 77 alunos?

    Para agrupar 13 aviões em filas de 3 ou de 5, quantas filas serão formadas de cada tipo?

A resolução destes problemas consiste na busca de soluções inteiras (e positivas) da equação

ax  +  b y   =   c.

_________
*Este material foi desenvolvido como parte de atividades com professores do 2.° grau, no Projeto Matemática, Comunidade e Universidade, do Departamento de Matemática da PUC-Rio.

Trata-se, portanto, de uma equação diofantina.

Analisando os casos acima, o problema do laboratório pode ser descrito pela equação 15x+25y = 2000 que apresenta 27 soluções (que sejam pares de números inteiros positivos), 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. No caso das quadras, uma equação é l0x+12y=80, que apresenta as 2 soluções x = 2 e y = 5 ou x = 8 e y = 0, enquanto a equação l0x + 12y = 77 não apresenta soluções (que sejam pares de números inteiros). No caso dos aviões (que pode ser apresentado desde muito cedo às crianças), a equação 3x+5y=13 apresenta uma única solução (pares de números inteiros e positivos)  x = l , y=2.

Ao propor um de tais problemas, a escolha dos coeficientes a, b, c importa, não só para maior ou menor dificuldade nos cálculos, como também para a existência de uma, várias ou nenhuma solução (desde que sejam inteiras ou inteiras positivas). Estes são exemplos de variáveis didáticas (Caderno da RPM, v. 1, p. 13), das quais o professor pode lançar mão para atingir este ou aquele objetivo. E, para isso, um conhecimento mais vasto da situação envolvida é bastante útil.

Ora, ao estudarmos um problema matemático, é muito conveniente termos um "processo" que nos diga se ele tem ou não soluções e que, no primeiro caso, forneça todas as soluções. Por exemplo, dada a equação do segundo grau

ax² + bx + c = 0 ,

sabemos que ela tem soluções reais se, e somente se,

b² - 4ac 0 .

Quando isso acontece, as soluções reais x₁ e x₂ são dadas por

Ao estudarmos a equação diofantina   ax + by = c,   com   a,b e c números inteiros, interessa-nos saber se há um critério que permita dizer se ela tem soluções e um método (algoritmo) para achar todas as soluções (se existirem). Como estamos tratando de equações diofantinas, interessamo-nos somente por soluções inteiras de ax + by = c.

Existe de fato um critério que nos permite decidir se a equação ax + by = c tem ou não soluções inteiras, e ele é uma aplicação genuína e não-trivial da noção de máximo divisor comum!

No que segue, apresentaremos:

1. Um critério de existência de solução, que já tem como subproduto um processo para   encontrarmos uma solução particular;

2.   Um algoritmo para encontrar essa solução particular;

3.    A expressão que fornece todas as soluções inteiras a partir de uma particular.

Seja portanto pedido para resolver a equação diofantina

ax + by = c,

isto é, nela   a, b e c   são números inteiros e procuramos soluções (x,y) que sejam pares ordenados de números inteiros.

No que segue, usaremos algumas propriedades de divisibilidade que enunciamos a seguir, as duas primeiras das quais são de verificação imediata e uma prova da terceira pode ser encontrada, por exemplo, na RPM 13, p. 45:

Propriedade 1 - Se d divide a, então dividirá am, para qualquer inteiro m;

Propriedade 2 -   Se d divide a e divide b, então dividirá a + b;

Propriedade 3 - Se d é o máximo divisor comum de a e b, então existem inteiros r e s tais que                             ar + bs = d.

Observemos que, a partir das duas primeiras propriedades acima, se o problema ax + by = c, tiver alguma solução com x₀ e y₀ inteiros e se d for um divisor comum de a e b, então d dividirá c. Em particular, o máximo divisor comum de a e b deve dividir c. Essa é, então, uma condição necessária para a existência de solução inteira.

Será também suficiente?

A terceira propriedade acima enunciada afirma que sim. Com efeito, se d for o máximo divisor comum de a e b e d dividir c, então c = dm e, pela propriedade 3, existirão inteiros r e s tais que ar + bs = d. Ora, multiplicando ambos os membros desta última igualdade pelo inteiro m, vem a(rm) + b(sm) = c,  donde x = rm  e  y = sm   é a solução procurada.

Podemos, assim, enunciar o

Teorema 1. A equação diofantina  ax + by = c  tem solução (inteira) se, e somente se, o máximo divisor comum de a e b dividir c.

Exemplos:

Como aplicação do teorema 1, vemos que 4x + 6y = 9 não tem solução, pois  mdc(4 ,6) = 2 e 2 não divide 9. De resto, é claro que o número 4x + 6y, com x e y inteiros, será sempre par, logo não poderá ser 9.

Por outro lado, 8x + l2y = 36 tem solução, pois mdc(8, 12) = 4  e 4 divide 36.

0 teorema 1 tem um corolário imediato, que é o seguinte:

Corolário. Se mdc(a,b) = 1, isto é, se a e b são relativamente primos (ou primos entre si), então a equação ax + by = c sempre tem soluções inteiras, qualquer que seja c.

Observação. Para efeito de encontrar as soluções inteiras, o caso que interessa é só esse do corolário, em que mdc(a,b) = 1. De fato, se existir solução e esse máximo divisor comum for d1, basta dividir ambos os membros da equação por d que se chega ao caso de coeficientes a e b relativamente primos, com um segundo membro ainda inteiro.

Vimos que na busca de soluções inteiras de ax + by = c, podemos tomar mdc(a,b) = 1 e que achar uma solução inteira dessa equação equivale a encontrar inteiros r e s tais que ar + bs=1.

A prova que citamos da existência desses números r e s não é construtiva.

Um modo de se chegar a eles é obtido através do algoritmo de Euclides, ou algoritmo das divisões sucessivas, para o cálculo do mdc(a,b). A legitimidade desse algoritmo repousa sobre as seguintes observações:

1)        Se a e b são inteiros, com b > 0, existem inteiros  q  e  r, com 0 r < b,  únicos, tais que  a = bq + r  (algoritmo da divisão).

2)   Sejam a e b inteiros, com   b > 0,  e  a = bq + r,   com  0 r < b.    Então   mdc(a,b)=mdc(b,r).   Com efeito, mostraremos que o conjunto dos divisores comuns de a e b é igual ao conjunto dos divisores comuns de b e r. Segue-se então, forçosamente, que o máximo divisor comum de a e b é igual ao de b e r. Se  a = bq + r e g é um divisor comum de a e b (isto é, g divide a e g divide b), então, de   a bq = r,  segue-se que g divide b e g divide r.   Logo g é um divisor comum de b e r.

Reciprocamente, se g divide b e r, como a = bq + r, segue-se que g divide a e b.

Mostraremos agora, por um exemplo, como achar os inteiros  r  e  s  tais que  ar + bs = 1.

Para isso, consideremos os números 32 e 9. O algoritmo de Euclides (que, no Rio de Janeiro, tem o nome de "jogo-da-velha") para o cálculo do  mdc (32,9)  é o seguinte:

Este algoritmo resume as seguintes divisões:

e, então, pela segunda observação acima,

mdc (32,9) = mdc (9,5) = mdc (5,4) = mdc (4,1) = 1.

Agora, combinando convenientemente as expressões (A), (B), (C), acharemos inteiros  r e s  tais que  32r + 9s = 1.   De fato, de (C),   vem   5 1 x 4=1.   De (B), tiramos     4 = 9 1 x 5 que, na expressão acima, dá

5 l x (9 l x 5) = l    ou    5 1 x 9 + 1 x 5 = 1

ou, ainda,  2 x 5 1 x 9 = 1.

De (A),  temos     5 = 32 3 x 9     que, na expressão acima, dá

2 x (32 3 x 9) 1 x 9 =1    ou    2 x 32 7 x 9 = 1

e os números procurados são, finalmente, 2 e 7.

A demonstração geral é análoga a este exemplo.

Seja (x₀, y₀) uma solução inteira de ax + by = c, com a e b relativamente primos. Então ax₀+by₀ = c. Ora, se ao primeiro membro acrescentarmos e subtrairmos o mesmo número, a igualdade continuará valendo. Para que possamos colocar a e b em evidência, exigiremos que o número acrescentado seja um múltiplo de ab, isto é, seja um número da forma abk, com k inteiro. Temos, então,

o que mostra que o par (x₀ + bk, y₀ ak) é ainda uma solução da equação diofantina considerada. (Observe que, até este ponto, a hipótese de que   mdc(a,b) = 1   não foi utilizada!)

Será que estas são todas as soluções inteiras? Existirão outras? Para buscarmos uma resposta a esta pergunta, suponhamos que (x₀ , y₀)  e  (x₁,y₁)  sejam soluções inteiras de ax + by = c, com mdc(a,b) = 1.

Temos então

ax₀ + by₀ = c        e        ax₁ + by₁ = c.

Logo,

a (x₁ x₀) = b(y₀ y₁).

Primeiro caso: Se a = 1, chamamos de k; o inteiro y₀ y₁ e teremos x₀ x₁ = bk, isto é, x₁ = x₀ + bk onde y₀ y₁ = k, ou seja, y₁ = y₀ k, que é igual a  y₁ = y₀ ak,  pois  a = 1. Logo, neste caso, qualquer solução (x₁,y₁) é da forma (x₀ + bk, y₀ ak), com k inteiro.

Segundo caso: Se a 1, a não divide b,  pois a e b  são relativamente primos. Então a divide  y₀   y₁, ou seja, existe k; inteiro tal que  y₀   y₁ = ak,  donde  y₁ = y₀  ak.  Mas então a( x₁ x₀ ) = bak,  e, como  a 0,  vem que  x₁ x₀ = bk,  ou seja,  x₁=x₀+bk.

Acabamos assim de demonstrar o seguinte teorema:

Teorema 2.

Se (x₀ , y₀) for uma solução da equação diofantina  ax + by = c,  com mdc(a,b)= 1, então ( x₁, y₁) será solução da equação se, e somente se, existir um inteiro k tal que  x₁ = x₀ + bk   e   y₁ = y₀    ak.

Observe que a condição de a e b serem relativamente primos não é necessária para que  x₁ e y₁ dados no teorema 2 sejam soluções da equação diofantina, mas essa condição é necessária para garantir que essas sejam iodas as soluções da equação dada.

Exemplo: Determinemos todas as soluções da equação diofantina 143x + 17y = 132. Em primeiro lugar, mdc (143,17) = 1, logo a equação tem soluções inteiras. Para achar uma delas, observe que

143 = 8 x 17 + 7    ,     17 = 2 x 7 + 3    ,     7 = 2 x 3 + 1.

Logo

l = 7 2 x 3 = 7 2 x [17 2 x 7] = 5 x 7 2 x 17 =

= 5 x [143 8 x 17] 2 x 17 = 5 x 143 42 x 17.

Donde,

143 x [5 x 132] + 17 x [42 x 132] = 132,

ou seja,

(x₀, y₀ ) = (660,5544)    é solução da equação.

Então, todas as soluções são da forma

x = 660 + 17k       e        y = 5544 143k ,

onde k é um inteiro arbitrário.

Pouco se sabe da vida de Diofanto. Acredita-se que tenha vivido por volta de 250, em Alexandria. O único dado pessoal sobre Diofanto encontra-se, sob forma de problema, na chamada Antologia Grega do 5.° ou 6.° século:

Deus lhe concedeu ser menino pela sexta parte de sua vida, e somando uma doudécima. parte a isso cobriu-lhe as faces de penugem. Ele lhe acendeu a lâmpada nupcial após uma. sétima parte, e cinco anos após seu casamento concedeu-lhe um filho. Ai! infeliz criança; depois de viver a metade da vida de seu pai, o Destino frio o levou. Depois de se consolar de sua dor durante quatro anos com a ciência dos números ele terminou sua vida.

Se esse enigma for historicamente exato, Diofanto viveu 84 anos.

A principal obra de Diofanto é a Arithmetica, tratado originalmente em 13 livros, dos quais só os seis primeiros se preservaram. (...) É um tratado caracterizado por um alto grau de habilidade matemática e de engenho: quanto a isto, o livro pode ser comparado aos grandes clássicos da Idade Alexandrina anterior; no entanto quase nada tem em comum com esses ou, na verdade, com qualquer Matemática grega tradicional. Representa essencialmente um novo ramo e usa um método diferente. Devido à ênfase dada na Arithmetica, à solução de problemas indeterminados, o assunto, às vezes chamado análise indeterminada, tornou-se conhecido como análise diofantina.

A Arithmetica, é uma coleção de cerca de 150 problemas, todos estudados em termos de exemplos numéricos específicos, embora talvez pretendendo conseguir generalidade de método. (...) Não é feita uma distinção clara entre problemas determinados e indeterminados, e mesmo para os últimos, para os quais o número de soluções em geral é infinito, uma só resposta é dada.

Diofanto é,  às vezes, considerado como pai da Álgebra por ter feito uso sistemático de abreviações (não de símbolos especiais) para potências de números e para relações e operações. Com a sua notação, Diofanto podia escrever polinômios numa incógnita quase tão concisamente quanto nós hoje.

Diofanto teve uma influência maior sobre a teoria moderna dos números do que qualquer outro algebrista grego não geométrico. Em particular, Fermat foi levado ao seu célebre "último" teorema (v. RPM 15, p. 14) quando procurou generalizar um problema que tinha lido na Arithmetica de Diofanto: dividir um dado quadrado em dois quadrados.

(Esta nota histórica foi extraída do livro História da Matemática, Boyer, C. B. Editora Edgard Bliicher Ltda.)