(AIME-83) Qual o resto da divisão de 6^83+ 8^63 por 49?

Passo 1

O enunciado pede o resto da divisão de
6^83 + 8^63
por 49.
Aqui vamos usar teoria de congruências módulo p^2 (aqui p=7), em particular o Teorema de Euler ( varphi(49)=42) e, quando possível, descobrir a ordem de cada base para reduzir ainda mais os expoentes.

Passo 2

Como gcd(6,49)=1, vale
6^42equiv1pmod49
Mas podemos achar a ordem exata de 6 módulo 49. Calculamos potências pequenas:
6^2=36, 6^3=36cdot6=216equiv20, 6^6=(6^3)^2=20^2=400equiv8,
6^7=6^6cdot6=8cdot6=48, 6^14=(6^7)^2=48^2=2304equiv1
Logo a ordem de 6 módulo 49 é 14.

Passo 3

Reduzimos o expoente 83 módulo 14:
83 = 14cdot5 + 13 Longrightarrow 6^83equiv6^13pmod49
E como
6^13=6^7cdot6^6equiv48cdot8=384equiv384-7cdot49=384-343=41,
temos
6^83equiv41pmod49

Passo 4

De modo análogo, como gcd(8,49)=1, temos
8^42equiv1pmod49
Buscando a ordem de 8:
8^2=64equiv15, 8^3=15cdot8=120equiv22,
8^6=(8^3)^2=22^2=484equiv43, 8^7=43cdot8=344equiv1
Então a ordem de 8 módulo 49 é 7. Reduzindo o expoente 63:
63 = 7cdot9 Longrightarrow 8^63equiv(8^7)^9equiv1^9=1pmod49

Passo 5

Somando os restos:
6^83+8^63equiv41+1=42pmod49

Resposta

O resto da divisão de 6^83+8^63 por 49 é 42.

Exercícios de Livros Relacionados