USC - Qual é o menor inteiro positivo n, sabendo que 31 divide 5^n+n ?
a) 23
b) 30
c) 31
d) 68
e) 88

Passo 1

O problema pede o menor inteiro positivo n tal que
31 mid 5^n + n
O conteúdo é aritmética modular com exponenciação e resolução de congruências. Vamos usar o fato de que, em Z31, a ordem de 5 é um divisor de varphi(31)=30, e depois resolver um sistema usando classes modulares.

Passo 2

Primeiro a gente acha a ordem de 5 módulo 31. Pelos divisores de 30 testamos:
5^1 = 5 notequiv 1 pmod31, 5^2 = 25 notequiv 1 pmod31,
e
5^3 = 125 equiv 125 - 4cdot31 = 1 pmod31
Logo a ordem de 5 em Z31^* é 3, e por isso
5^n equiv 5^,n bmod 3 pmod31

Passo 3

Agora analisamos as três classes de n mod 3:
Caso nequiv 0pmod3.
Então 5^nequiv 1, e a congruência vira
1 + n equiv 0 pmod31 Longrightarrow n equiv -1 equiv 30 pmod31
Como pedimos também nequiv0pmod3, verificamos que 30equiv0pmod3, logo é consistente. Os n dessa classe são nequiv30pmod31, e o menor positivo é n=30.

Passo 4

Verificamos rapidamente os outros casos para confirmar que não há solução menor:
  • Se nequiv1pmod3 então 5^nequiv5 e
    5 + n equiv 0 pmod31 Longrightarrow n equiv 26 pmod31,
    mas 26equiv2pmod3, conflito com nequiv1pmod3.
  • Se nequiv2pmod3 então 5^nequiv25 e
    25 + n equiv 0 pmod31 Longrightarrow n equiv 6 pmod31,
    mas 6equiv0pmod3, conflito com nequiv2pmod3.
Logo a única solução menor que 31 é n=30.

Resposta

30

Exercícios de Livros Relacionados