Resposta
O único resultado que eu achei é que [tex3]n[/tex3] é uma potência de dois
Olimpíadas ⇒ (Coreia 1999) Divisibilidade Tópico resolvido
-
Deleted User 24633
- Última visita: 31-12-69
Ago 2020
20
11:54
(Coreia 1999) Divisibilidade
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]
O único resultado que eu achei é que [tex3]n[/tex3] é uma potência de dois
O único resultado que eu achei é que [tex3]n[/tex3] é uma potência de dois
-
Ittalo25
- Mensagens: 2349
- Registrado em: 18 Nov 2013, 22:11
- Última visita: 27-03-24
- Agradeceu: 299 vezes
- Agradeceram: 1401 vezes
Ago 2020
20
16:29
Re: (Coreia 1999) Divisibilidade
É 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]
[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]
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
-
Deleted User 24633
- Última visita: 31-12-69
Ago 2020
20
16:47
Re: (Coreia 1999) Divisibilidade
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]
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]
Editado pela última vez por Deleted User 24633 em 20 Ago 2020, 16:50, em um total de 1 vez.
-
- Tópicos Semelhantes
- Resp.
- Exibições
- Últ. msg
-
-
Nova mensagem Olimpíada da Coréia do Sul - Divisibilidade
por Auto Excluído (ID:17906) » » em Olimpíadas - 1 Resp.
- 1076 Exibições
-
Últ. msg por Ittalo25
-
-
- 1 Resp.
- 1098 Exibições
-
Últ. msg por Ittalo25
-
- 0 Resp.
- 1316 Exibições
-
Últ. msg por owen123
-
- 1 Resp.
- 872 Exibições
-
Últ. msg por Jigsaw
-
- 2 Resp.
- 937 Exibições
-
Últ. msg por rcompany
