Achar os restos das seguintes divisões:
por 51
Passo 1
O enunciado pede: achar o resto da divisão de
por
.
Informações dadas e relevantes: o número base é , o expoente é
e o divisor (módulo) é
. Queremos encontrar o inteiro
tal que, quando dividimos
por
, o resto seja
com
.
Informações dadas e relevantes: o número base é
Passo 2
Escolha do método: vou usar o teorema de Euler (redução de expoente módulo
). Raciocínio: quando a base e o módulo são primos entre si (isto é, têm máximo divisor comum igual a
), o teorema de Euler permite reduzir expoentes grandes usando
. Isso normalmente torna o cálculo manual bem simples. Depois faço uma checagem alternativa via congruências modulares menores (método chinês) para confirmar o resultado.
Passo 3
Verificar se podemos aplicar Euler: calcular
. Como
e
não é múltiplo de
nem de
, segue que
Portanto podemos aplicar o teorema de Euler.
Passo 4
Lembrete do teorema de Euler e definição de
: o teorema de Euler diz que, se
, então
onde
é a função totiente de Euler — ela conta quantos inteiros entre
e
são coprimos com
.
Calcular
. Como
com
e
primos distintos, usa-se a fórmula multiplicativa:
Faço as contas passo a passo:
Logo
Passo 5
Aplicar Euler para reduzir o expoente: como
e
, temos
Escrevo
, então
Assim basta calcular
e reduzir módulo
.
Passo 6
Calcular
e reduzir:
Agora reduzimos
módulo
. Multiplicando
por
dá
. Subtraindo,
Portanto
ou seja, o resto da divisão é
.
Passo 7
Cheque rápido por congruências modulares (controle): verificação separada por módulos primos
e
.
Calcular
e reduzir em módulo
:
, então
. Assim buscamos
tal que
e
;
satisfaz ambos, confirmando o resultado anterior.