Equações Diofantinas

Uma equação diofantina é uma equação em que somente soluções inteiras são permitidas.

O termo diofantina se refere ao matemático Diofanto de Alexandria, que viveu no século III; ele foi o primeiro a estudar tais tipos de equações.

Na maioria dos casos, as equações diofantinas são insolúveis, fato este que foi demonstrado em meados do século XX, nas tentativas de resolução do Décimo Problema de Hilbert (que propõe a demonstração da solubilidade das equações diofantinas nos inteiros).

Equações Diofantinas Lineares

Trata-se de qualquer equação linear de 1º grau com coeficientes inteiros, isto é, $a_1x_1+a_2x_2+\cdots+a_nx_n=b$ com $a_{1},a_{2},\cdots ,a_{n}\in \mathbb {Z}$ , tal que haja soluções para $x_1,x_2,\cdots,x_n$ inteiros. Aqui $a_1, a_2, \cdots, a_n$ são chamados de coeficientes, enquanto $x_1,x_2,\cdots,x_n$ são as incógnitas.

Equações Diofantinas Lineares Com Duas Variáveis

Este é o tipo mais conhecido de equações diofantinas lineares. Basicamente, é toda equação da forma $a x + b y = c$ , onde $a, b$ e $c$ são inteiros.

Quando Equações Diofantinas Lineares Com Duas Variáveis Possuem Soluções?

Se $\operatorname{mdc}(a,b)|c$ , então a equação diofantina da forma $a x + b y = c$ possui solução.

Prova: Por hipótese, existe $p$ inteiro tal que $c=p\cdot \operatorname{mdc}(a,b)$ . Pelo Teorema de Bachet-Bézout, existem $m$ e $n$ inteiros tais que $am+bn=\operatorname{mdc}(a,b)$ . Se multiplicarmos ambos os lados da igualdade por $p$ ,

$a(pm)+b(pn)=p\cdot \operatorname{mdc}(a,b)=c$ .

Com isso, o par $(x,y)=(pm,pn)$ é uma solução da equação diofantina.

Resoluções de Equações Diofantinas Lineares Com Duas Variáveis

Para resolvermos estes tipos de equações, devemos realizar os seguintes passos:

Utilizamos o o Algoritmo de Euclides para calcular $\operatorname{mdc}(a,b)$ e dele, podemos ver se a equação possui solução ou não.
Feito isso, partiremos para a versão estendida do Algoritmo de Euclides, que consiste em encontrar um par de números inteiros $(m, n)$ que satisfaça a Relação de Bézout.
A partir daí, é encontrada a chamada solução particular da equação, que é $(x_0,y_0)=(pm,pn)$ , onde $p=\frac{c}{\operatorname{mdc}(a,b)}$ .
Partindo da solução particular, podemos encontrar a solução geral, que é definida por $\begin{cases}x=x_0+bt\\ y=y_0-at\end{cases},\ t\in\mathbb{Z}$ .

Exemplo

Encontre todas as soluções inteiras de $3x+5y=101$ .

Solução: Inicialmente, calculemos o $\operatorname{mdc}$ de $3$ e $5$ . Observe que

$5=3\cdot1+2$

$3=2\cdot1+1$ .

Assim, $\operatorname{mdc}(3,5)=1$ . Como $1|101$ , a equação do enunciado possui solução. Vamos aplicar o Algoritmo Estendido de Euclides. Das igualdades anteriores, podemos concluir que

$1=3-1\cdot2$

$2=5-3$ .

Se substituirmos a segunda igualdade na primeira:

$3\cdot2+5\cdot(-1)=1$ .

Para encontrarmos uma solução particular, basta multiplicarmos ambos os lados da igualdade por $101$ :

$3\cdot202+5\cdot(-101)=101$ .

Logo a solução particular é $x_0=202$ e $y_0=-101$ , de onde segue que a solução geral é $x=202+5t$ e $y=-101-3t$ .

Observação

Se uma equação diofantina linear com duas variáveis possuir alguma solução, então ela possui infinitas.

Equações Diofantinas Lineares Com Três ou Mais Variáveis

Essas equações, se possuem uma solução, possuem infinitas. Quase sempre, não há fórmulas que nos permitam resolver esses tipos de equações. Analogo ao caso de duas variáveis, as soluções existem quando $\operatorname{mdc}(a_1,a_2,\cdots,a_n)|b$ .

