Olimpíadas ⇒ (Coreia 1999) Divisibilidade Tópico resolvido

[Auto Excluído (ID: 24633)]

Encontre todos os inteiros [tex3]n[/tex3] tais que [tex3]2^n −1[/tex3] é um múltiplo de [tex3]3[/tex3] e [tex3]\dfrac{2^n − 1}{3}[/tex3] é um divisor de [tex3]4m^2 + 1[/tex3] para algum inteiro [tex3]m.[/tex3]

Resposta

---

O único resultado que eu achei é que [tex3]n[/tex3] é uma potência de dois

[Ittalo25MOD]

É fácil ver que [tex3]ord_3(2) = 2 [/tex3], portanto [tex3]2|n [/tex3] e [tex3]n=2a [/tex3]

[tex3]\dfrac{2^{2a} − 1}{3} = \dfrac{4^{a} − 1}{3}[/tex3]

Agora se fizer [tex3]a = 2^k [/tex3] vai ficar melhor ainda, já que:

[tex3]\dfrac{4^{2^k} − 1}{3} = \dfrac{(4^{2^{k-1}}+1)(4^{2^{k-2}}+1)(4^{2^{k-3}}+1)(4^{2^{k-3}}+1)...(4^2+1)(4+1)(4-1)}{3} [/tex3]

Assim esse produto é divisível por 3.

Agora falta ver: [tex3]4m^2+1\equiv 0 \mod((4^{2^{k-1}}+1)(4^{2^{k-2}}+1)(4^{2^{k-3}}+1)(4^{2^{k-3}}+1)...(4^2+1)(4+1)) [/tex3]

Se todos esses temos do produtos forem coprimos, então o teorema chinês dos restos garante que existe solução.
Esses números da forma [tex3]F_n = 2^{2^k}+1 [/tex3] são conhecidos como números de Fermat e eles têm essa propriedade de que todos eles são primos entre si
Então [tex3]n = 2^{k+1} [/tex3] é solução. ou melhor [tex3]n = 2^u [/tex3] para [tex3]u\geq 1[/tex3]

Agora se [tex3]n = p\cdot 2^u [/tex3], com p ímpar e diferente de 1, então:

[tex3]\dfrac{4^{2^up} − 1}{3} = \dfrac{(4^{2^{u-1}p}+1)(4^{2^{u-2}p}+1)(4^{2^{k-3}p}+1)(4^{2^{k-3}p}+1)...(4^{2p}+1)(4^p+1)(4^p-1)}{3} [/tex3]

Se [tex3]4m^2+1 \equiv 0 \mod(\dfrac{4^{2^up} − 1}{3}) [/tex3], então: [tex3]4m^2+1 \equiv 0 \mod(\dfrac{4^{p} − 1}{3}) [/tex3]

Mas [tex3]\frac{4^p-1}{3} = \frac{(2^p-1)(2^p+1)}{3}[/tex3], e como p é ímpar, então [tex3]2^p+1 \equiv 0 \mod(3) [/tex3]

e sendo assim precisamos de: [tex3]4m^2+1 \equiv 0 \mod(2^p-1)[/tex3]

Como [tex3]2^p-1 \equiv 3 mod(4)[/tex3], se todos os divisores primos de [tex3]2^{p}-1[/tex3] fossem [tex3]1 \mod(4) [/tex3], então [tex3]2^{p}-1 \equiv 1 \mod(4)[/tex3], mas isso não é verdade, então pelo menos um divisor primo de [tex3]2^{p}-1[/tex3] é [tex3]3 \mod(4) [/tex3], seja b esse divisor.

[tex3]4m^2 \equiv -1 \mod(b) [/tex3]
[tex3](2m)^2 \equiv -1 \mod(b) [/tex3]

Só que -1 não é resíduo quadrático do primo b se [tex3]b \equiv 3 \mod(4) [/tex3], aqui na página 28

Então a única solução é [tex3]n = 2^u [/tex3]

[Auto Excluído (ID: 24633)]

Bem, parece que me faltou conhecimento; não sabia que todos os números de Fermat eram coprimos dois a dois.

Na parte final, dava para continuar por redução ao absurdo sobre o pequeno teorema de Fermat que eu acho mais trivial. Em geral se [tex3]p \equiv 3 \pmod 4[/tex3] e [tex3]p\mid a^2+b^2[/tex3] então [tex3]p\mid a,b[/tex3]