208 (Argentina-95)- Achar o resto da divisão de 111…111 (com 1995 dígitos 1) por 1001.
Passo 1
O enunciado pede o resto da divisão do número formado por 1995 dígitos “1” por 1001. Esse número é
Vamos usar aritmética modular para aproveitar que
e reduzir a soma.
Passo 2
Mostramos que
verificando separadamente em cada fator de
:
- Módulo 7:
, . - Módulo 11:
, e portanto . - Módulo 13:
pois a ordem de 10 em é 6.
Pelo CRT segue.
Passo 3
Como
, os termos
formam um ciclo cuja soma é
Logo cada bloco de 6 potências soma zero módulo 1001.
Passo 4
Escrevemos
. Assim
Todos os 332 ciclos completos dão resto 0, sobrando apenas os três primeiros termos do ciclo:
Resposta
111