No geral a solução possível é escrever uma das incógnitas em função das demais. Nos naturais, contudo, a quantidade de soluções pode ser restringida.

Equações Diofantinas Não-Lineares

São as equações diofantinas que possuem pelo menos um termo de grau superior a $1$ (por exemplo, $x^2+y^3=3$ , onde o grau da incógnita $x$ é $2$ e o da incógnita $y$ é $3$ ). Também existem equações diofantinas em que uma ou mais incógnitas aparecem como expoentes, por exemplo, $2^x+5=y^2$ (são as chamadas equações diofantinas exponenciais). A maioria dessas equações não possui soluções.

Estratégias para Resoluções de Equações Diofantinas

Analisar a paridade.
Fatorações.
Aritmética Modular.
Discriminante.
Números Complexos.

Algumas Ideias Comuns

Faça uma fatoração aparecer em pelo menos um dos membros da igualdade, para que você possa comparar os fatores.
Você pode mostrar que alguma das incógnitas não é tão grande assim (e assim, como restam poucas possibilidades, você pode testá-las). Para isso, encontre uma divisibilidade $a|b$ e use a propriedade da limitação, isto é, $|a| \leq |b|$ .

Exemplo (Cone Sul 1996)

Se pretende cobrir totalmente um quadrado de lado $k$ ( $k$ inteiro e maior que um) com os seguintes retângulos: $1$ retângulo $1 \times 1$ , $2$ retângulos $2 \times 1$ , $4$ retângulos de $3\times1$ , ..., $2^n$ retângulos de $(n+1) \times 1$ , de tal maneira que os retângulos não se superponham nem excedam os limites do quadrados.

Achar todos os valores de $k$ para os quais isto é possível e, para cada valor de $k$ encontrado, desenhar uma solução.

Solução: Divida o quadrado em $k^2$ quadradinhos $1 \times 1$ . Se pudermos preencher conforme o enunciado, a quantidade de quadradinhos $1 \times 1$ será

$1.1+2.2+4.3+\dots+2^n(n+1).$

Com isso,

$k^2=1.1+2.2+4.3+\dots+2^n(n+1). (*)$

Podemos simplificar o lado direito dessa igualdade? Considere

$S=1.1+2.2+4.3+\dots+2^n(n+1). (**)$

Repare que o primeiro fator de cada parcela forma uma progressão geométrica. Se multiplicarmos ambos os lados da igualdade por $2$ , ainda teremos uma progressão geométrica "empurrada para frente". Com isso,

$2S=2.1+4.2+8.3+\dots+2^n.n+2^{n+1}(n+1).$

Podemos relacionar os fatores que formam uma progressão geométrica nestas duas últimas igualdades. De fato, se subtrairmos $(**)$ de $(*)$ :

$-S=1+2+4+\dots+2^n-2^{n+1}(n+1).$

Apareceu a soma dos termos de uma progressão geométrica. Com isso,

$S=2^{n+1}n+1.$

Desta maneira,

$k^2=2^{n+1}n+1.$

Façamos alguma fatoração aparecer em algum dos lados da igualdade:

$k^2-1=2^{n+1}n \Leftrightarrow (k+1)(k-1)=2^{n+1}n.(***)$

Vamos focar nas potências de $2$ já que elas aparecem do lado direito. Quais são as potências de $2$ que dividem $k+1$ e $k - 1$ ? Observe que $4$ não podem dividir $k+1$ e $k - 1$ ao mesmo tempo. De fato, se isso acontecesse, então $4$ deveria dividir $k+1-(k-1)=2$ .

Logo, $4\nmid k-1$ ou $4\nmid k+1$ . Analisemos cada um dos casos.

(i) $4\nmid k-1$

Neste caso, $2^n|k+1$ , ou seja, existe $x$ inteiro positivo tal que

$2^nx=k+1 \Leftrightarrow k=2^nx-1.$

Se substituirmos em $(***)$ :

$2^nx(2^nx-2)=2^{n+1}n \Leftrightarrow x(2^{n-1}x-1)=n.$

Vejamos que as soluções não podem ser tão grandes assim. Para isso, usaremos a propriedade da limitação. Observe que

$2^{n-1}x-1|n \Rightarrow 2^{n-1}x-1 \leq n \Rightarrow 2^{n-1} \leq n+1.$

