quinta-feira, 8 de novembro de 2012

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.




Nenhum comentário:

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...