Teoria Elementar dos Números

Quando se fala em Teoria dos Números, não podemos deixar de falar de divisibilidade. Por isso, devemos ter em mente alguns teoremas simples sobre divisibilidade: 

Teorema Básico: Sempre podemos escrever [; a = bq +r ;]. Chamamos [;q;] de quociente da divisão e [;r;] de resto da divisão euclidiana, onde 0< r < q ou r=0. 

Teorema da Divisibilidade de Inteiros: Dados inteiros [;a,b,c;] , então 

(a) Se [; a | b;] , então [; a| ax+by;] para quaisquer valores de [;x,y;] nos inteiros
(b) Se [;a|b;], então [;|a| \le |b|;]
(c) Se [;a|b;] e [;b|c;], então [;a|c;] 

Como a demonstração de ambos os teoremas é muito intuitiva, esta será deixada a cargo do leitor interessado. Esta é a nossa primeira parte, que nos permite resolver alguns problemas interessantes: 

Exemplo 1: Determine todos os inteiros não negativos [; n;] tais que [;\frac{n^3+2n-1}{3n^2-1};]  é também inteiro. 

Resolução: Utilizando o nosso item (a), Reduzimos a expressão para achar todos os [;n;] tais que   [;\frac{7n-3}{3n^2-1};]é inteiro. Utilizando, agora, o item (b), temos que[;|3n^2-1|\le|7n-3|;]  . Portanto, temos que[;o\le n \le 2;] . Verificando, todos estes números são realmente soluções. 

Exemplo 2: (Bielorrussia 1996) Sejam [;m,n;] inteiros tais que 

 [;(m-n)^2=\frac{4mn}{m+m-1};]

a) Prove que [;(m-n);]  é um quadrado perfeito. 
b) Ache todos os inteiros que satisfazem esta relação. 

Resolução:  
a) [; (m+n)(m-n)^2 = 4mn + m^2 - 2nm + m^2 = (m+n)^2;] 
  [;(m+n) = 0;] ou [; (m+n)=(m-n)^2 ;] 
b) Se [; m-n=t;],então [; m+n=t^2;](segundo caso), e nossos pares são  [;(t,-t), (\frac{t^2+t}{2}, \frac{t^2-t}{2});] que são realmente soluções da equação. 


Agora, analisemos o exemplo a seguir:

Exemplo 3: (IMO-2007) Se [;a,b;] são inteiros positivos tais que [; 4ab-1 | (4a^2 -1)^2 ;], prove que [; a=b;]

Bom, comecemos utilizando nosso item (a), parece ser o mais correto a se fazer:

[;4ab-1 | 16a^4b - 8a^2b +b +8a^2b-2a = 16a^4b-2a+b ;] 
[; 4ab-1|16a^4b-2a+b-16a^4b +4a^3 = 4a^3-2a+b ;] 
[; 4ab-1|4a^3b-2ab+b^2-4a^2b+a^2 = (a-b)^2 ;] 

Ao tentar reduzir o grau do lado direito, entretanto, falhamos. Agora, o que fazer? A resposta é simples: usar o root-flipping. O nome parece estranho, mas é uma ideia natural: vejamos o que faremos: 

Pela condição de divisão, temos que

[;(a-b)^2=(4ab-1)k \Rightarrow a^2-2ab(2k+1)+b^2+k=0;]

Agora, você já deve ter percebido o que fizemos! Vamos, é claro, considerar como uma equação do segundo grau em [;a;]! Seja, agora, [;a,b;] uma solução minimal da equação dada. Logo, pelas relações de Girard, 

[; a+a_1 = 2b(2k+1) ;]

Como [;a,b;] são positivos, então [;a_1;] é também solução. Se [; a > b(2k+1) ;], então [;a_1;] é menor que [;a;], contradizendo sua minimalidade. Logo, [;a<b(2k+1);] . Portanto,  [;b^2+k \ge a^2 \Rightarrow k \ge a^2 -b^2;](considerando, aqui, [;a\ge b;], sem perda de generalidade). Porém, sabemos que  

[;k=\frac{a^2-b^2}{4ab-1} \ge a^2-b^2;]
Porém,  isto é, por si só, uma contradição, pois o denominador é sempre maior ou igual a 3. A única maneira de não haver contradição é com [; a=b;], e isto termina o problema. 

