# 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?

• Think about this number as: $$\sum_{i=0}^{999}5\cdot 10^i$$ Commented Jan 1, 2015 at 15:52
• Would calculating this to find the pattern more manageable for you? $$555\bmod 7= [(55\bmod 7)\cdot3-2]\bmod7\\5555\bmod 7= [(555\bmod 7)\cdot3-2]\bmod7$$ Commented Jan 1, 2015 at 15:57
• What you describe looks like a perfectly good fast way to solve the problem. However, you leave out important details of how you actually did the calculations you mention, which can make a huge difference in how much work it takes. For example, how did you calculate $555555 \bmod 7$? Did you perform long division to obtain the quotient and remainder? Or did you use your previously calculated value of $55555 \bmod 7$ to perform a much smaller calculation? Or did you use the given hint to immediately obtain the value?
– user14972
Commented Jan 1, 2015 at 16:05

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

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

• Note: I'd rather reduce to $-101$ by subtracting $5656$ and knowing that $98=7\times 14$ this would leave me with $-3\equiv 4$ for the remainder. But that would be a personal preference. Commented Jan 1, 2015 at 16:20
• @KimJongUn It's impossible to have any idea what answer was "intended" without knowing much further context. Commented Jan 1, 2015 at 19:04
• @MarkBennet, I think you mean 4949 is divisible by $7$. Commented Jan 3, 2015 at 22:07
• @DaneBouchie Good spot - I've edited accordingly. Thanks! Commented Jan 3, 2015 at 22:09

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

• Note that $555555$ being divisble by $7$ is already given in the question. Commented Jan 1, 2015 at 16:10

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$

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.

• Fun solution. I wonder why your 1st sentence implies the 2nd though. Care to elaborate? Thanks. Commented Jan 1, 2015 at 18:19

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

• It'd be helpful to say which way you deduce $\,10^{1000}\equiv 10^4.\,$ Is it different than my answer? Commented Jan 1, 2015 at 18:59
• @BillDubuque: I just used $10^6\equiv 1\pmod{7}$ that comes from Fermat's little theorem. Commented Jan 2, 2015 at 18:43

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}

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

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

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