domingo, 25 de novembro de 2012

Equações Diofantinas Exponenciais: Como o Lema de Hensel pode salvar sua vida!

Quando resolvemos problemas de teoria dos números, são muito importantes os problemas em que é dada uma equação diofantina cujas incógnitas são expoentes. Há muitas maneiras de resolver tais equações: analisar módulo algum primo conveniente, utilizar métodos análogos à equação de Pell ou de Pitágoras e, dentre os tantos outros, a análise através de um teorema muito importante, que recebe, ao meu ver, um injusto título de "Lema" 

O Lema do qual falamos é o Lema de Hensel, o qual diz muito sobre expoentes e fatores primos de números da forma . Vamos esclarecer: 

Teorema 1: (Lema de Hensel) Seja p um primo e a um inteiro qualquer. Portanto, 


(a) Se  for a maior potência de p que divide a - 1, e  a maior que divide n, então  é a maior potência de p que divide . (p TEM de dividir a - 1) 


(b) Se   for a maior potência de p que divide a + 1, e   a maior que divide n (n ímpar), então  é a maior potência de p que divide  (p TEM de dividir a +1)


Demonstração: Faremos um dos itens, sendo o outro totalmente análogo. Antes de partir para a demonstração, notemos que p tem de dividir a -1 ou a+1. Já explicaremos o porque, mas primeiro demonstraremos: 


Faremos indução em : Para , temos de provar que a maior potência de p  que divide  é , onde . Como , então 




Que, de fato, por , para k diferente de p ou 0, ser sempre múltiplo de p, deixa resto 1 mod . Como o l não contém p em sua fatoração, ao elevarmos a l não aumentamos o expoente de p (pode-se conferir isso mais uma vez com o binômio de Newton). 

Agora, suponhamos, para certo , que o maior expoente de  seja . Portanto, elevando a p para aumentar em um o expoente, 


Usando o mesmo argumento da hipótese de indução, alcançamos o desejado.  

Pode parecer um Lema um tanto quanto forçado, meio particular, mas resolve muito problema olímpico. Vejamos um exemplo primário: 

Exemplo 1: Ache todos os inteiros positivos x,y tais que 


Resolução: Primeiramente, reorganizando os fatores, ficamos com 


Isto nos sugere muito utilizar o Lema de Hensel! Repare que a maior potência de 3 que divide 7-1=6 é 3, e, pelo problema, deve ser . Logo, 


Portanto, reescrevendo a equação, 


Com igualdade se, e somente se,  

Exemplo 2: (IMO-1999) Ache todos os primos p e inteiros positivos n tais que 



Resolução: Primeiro, notemos que (1,p) sempre é solução. Agora, suponhamos que p divida n. Portanto, pelo Lema de Hensel, o maior expoente na fatoração da segunda expressão é a  + 1, onde o maior expoente de p ao dividir n é a. Porém, o maior expoente na primeira expressão é (p - 1)a. Portanto, devemos ter


Portanto, devemos ver o caso em que p não divide n. Mostraremos que este caso é impossível, ou seja, que p deve dividir n

Escolhamos o menor primo ímpar que divide n. Chamemos de q. Logo, analisando a segunda expressão mod q


Como a ordem mod q (menor expoente tal que um número primo com q elevado a este expoente é congruente a um mod q) divide (q - 1) e 2n, ela divide seu mdc. Porém, (q  - 1) é primo com n. Logo, escrevemos nt = (q - 1)r +1. Reparemos, agora, que, para p diferente de 2, então n é ímpar, implicando que t seja impar (pois q - 1 é par).  Portanto, 


Como q é maior que 1, e q divide p, então q = p, absurdo, pois escolhemos n de tal modo que p não dividisse n. 

Para os que duvidavam, está aí! Resolvemos um problema da IMO nos baseando principalmente no Lema de Hensel. Porém, vamos dar mais um exemplo para os que não se familiarizaram com o espírito da coisa, mas antes, vamos fazer um passo-a-passo de como aplicar o Lema: 

Passo 1) Utilize o Teorema Fundamental da Aritmética no expoente
Passo 2) Utiliza ordem para encontrar o menor primo que divide o expoente. 
Passo 3) Se você tiver chegado a uma contradição, fim. Se não, ache ou estime o expoente deste primo com o Lema de Hensel. 
Passo 4) Se você chegar a uma contradição, pare. Caso contrário, continue com os primos, do menor para o maior, utilizando os passos de 2 a 4 repetidamente até acabar. 

Repare que, de fato, o nosso processo acaba, pois o expoente é obrigatoriamente finito. Logo, o que temos em mãos é um algoritmo que resolve problemas. Bonito, não? Porém, fique claro que o algoritmo, sem que se tenha a ideia certa no momento certo, não mata problema algum. Ou seja, ainda precisamos de raciocínio para fazer os problemas. 

Exemplo 3: (China - 2005 - Problema 6) Ache todos os inteiros não-negativos (x,y,z,w) tais que 



Resolução: Primeiro, vamos provar que x é menor que 3. Supondo x maior ou igual a 2, então, analisando mod 3, 