Vamos esclarecer ao leitor o processo acima. O root-flipping consiste em um caso particular do descenso infinito de fermat: buscamos uma equação dada, e, considerando uma solução mínima, encontramos uma menor, e isso contradiz a minimalidade da solução e, portanto, a existência de uma (pois o conjunto dos números naturais é bem ordenado, ou seja, todo subconjunto deste possui um elemento mínimo).

Basicamente, o root-flipping é achar uma equação do segundo (ou qualquer outro) grau em uma das variáveis, considerá-la mínima ou considerar algum aspecto possivelmente contraditório e, com ajuda das relações de Girard, contradizer essa minimalidade ou a propriedade contraditória, provando algo sobre a equação dada. Lendo esta definição, pode parecer um pouco vago, mas o exemplo acima mostra bem a utilidade desta ferramenta. Vejamos mais dois exemplos da descida de Fermat aliada ao root flipping:

Exemplo 4: Sejam [; a,b ;] inteiros tais que  [;\frac{a^2+b^2+1}{ab};]é também inteiro. Prove que este inteiro é 3.

Resolução: Usando a técnica que acabamos de aprender, então temos que

[; a^2 -(bk)a + b^2 +1 =0 ;]

Logo, vamos procurar uma solução com soma [;a+b;] minimal, e mostrar que [;a=b=1;]. De fato, [;k=3;] neste caso. Caso  [;k\ne 3;], nossa procura por uma solução com [;a>b;] (sem perda de generalidade) se abrevia ao notarmos que  [;a_1+a_2=kb> 2y \Rightarrow a_1 \ge a_2 > b;]. Porém, pela relação de Girard, [;a_1 \cdot a_2 =b^2 + 1;] , que contradiz claramente as desigualdades acima. Logo,  [;k \ne 3;] não pode acontecer, e terminamos. C.Q.D. 

Exemplo 5: Sejam [;m,n ;] inteiros positivos tais que [;m|n^2 +1;] e [;n|m^2 +1 ;]. Ache todos tais inteiros. 

Resolução: Notemos que esta equação implica em [; nm | n^2 + m^2 +1 ;], que é exatamente a equação do exemplo acima. Portanto, [;3mn = n^2 + m^2 +1;], que implica [; (3m-n)n = m^2 +1;]. Ou seja, se [;n;] é solução, então [;3m-n;] também é. Portanto, sempre podemos transformar um par [;(m,n);] em um par [;(3m-n,m);]. Achamos, assim, uma cadeia ascendente de soluções, ou descendente, dependendo do ponto de vista, que para na solução mínima. Como vimos, esta é [;(n,m)=(1,1);]. Portanto, as soluções são todas as geradas a partir desta satisfazendo a relação acima. C.Q.D.

Agora, que tal alguns exercícios para praticar o que aprendeu? 

P.1 - (IMO) Ache todos os pares [; (x,y) ;] de inteiros positivos tais que [;x^2y + x + y;] é divisível por [;xy^2 + y+7 ;]
P.2 - (IMO) Ache todos os inteiros [;(n,m);] tais que  [;\frac{n^3+1}{nm-1};]é um inteiro. 

P.3 - (IMO) Sejam [;(a,b);] inteiros tais que [;ab+1;] divide [;a^2+b^2 ;]. Prove que  [;\frac{a^2b^2}{ab+1};]é um quadrado perfeito. 

P.4 - Prove que, além de haver infinitos [;(a,b);] satisfazendo que  [;\frac{a^2+b^2}{ab-1};]seja inteiro, esse quociente vale 5. 

P.5 - (IMO) Encontre todos os inteiros positivos [;(m,n);] tais que

[;\frac{m^2}{2mn^2-n^3+1};]

Também é um inteiro.

Referências Bibliográficas: 

[1] - TENGAN, Eduardo; SALDANHA, Nicolau; MOREIRA, Carlos Gustavo, B. MARTINEZ, Fabio. Teoria dos Números: Um passeio com números primos e outros números familiares pelo mundo inteiro. Rio de Janeiro, RJ, Projeto Euclides, IMPA, 2010. 

[2] - http://cyshine.webs.com/tres-vip.pdf. - Treinamento Para as Olimpíadas Iberoamericana e IMO.




Comentários