Olimpíadas(OBM/2008- 3 fase-N2)

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
golondrina
Pleno
Mensagens: 60
Registrado em: Qua 26 Dez, 2018 13:30
Última visita: 09-02-24
Ago 2022 05 09:22

(OBM/2008- 3 fase-N2)

Mensagem não lida por golondrina »

Prove que existem infinitos inteiros positivos n tais que [tex3]\frac{5^{n-2}-1}{n}[/tex3] pertence aos inteiros




Avatar do usuário
leozitz
2 - Nerd
Mensagens: 331
Registrado em: Qui 06 Jan, 2022 16:26
Última visita: 26-02-24
Ago 2022 05 13:56

Re: (OBM/2008- 3 fase-N2)

Mensagem não lida por leozitz »

isso é o mesmo que dizer q n divide [tex3]5^{n-2} - 1[/tex3] , passando para notação de congruencia
[tex3]5^{n-2}\equiv 1 \pmod n[/tex3]
a primeira ideia é pegar um primo, pq a gente sabe algumas coisas interessantes sobre esse tipo de congruencia, tipo o pequeno teorema de fermat, poderiamos usar o teorema de euler e tentar algumas coisas usando ordem, mas se voltarmos um pouco temos o seguinte.
[tex3]5^{p-1}\equiv1\pmod p[/tex3]
e se a gente conseguisse tranformar n - 2 em p - 1 ou algo parecido?
para isso toma n = 2p
então vamos ter [tex3]n^{2p-2}\equiv 1({\mod 2p})[/tex3] , se p for relativamente primo com 2 a gente pode separar essa congruencia em [tex3]5^{2p-2}\equiv 1 \pmod 2[/tex3] q é sempre verdade
e [tex3]5^{2p-2}\equiv 1\pmod p[/tex3] e isso é verdade pq a gente pode reescrever como
[tex3]{(5^{p-1})}^{2}\equiv 1^2 \equiv 1 \pmod p[/tex3] .
como isso vale para todo primo diferente de 5 acabou.
basta tomar n = 2p onde p é um primo maior que 5 e aquele número sera um inteiro




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”