Agora, analisando mod 4, 


Portanto, analisando, agora, mod 8, 


Assim, x é menor que 3, como dissemos. (na verdade, isto só ocorre se y é diferente de zero)

Portanto, vamos analisar os diferentes casos para x : 


i) x = 0 (zero). Neste caso, temos 




Com isso, é fácil notar que o lado esquerdo é par e o direito, ímpar. Logo, nenhuma solução. 

ii) x = 1. Neste caso, tomar a equação  módulo 3 dá que z é ímpar. Analisando módulo 4, , e, reescrevendo, 


Que é impossível (desde que y teria de ser zero módulo 6, implicando y par, absurdo). Logo, w deve ser nulo. Portanto,  nossa equação se reescreve como 


Analisando, agora, a equação se y = 1, obtemos a solução (1,1,1,0). Agora, se y é maior que 1, 


Então, z = 6k + 3. Logo, 


Absurdo. 

iii) x = 2. Agora, . Portanto, podemos fatorar a equação inicial em 



Daí vemos que, por 7 não dividir o primeiro fator, 


Mas já analisamos a ultima equação! Logo, obtemos a solução (2,2,1,1) 

 - Agora, vamos à análise de quando y é zero. Neste caso, bem notado nos parêntesis, temos 




Agora, , que implica em 4 dividir x, que implica em 3 dividir o primeiro membro, ou seja, divide o segundo, absurdo. Portanto, z = 0, que implica em 

 

Pelo Lema de Hensel, como a maior potência de 2 que divide o lado direito é 8, então . Agora, como , então só podemos ter x = 1,2,3. Podemos descartar o 2, pois já o analisamos. Portanto, temos dois casos, que geram duas soluções: (1,0,0,0) e (3,0,0,1). Como terminamos a análise de casos, achamos todas as soluções, e terminamos o problema. 


Pode parecer que "qualquer" problema com expoentes se resolve por Hensel; no entanto, alguns se resolvem somente com ordem ou analisando módulos pequenos. Portanto, tome cuidado ao usar Hensel - há vezes que nem autorizados a fazer isto estamos! Vamos mostrar no próximo

Exemplo 5 (Errado): Prove que não há primos p,q com q>p>2 tais que 



Resolução: Ora, a ideia seria usar Hensel, é claro! Como q é maior que p, então q não divide p-1. Como ambos são primos, também não divide o expoente, e, logo, o maior expoente de q na expressão da direita é a soma dos dois anteriores, ou seja, 0, certo?

ERRADO! O Lema de Hensel diz, claramente, que p-1 tem que ser divisível por q para este valer. Portanto, nossa solução está errada - inclusive, olhando para o contra-exemplo abaixo fica claro: 


Agora que mostramos a utilidade do nosso teorema, vamos propor alguns problemas para você poder treinar. Os primeiros saem por congruências ou elementos mais simples que o Lema de Hensel. Porém, para alguns, precisaremos sim do Lema. Portanto, sejam criativos! 

P1: Ache todos os m,n,k tais que 



P2: (OBM) Ache todos os inteiros positivos x,a,b  tais que 



P3: (Preparação para o próximo) Ache todos os inteiros p,m,n, onde é primo impar, tais que 



P4: Ache todos os inteiros p,m,n, onde p é primo impar, tais que 


P5: (China) Prove que, se , então x=y=1. 

P6: Ache todas as soluções inteiras positivas de 



P7: (IMO Shortlist 2000) Ache todos os inteiros positivos a,m,n tais que 


P8: (IMO Shortlist 1997) Prove que se  têm os mesmos divisores primos, então  é uma potência de 2. 

P9: (Miklós-Schweitzer) Ache todas as triplas de inteiros positivos x, y, z tais que 

P10: (IMO-1990-Problema 3) Ache todos os inteiros n tais que  é também inteiro. 

Referência Bibliográfica: 

1 - SHINE, Carlos Y. O Lema de Hensel, como acessado em http://cyshine.webs.com/hensel.pdf, entre os dias 19 e 25 de Novembro de 2012. 

2 -  MARTINEZ, Fabio B. , MOREIRA, Carlos Gustavo T.D.A., SALDANHA, Nicolau C., TENGAN, Eduardo. Teoria dos Números, um passeio com primos e outros números familiares pelo mundo inteiro, segunda edição. Brasil: Projeto Euclides, 2011. 

3 - MUNIZ NETO, Antonio C. Tópicos de Matemática Elementar: Volume 5 - Teoria dos Números. Primeira Edição, Rio de Janeiro: SBM, 2012

Não se esqueçam de avaliar o post aqui embaixo. Qualquer dúvida, sugestão, nota ou correção, nos digam nos comentários! Além do mais, caso gostem do blog, recomendem para amigos que vocês acharem que vão gostar do blog. Até a próxima! 



Um comentário:

  1. Oi, Pedro

    Muito interessante este teorema de Hensel e mais ainda a forma como expôs a teoria do mesmo.

    Parabéns!

    ResponderExcluir

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...