It can be calculated that $\frac{555555}{7} = 79365$. What is the remainder of the number $5555\dots5555$ with a thousand $5$'s, when divided by $7$?
I did the following:
$$\begin{array}
& 5 \ \text{mod} \ 7=& &5 \\
55 \ \text{mod} \ 7= & &6 \\
555 \ \text{mod} \ 7= & &2 \\
5555 \ \text{mod} \ 7= & &4 \\
55555 \ \text{mod} \ 7= & &3 \\
555555 \ \text{mod} \ 7= & &0 \\
5555555 \ \text{mod} \ 7= & &5 \\
55555555 \ \text{mod} \ 7= & &6 \\
555555555 \ \text{mod} \ 7= & &2 \\
5555555555 \ \text{mod} \ 7= & &4 \\
\end{array}$$
It can be seen that the cycle is: $\{5,6,2,4,3,0\}$.
$$\begin{array}
& 1 \ \text{number =} &5 \\
7 \ \text{numbers =} &5 \\
13 \ \text{numbers =} &5 \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots & \\
985 \ \text{numbers =} &5 \\
991 \ \text{numbers =} &5 \\
997 \ \text{numbers =} &5 \\
998 \ \text{numbers =} &6 \\
999 \ \text{numbers =} &2 \\
\color{red}{1000} \ \color{red}{\text{numbers =}} &\color{red}{4} \\
\end{array}$$
From here, we can conclude that $\underbrace{555\cdots555}_{1000\ \text{times}} \ \text{mod} \ 7 = 4$.
However, I wasn't allowed to use a calculator and solved this in about 12 minutes. Another problem was that there was a time limit of about 5 minutes. My question is: Is there an easier and faster way to solve this?
Thanks a lot in advance!
Best Answer
${\rm mod}\ 7\!:\,\ \overbrace{55\cdots 55}^{1+3n\rm\,\ fives}\, =\, \dfrac{5(10^{1+3n}\!-1)}9\, \equiv\, \dfrac{-2\,(3^{1+3n}-1)}2 \,\equiv\, -3(\color{#c00}{3^3})^{n}\!+1 \equiv 4\ $ by $\ \color{#c00}{3^3\equiv -1},\ n$ odd