What is $\underbrace{555\cdots555}_{1000\ \text{times}} \ \text{mod} \ 7$ without a calculator

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!

Solution 1:

${\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

Solution 2:

After noting $555555$ is divisible by $7$, note further that $555555\times 10^r$ is divisible by $7$ for any positive integer $r$. So you can cast out groups of six $5$s starting at the most significant digit, without changing the remainder on division by $7$. This gets rid of $996$ of the $5$s, leaving $5555$. Then $4949$ is obviously divisible by $7$ leaving $606$, and simple division then gives the remainder $4$.

Solution 3:

Note that $111111$ is divisible by $7$. This follows either from $111111 = \frac{10^6-1}{9}$ where $10^6-1$ is divisible by $7$ by Fermat's little theorem, or from the factorization $111111 = 111 \cdot 1001 = 111 \cdot 7 \cdot 11 \cdot 13$. This implies that $555555$ is also divisible by $7$, hence $$ \underbrace{555 \cdots 5}_{k \text{ times } 5} \mod 7 $$ is periodic with period $6$: if $k = 6a+b$, then $$ \underbrace{555 \cdots 5}_k = \underbrace{5555}_b + 555555 \cdot 10^b + 555555 \cdot 10^{6+b} + \cdots + 555555 \cdot 10^{6(a-1)+b} $$ where all terms (expect the first) are divisible by $7$. You can now draw the desired conclusion, after noting that $1000 \equiv 4 \mod 6$.

Solution 4:

There are some great answers here, but If your doing mental math, this might be the easiest if you basic modular arithmetic properties. First look at the pattern 5, 55, 555, 555.... If you notice that this can be written as

$a_1 = 5$ and $a_n = 10a_{n-1}+5$

This produces the pattern. Now if we perform the modulo we get

$a_n \equiv 3a_{n-1}-2~\mod 7$.

This is a lot easier to work with. We can then do the same method you did, calculating the cycle:

$5 \equiv a_1 \equiv 5 \mod 7$

$55 \equiv 3(5)-2 \equiv 6 \mod 7$

$555 \equiv 3(6)-2 \equiv 2 \mod 7$

$5555 \equiv 3(2)-2 \equiv 4 \mod 7$

$55555 \equiv 3(4)-2 \equiv 3 \mod 7$

$555555 \equiv 3(3)-2 \equiv 0 \mod 7$

$5555555 \equiv 3(0)-2 \equiv 5 \mod 7$

Therefore the cycle is, as you said ${(5,6,2,4,3,0)}$ Now $1000 \equiv 10(10)(10) \equiv 4(4)(4) \equiv 4(16) \equiv 4(4) \equiv 4 \mod 6$. So we pick the $4$th element, therefore the answer is $4$