(AIME-83) Qual o resto da divisão de
por 49?
Passo 1
O enunciado pede o resto da divisão de
por
.
Aqui vamos usar teoria de congruências módulo (aqui
), em particular o Teorema de Euler (
) e, quando possível, descobrir a ordem de cada base para reduzir ainda mais os expoentes.
Aqui vamos usar teoria de congruências módulo
Passo 2
Como
, vale
Mas podemos achar a ordem exata de
módulo
. Calculamos potências pequenas:
Logo a ordem de
módulo
é
.
Passo 3
Reduzimos o expoente
módulo
:
E como
temos
Passo 4
De modo análogo, como
, temos
Buscando a ordem de
:
Então a ordem de
módulo
é
. Reduzindo o expoente
:
Passo 5
Somando os restos:
Resposta
O resto da divisão de
por
é
.