Esta desigualdade deixa de ser verdadeira quando $n \geq 4$ (neste caso, $n+1 <2^{n-1}$ ). Logo, $n \leq 3$

(ii) $4\nmid k+1$

O mesmo raciocínio nos faz concluir que não existe solução neste caso.

Como $n \leq 3$ , podemos testar as possbilidades para $n=1,2,3$ . A única que dará certo é $n = 3$ , o que nos dá $k=7$ .

Aritmética Modular na Resolução Equações Diofantinas

Uma boa maneira de escolhermos o módulo é fazermos de tal forma que uma ou mais variáveis desapareça.

Exemplo (OBM 2007 - 3ª Fase - Nível 2)

Prove que não existem soluções inteiras e positivas para a equação

$3^m+3^n+1=t^2$ .

Solução: Vamos começar analisando a paridade. Observe que o lado esquerdo da igualdade é ímpar. Assim, $t^2$ é ímpar, de onde segue que $t$ também é. Logo, existe $k$ inteiro tal que $t=2k+1$ . Se substituirmos na equação do enunciado:

$3^m+3^n+1=(2k+1)^2 \Leftrightarrow 3^m+3^n=4k(k+1)$ .

Um dentre os números $k$ e $k+1$ é par. Logo, $k(k+1)$ e assim, o lado direito da igualdade é múltiplo de $8$ . Que tal então analisarmos a equação módulo $8$ ?

Observe que $3^m+3^n \equiv 0 \pmod{8}$ . Mas, se $x$ é inteiro, então $3^x \equiv 1 \textrm{ ou } 3\pmod{8}$ , de onde segue que $3^m+3^n \equiv 2,4 \textrm{ ou } 6 \pmod{8}$ , Logo, a equação do enunciado não admite soluções inteiras.

Exemplo (Cone Sul 1992)

Encontre um número inteiro positivo $n$ tal que, se você colocar o número $2$ à esquerda e o número $1$ à direita, o novo número será igual a $33n$ .

Solução: Observe que o enunciado não pede todos os valores de $n$ e sim apenas algum valor. O que significa colocar $1$ à direita? Que estamos transformando $n$ em $10n+1$ .

E quanto ao $2$ colocado à direita? Se $n$ tiver k algarismos, então $10n+1$ terá $k+1$ algarismos. Colocar o $2$ à direita é o mesmo que transformar $10n+1$ em $2.10^{k+1}+10n+1$ .

Queremos, então, encontrar $n$ e $k$ inteiros tais que

$2.10^{k+1}+10n+1=33n \Leftrightarrow 2.10^{k+1}+1=23n.$

Se interessante se conseguíssemos usar o módulo, sem precisar mexer com $n$ . Para isto, basta usarmos módulo $23$ : $2.10^{k+1}+1 \equiv 0 \pmod {n}$ .

Note que $k=0$ e $k = 1$ não são soluções, porém $k=2$ é. Existe algum $n$ com dois algarismos tal que satisfaça a equação com $k=2$ ? Repare que se $k=2$ , então $n=87$ , que é uma solução.

Algumas Ideias Comuns sobre Módulos em Equações Diofantinas

Quando aparecem quadrados perfeitos, uma boa ideia é usar módulo $4$ . De fato, $a^2$ só pode ser congruente a $0$ ou $1$ módulo 4.
Quando aparecem cubos perfeitos, uma ideia bacana é usar módulo $7$ . De fato, se $a$ é inteiro, então $a^3$ só pode ser congruente a $0$ , $1$ ou $6$ módulo $7$ .

Exemplo (OBM 2001 - 3ª Fase - Nível 2)

Mostre que não existem dois números inteiros $a$ e $b$ tais que $(a+b)(a^2+b^2)=2001$ .

Solução: No lado esquerdo da igualdade aparece um produto. E quanto ao lado direito? Podemos escrevê-lo como o produto de dois números inteiros? Nossa, parece muitos inteiros. Precisamos considerar os negativos também? Neste caso não: $a^2+b^2 >0$ . Logo, $a+b > 0$ .

Observe que a fatoração em primos de $2001$ é $3.23.29$ . Assim, as maneiras de escrevermos $2001$ como o produto de dois números é $1.2001=3.667=23.87=29.69$ .

