Olimpíadasdivisibilidade

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
quevedo
sênior
Mensagens: 43
Registrado em: Qua 20 Abr, 2016 17:52
Última visita: 03-05-23
Jun 2018 03 23:10

divisibilidade

Mensagem não lida por quevedo »

A soma dos 4 menores fatores primos distintos do número 15^15^15 + 15 é igual a:
a) 33
b) 39
c) 27
d) 29
e) 41
Resposta

b
Pelo problema fatorando ficaríamos: 15x(15^(15-1) + 1)
Daí teríamos que os fatores primos são 2, 3, 5 => 2 pq a soma de dois ímpares é par. O problema é achar o 4 número.
Claro que pela resposta dá pra saber que é 29, mas como chegar a esse resultado?




Avatar do usuário
Vinisth
4 - Sabe Tudo
Mensagens: 1244
Registrado em: Qui 10 Jun, 2010 23:39
Última visita: 11-07-23
Jun 2018 03 23:42

Re: divisibilidade

Mensagem não lida por Vinisth »

Olá quevedo,

DICA:
Você lista os outros primos: 7, 11, 13, 17, 19, 23, 29 ...
EDIT
Realmente, passei digitando sem pensar ...

Abraço !

Última edição: Vinisth (Seg 04 Jun, 2018 20:29). Total de 3 vezes.



Avatar do usuário
Autor do Tópico
quevedo
sênior
Mensagens: 43
Registrado em: Qua 20 Abr, 2016 17:52
Última visita: 03-05-23
Jun 2018 04 17:32

Re: divisibilidade

Mensagem não lida por quevedo »

Desculpe amigo mas não entendi pq 15 = -1 (mod 29) ?
Pois assim 15 + 15 = -2 (mod 29), mas 30 = 1 (mod 29)



Avatar do usuário
Ittalo25
5 - Mestre
Mensagens: 2349
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 27-03-24
Abr 2021 10 02:27

Re: divisibilidade

Mensagem não lida por Ittalo25 »

[tex3]15^{15^{15}}+15=15\cdot (15^{15^{15}-1}+1)[/tex3]

Supondo um primo p maior que 5, devemos ter:
[tex3]15^{15^{15}-1}\equiv -1 \mod(p)[/tex3]
[tex3]15^{2\cdot 15^{15}-2}\equiv 1 \mod(p)[/tex3]
Como mdc(15,p) = 1, pelo pequeno teorema de Fermat devemos ter:
[tex3]p-1|2\cdot (15^{15}-1) [/tex3]
[tex3]p-1|2\cdot (15^{5}-1)\cdot (15^{10}+15^5+1) [/tex3]
[tex3]p-1|2\cdot (15-1)\cdot (15^4+15^3+15^2+15+1)\cdot (15^{10}+15^5+1) [/tex3]
[tex3]p-1|28\cdot (15^4+15^3+15^2+15+1)\cdot (15^{10}+15^5+1) [/tex3]
Isso mostra que [tex3]p-1=28\rightarrow \boxed{p=29} [/tex3] funciona.

Isso é bom porque limita por cima, agora só precisamos testar se algum dos primos 7, 11, 13, 17, 19, 23 funciona. Aí deixo com você.



Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

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

Voltar para “Olimpíadas”