Olimpíadas ⇒ divisibilidade

[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?

[Vinisth]

Olá quevedo,

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

Abraço !

[quevedo]

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

[Ittalo25]

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]15^{15^{15}-1}\equiv -1 \mod(p)[/tex3]

[tex3]15^{2\cdot 15^{15}-2}\equiv 1 \mod(p)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]p-1|2\cdot (15^{15}-1) [/tex3]

[tex3]p-1|2\cdot (15^{5}-1)\cdot (15^{10}+15^5+1) [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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