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

Question

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!

Answer 1

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$.

Answer 2

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$.

Answer 3

Now since you already know $555555\bmod 7 = 0$, $$555555\cdot1000001 \bmod 7 = 0\\ 555555\cdot 1000001000001\bmod 7 = 0\\ \vdots$$

Would calculating this to find the pattern more manageable for you to extend a few more 5's? $$555\bmod 7= [(55\bmod 7)\cdot3-2]\bmod7\\5555\bmod 7= [(555\bmod 7)\cdot3-2]\bmod7\\\vdots \\ \underbrace{555\cdots555}_{n\ \text{times}} \bmod7 = [(\underbrace{555\cdots555}_{n-1\ \text{times}} \bmod7)\cdot3-2]\bmod 7$$

Answer 4

1/7=0.14285714285.......................

So, there you see a period of 6 in repetition of digits. So, any number written 6 times side by side is divisible by 7. This can be extended to same number written multiples of 6 times. [1000/6 ]=166 with remainder of 4 number of 5s. rem(5555/7)=4. Hence the answer. This can be used for a shortcut.

Answer 5

You can use this way to solve: \begin{eqnarray} \underbrace{55\cdots5}_{100\ \text{times}} \ \text{mod} \ 7&\equiv&\sum_{i=0}^{9}\underbrace{55\cdots5}_{10\ \text{times}}\times 10^{10i}\ \text{mod} \ 7\\ &\equiv&4\sum_{i=0}^{9}3^{10i}\ \text{mod} \ 7\\ &\equiv&4\sum_{i=0}^{9} 59049^{i}\ \text{mod} \ 7\\ &\equiv&4\sum_{i=0}^{9} 4^{i}\ \text{mod} \ 7\\ &\equiv&4\times\frac{4^{10}-1}{4-1}\ \text{mod} \ 7\\ &\equiv&4 349525 \ \text{mod} \ 7\\ &\equiv&4 \ \text{mod} \ 7\\ \end{eqnarray}

Answer 6

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$

Answer 7

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

Answer 8

$$\frac{5}{9}\left(10^{1000}-1\right) \equiv \frac{-2}{2}\left(10^{4}-1\right) \equiv 1-3^4 \equiv -80 \equiv 4\pmod{7}.$$

Answer 9

Set $C = \displaystyle \sum_{i=0}^{999}5\cdot 10^i$.

Applying the summation formula for a geometric series,

$\quad \displaystyle C = 5 \, (1-10^{1000}) \,(1-10)^{-1}$

Continuing,

$\quad \displaystyle C \equiv 5 \, (1-3\times{3^3}^{333}) \, 5^{-1} \equiv 1 - 3\times(-1)^{333} \equiv 4 \pmod{7}$

Answer 10

There are many great answers already written up, so I'm not sure if this is going to add anything, but for what it's worth, here's how I did it.

Recognise that $\underbrace{555\cdots555}_{1000\ \text{times}} = 5\cdot \underbrace{111\cdots111}_{1000\ \text{times}} = 5 \cdot 9^{-1} \cdot \underbrace{999\cdots999}_{1000\ \text{times}} = 5 \cdot 9^{-1} \cdot (10^{1000}-1)$

Working modulo $7$,

$10^{1000}-1 \equiv 3^{1000} - 1 = 3^{6\cdot 166 + 4} - 1 {\equiv} 80 \equiv 3 \pmod 7$

The modular inverse of $9$ is $4 \pmod 7$.

So the final residue is $5\cdot 4 \cdot 3 \equiv 4 \pmod 7$.