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 é
R = 111\ldots111 = \sum_{i=0}^{1994}10^i.
Vamos usar aritmética modular para aproveitar que 10^6\equiv1\pmod{1001} e reduzir a soma.

Passo 2

Mostramos que 10^6\equiv1\pmod{1001} verificando separadamente em cada fator de 1001=7\cdot11\cdot13:
  • Módulo 7: 10\equiv3, 3^6\equiv1\pmod7.
  • Módulo 11: 10\equiv-1, (-1)^2\equiv1\pmod{11} e portanto (-1)^6=1.
  • Módulo 13: 10^6\equiv1\pmod{13} pois a ordem de 10 em \mathbb{Z}_{13}^* é 6.
    Pelo CRT segue 10^6\equiv1\pmod{1001}.

Passo 3

Como 10^6\equiv1, os termos 10^0,10^1,\dots,10^5 formam um ciclo cuja soma é
\sum_{i=0}^{5}10^i = \frac{10^6-1}{10-1}\equiv\frac{1-1}{9}=0\pmod{1001}.
Logo cada bloco de 6 potências soma zero módulo 1001.

Passo 4

Escrevemos 1995 = 6\cdot332 + 3. Assim
R = \sum_{i=0}^{1994}10^i = \underbrace{\sum_{i=0}^{5}10^i}_{\equiv0}\,+\underbrace{\sum_{i=6}^{11}10^i}_{\equiv0}\,+\cdots+\sum_{i=6\cdot332}^{6\cdot332+2}10^i.
Todos os 332 ciclos completos dão resto 0, sobrando apenas os três primeiros termos do ciclo:
10^{6\cdot332} + 10^{6\cdot332+1} + 10^{6\cdot332+2} \equiv 10^0 + 10^1 + 10^2 = 1 + 10 + 100 = 111 \pmod{1001}.

Resposta

111

Exercícios relacionados