Calcule o resto da divisão de 7^34 por 51 e o resto da divisão de 5^63 por 29.

Passo 1

Beleza, o exercício pede para a gente achar dois restos de divisão bem grandões:
  1. o resto de a^phi(n) equiv 1 pmod n dividido por 51
  2. o resto de dividido por 29
Isso é conteúdo de aritmética modular e, mais especificamente, da Teoria de Números com a ideia do Teorema de Euler. Para resolver, a gente vai usar:
  • A função totiente de Euler , que diz quantos números menores que são primos com .
  • O Teorema de Euler: se , então
Com isso, dá pra reduzir exponenciais gigantes a coisas bem mais simples.

Passo 2

Primeira parte: resto de phi(51)=phi(3),phi(17)=(3-1),(17-1)=2cdot16=32 .
  1. Calcular 7^32equiv1pmod51 . Como e é multiplicativa:
  1. Como , pelo Teorema de Euler:

Passo 3

Agora reduzimos o expoente 34:
7^34 = 7^32+2 = 7^32cdot7^2 equiv 1cdot7^2 pmod51
Então só falta 7^34equiv49pmod51 . Logo

Passo 4

Segunda parte: resto de 5^28equiv1pmod29 .
  1. Calcular . Como 29 é primo, .
  2. Como , vale

Passo 5

Reduzimos o expoente 63 em relação a 28:
63 = 28cdot2 + 7 Longrightarrow 5^63 = (5^28)^2cdot5^7 equiv 1^2cdot5^7 = 5^7 pmod29
Bora calcular 5^63equiv5^7equiv28pmod29 módulo 29 passo a passo:
5 =25
5 =25·5=125≡125−(29·4)=125−116=9
5 =9·5=45≡45−29=16
5 =16·5=80≡80−58=22
5 =22·5=110≡110−87=23
5 =23·5=115≡115−(29·3)=115−87=28
Então

Resposta

Resto de por 51 = 49
Resto de por 29 = 28

Exercícios relacionados