Se soubermos qual dos dois fatores do lado esquerdo da igualdade é maior, nossa vida será mais fácil. Como não existe nenhum inteiro $x$ tal que $0<x<1$ , segue que $x^2 \geq x$ para todo $x$ inteiro.

Com isso,

$a^2 \geq a$

$b^2 \geq b$

e assim $a^2+b^2 \geq a+b$ . Desta forma, existem quatro casos:

(i) $a+b=1$ e $a^2+b^2=2001$

(ii) $a+b=3$ e $a^2+b^2=667$

(iii) $a+b=23$ e $a^2+b^2=87$

(iv) $a+b=29$ e $a^2+b^2=69$ .

Vamos analisar cada um deles separadamente.

(i) $a+b=1$ e $a^2+b^2=2001$

$a+b=1 \Leftrightarrow a=1-b$ .

Com isso, se substituirmos na equação $a^2+b^2=2001$ , teremos

$b^2-b-1000=0.$

Aqui, $\Delta=4001$ (que não é um quadrado perfeito). Logo, não existe nenhuma solução neste caso.

(ii) $a+b=3$ e $a^2+b^2=667$

Vamos usar congruência. Já que aparecem quadrados perfeitos, uma boa ideia é usarmos módulo $4$ . Observe que

$a^2+b^2 \equiv 667 \equiv 3 \pmod{4}.$

Mas isto não pode ocorrer, pois $a^2+b^2$ só pode ser congruente a $0$ , $1$ ou $2$ módulo $4$ . Assim, não existem soluções neste caso.

(iii) $a+b=23$ e $a^2+b^2=87$

Análogo ao caso (ii)

(iv) $a+b=29$ e $a^2+b^2=69$ .

Análogo ao caso (i).

Logo, não existem inteiros $a$ e $b$ que satisfaçam as condições do enunciado.

Exemplo (OBM 2009 - 3ª Fase - Nível 2)

Prove que não existem inteiros positivos $x$ e $y$ tais que $x^3+y^3=2^{2009}$ .

Solução: Como para todo $a$ é inteiro, $a^3$ só pode ser congruente a $0$ , $1$ ou $6$ módulo $7$ , segue que $x^3+y^3$ só pode ser congruente a $0,1,2,5$ ou $6$ módulo $7$ . Mas $2^{2009} \equiv 4 \pmod{7}$ . Logo, a equação não possui soluções inteiras positivas.

Discriminante na Resolução de Equações Diofantinas

O discriminante da equação $ax^{2} + bx + c = 0$ é o número $\Delta = b^{2} - 4ac$ . Qual sua utilidade? Sabemos que essa equação tem solução real se, e somente se, $\Delta \geq 0$ .

Exemplo (OBM 2006 - 3ª Fase - Nível 2)

Encontre todos os pares ordenados $(x;y)$ de inteiros tais que $x^3-y^3=3(x^2-y^2)$ .

Solução: Observe que

$x^3-y^3=3(x^2-y^2) \Leftrightarrow$ .

$\Leftrightarrow (x-y)(x^2+xy+y^2)=3(x+y)(x-y)$ .

E agora: podemos dividir ambos os lados da igualdade por $(x-y)$ ? Só se ele for diferente de zero. Por isso, vamos dividir em casos.

1º Caso: $x-y=0$

Se fizermos $x = y$ na equação original, teremos uma igualdade sempre válida. Logo, todo par $(x,y)=(a,a)$ é solução para todo $a$ inteiro.

2º Caso: $x-y \neq 0$

Ao dividirmos ambos os lados da igualdade por $(x-y)$ :

$x^2+xy+y^2=3(x+y)\Leftrightarrow$ .

$\Leftrightarrow x^2+(y-3)x+y^2-3y=0$

$\Delta=(y-3)^2-4.1.(-3y)=-3(y+1)(y-3)$ .

A equação tem solução se, e somente se,

$\Delta \geq 0 \Leftrightarrow (y+1)(y-3) \leq 0$ .

Desta forma, um dos fatores é maior ou igual a zero e o outro é menor ou igual a zero. Observe que não pode ocorrer $y+1 \leq 0$ e $y-3 \geq 0$ .

Logo, $y+1 \geq 0$ e $y-3 \leq 0$ , o que equivale a dizer que $-1 \leq y \leq 3$ . Como $y$ é inteiro, segue que ele só pode ser um dos valores $-1,0,1,2,3$ . Analisemos cada caso.