# Find the smallest $n \ge 1000$ such the sum $1+11+111+⋯+11⋯11 (n$ digits) is divisible by $101$

I get another training problem, for a Romanian 6th grader competition, for which I have no answer. Find the smallest $$n \ge 1000$$ such the sum $$1+11+111+⋯+11⋯11 (n digits)$$ it is divisible by 101. I am familiar with the sum, I know how to compute it, but I can see how I can reason about the divisibility by $$101$$.

I did a numeric analysis on it, and it looks that the solution is $$n=1121$$, while the first numbers for which the sum is divisible by 101 are $$110,313, 403, 404, 514, 717, 807,808, 918$$ . Also I did notice that $$1111$$ is divisible by $$101$$, and I also seen that the pattern $$123456790$$ keeps repeating on the sum.

If you consider the remainders upon dividing every term by $$101$$ we obtain the following sequence:

$$1 \equiv 1 \pmod {101}$$ $$11 \equiv 11 \pmod {101}$$ $$111 \equiv 10 \pmod {101}$$ $$1111 \equiv 0 \pmod {101}$$ $$11111 \equiv 1 \pmod {101}$$ $$\cdots$$

It is not hard to conclude that the the remainders repeat each $$4$$ terms. Also note that any sum of $$4$$ consequtive terms will have remainder $$1+11+10+0 = 22$$ upon division by $$101$$. Thus:

$$\sum_{i=1}^{1000} a_n \equiv 22\cdot 250 \equiv 46 \pmod{101}$$

where $$a_n = 11 \cdots 1 (n$$ digits ). Now you want to solve the following equations:

$$46 + 22k_1 \equiv 100 \pmod{101}$$ $$46 + 22k_2 \equiv 89 \pmod {101}$$ $$46 + 22k_3 \equiv 0 \pmod {101}$$

The first one comes from adding $$k_1$$ blocks of $$4$$ terms and adding just one more afterwards to bring the remainder to $$0$$. The second one comes from ading $$k_2$$ blocks of $$4$$ terms and adding the next two afterwards. The last equation arises as one of the ways to reach remainder $$0$$ is to keep adding $$k_3$$ blocks of $$4$$ terms and the next three afterwards.

Let $$k_1,k_2,k_3$$ be the least nonegative solutions to the congruence relations. Then we have $$n_1 = (250+k_1)\cdot 4 + 1$$, $$n_2 = (250+k_2)\cdot 4 + 2$$, $$n_3 = (250+k_3)\cdot 4 + 3$$. The smallest integer out of $$n_1,n_2,n_3$$ is the wanted $$n$$.

Since $$111100\ldots00$$ is divisible by $$101$$, you can repeatedly remove the leading four $$1$$'s from $$111\ldots 111$$ until you get to one of $$0,1,11,$$ or $$111$$. And you can reduce $$111$$ still further to $$10$$. So you get the sum $$1+11+10+0+1+11+10+0+\ldots$$

mod $$101$$. Can you take it from there?

Firstly let's find $$F(n) = 1+11+111+...+\frac{10^n-1}{9}$$.

$$F(n) = \sum_{i=1}^n\frac{10^i-1}{9} = \frac{1}{9}(\sum_{i=1}^{n}10^i-\sum_{i=1}^n1) = \frac{10}{9}\frac{10^n-1}{9}-\frac{n}{9}=\frac{10^{n+1}-9n-10}{81}$$

$$101 | F(n) \implies 101 | (10^{n+1}-9n-10)$$ as gcd(101, 81) = 1

$$10^{n+1} \equiv 9n+10 \mod{101}$$

Notice

$$10^{n+1} \equiv 10, -1, 91(-10), 1 \mod{101} \textrm{ when }n \equiv 0, 1, 2, 3 \mod{4}$$ respectively.

Firstly, $$9^{-1} \equiv 45\mod{101}$$

Consider cases:

$$n \equiv 0 \mod{4}, 9n+10\equiv10,n\equiv0 \mod{101} \implies n \equiv 0 \mod{404}$$

$$n \equiv 1 \mod{4}, 9n+10\equiv-1,9n\equiv-11,n \equiv(45)(-11)\equiv-495\equiv10\mod{101}\implies n\equiv313\mod{404}$$

Similar for the other 2 cases, $$n\equiv0, 110, 313, 403 \mod {404}$$

$$n = 0, 110, 313, 403, ..., 808, 918, 1121, ...$$ so 1121 is the smallest integer >=1000.

Working $$\pmod {101}$$ we see that the remainders of the summands are periodic with cycle $$\{1,11,10,0\}$$.

We want the sum of the remainders to be a multiple of $$101$$.

Can we get $$101$$? Well $$1+11+10=22$$. To get to a multiple of $$101$$ we'll have to go through the cycle a number of times and then add $$0$$, $$1$$ or $$12$$. Thus we seek $$k$$ such that $$22k\equiv 0,-1,\, \text {or }\,-12 \pmod {101}$$

It's clear that the least solution for $$0$$ is $$101$$.

By brute force (though you could use the euclidean algorithm):

The least solution for $$-1$$ is $$78$$.

The least solution for $$-12$$ is $$27$$.

Starting with multiples $$101$$, we see that the first solution would be $$1212$$.

Now considering $$78$$, we note that $$78\times 4 = 312$$, $$(78+101)\times 4=716$$, $$78+2\times 101=1120$$. As $$1120+1=1121<1212$$, that's the lead contender for now.

We need to check that we don't get a smaller value if we start from $$27$$. But $$27\times 4=108$$, and adding $$4\times 101=404$$ to that repeatedly the first value $$≥1000$$ we come to is $$1320$$ so that's no good. (just to be careful, the prior value is $$916$$ and adding two to that does not get you to $$1000$$).

Thus we confirm your result, $$1121$$ is optimal.

• "...and then add $0,1,$ or $12$." – TonyK Feb 22 at 9:52
• @Tonyk True...not sure why I neglected that. Will edit. – lulu Feb 22 at 9:53
• @TonyK edited. $\quad$ – lulu Feb 22 at 9:56

Denote $$1_n$$ by the number with $$n$$ digits, each one equal to $$1$$. E.g. $$1_3 = 111$$.

Start with looking at the remainders when $$1_n$$ is divided by $$101$$. Note that $$1_n = 10 \times 1_{n-1} + 1$$, and $$1_1 = 1$$. Therefore, inductively we get that the sequence $$1_n \mod 101$$(for $$n \geq 1$$) looks like $$1,11,10,0,1,11,10,0,...$$

Now, let us denote $$b_m = \sum_{n=1}^m 1_n$$. We are interested in $$b_m \mod 101$$. For this, we break $$m = 4k,4k+1,4k+2,4k+3$$.

For $$m = 4k$$, clearly $$b_m \pmod{101} = 22k$$. For $$m = 4k+1$$ it is $$22k+1$$, for $$m = 4k+2$$ it is $$22k+12$$, for $$m = 4k+3$$ it is $$22k + 22$$.

Therefore, we need to solve these equations : $$22k \equiv 0 \pmod{101} \\ 22k+1 \equiv 0 \pmod{101} \\ 22k+12 \equiv 0 \pmod{101} \\ 22(k+1) \equiv 0 \pmod{101}$$

Each of these can be solved, since $$22$$ and $$23$$ are invertible mod $$101$$. The first and fourth equations have obvious solutions. I list the corresponding solutions below. $$k \equiv 0 \mod 101 k \equiv 78 \mod 101 k \equiv 27 \mod 101 k \equiv -1 \mod 101$$

Thus, the corresponding solutions to $$b_m = 0$$ are(for each $$l \geq 0$$) : $$4(101l) = 404l \\ 4(101l+78) + 1 = 404l + 313 \\ 4(101l+27) +2 = 404l+110 \\ 4(101l-1) + 3 = 404l-1$$

Now, we combine all this into any solution being of the form $$404l + d$$ where $$l \geq 0$$ and $$d \in \{0,(-1=) 403,110,313\}$$.

Finally, it is easy to see that $$404 \times 2 + 313 = 1121$$ is the smallest solution having four digits.

I feel the need to add this, but I think it will be nice to see.

Let us replace $$101$$ by an integer $$N$$ which is coprime to $$2$$ and $$5$$. Use the pigeonhole argument, to show that $$N$$ is divisible by $$1_m$$ for some $$1 \leq m \leq n+1$$. (Hint : consider the remainders when $$1_m$$ is divided by $$n$$).

Pick the smallest $$M$$ such that $$N$$ divides $$1_M$$. Then, we can now look at the sequence of numbers $$b_m = \sum_{i=1}^m 1_n$$, and ask : does there exist a number $$F$$ such that $$b_F$$ is a multiple of $$N$$?

Indeed, there is! To see this, note that $$1_M$$ is a multiple of $$N$$. Suppose that $$b_M$$ leaves a remainder $$r$$ mod $$N$$.

We claim the following inductive formula holds: $$b_{kM} = b_M\left(\frac{10^{kM}-1}{10^M - 1}\right) + \sum_{i=1}^{k-1} 1_{iM}$$

This can be verified easily. Next, taking remainders modulo $$N$$ above, note that $$1_{iM}$$ is a multiple of $$n$$ since $$1_M$$ is a multiple of $$n$$. So, we just get : $$b_{kM} \equiv r\times \left(\frac{10^{kM-1}}{10^M-1}\right) \pmod{N}$$

Observe that $$\frac{10^{kM} - 1}{10^M-1} = \frac{1_{kM}}{1_M} = c_k$$ .Note that this is an integer.

Claim : there exists $$1 \leq K \leq N+1$$ such that $$N$$ divides $$c_K$$.

For this, use pigeonhole on the remainders of $$c_K$$ mod $$N$$. Note that two of $$c_1,...,c_{N+1}$$ have the same remainder mod $$N$$, say $$c_{s} > c_{t}$$. Then, $$N | c_s - c_t = 10^{t}(c_{s-t})$$ (you can check this). But $$N$$ is coprime to $$10^r$$, hence $$N | c_{s-t}$$. Take $$K = s-t$$.

Therefore, $$b_{KM} \equiv rc_K \equiv 0 \mod N$$.

Now, we can find infinitely many $$F$$ such that $$b_F$$ is a multiple of $$N$$, by taking $$b_{2F},b_{3F}$$ and so on.

IN the example of $$101$$, you can check that $$M = 4$$ and $$K = 101$$ worked.

• "Romanian sixth grader competition" : I would expect this to be, in the least, crazy stuff at sixth class level. – астон вілла олоф мэллбэрг Feb 22 at 9:53
• Your $23k$ should be $22k+22$, I think. (This is not the same as $23k$!) – TonyK Feb 22 at 9:54
• Thank you for the point out. – астон вілла олоф мэллбэрг Feb 22 at 9:55
• You are right guys, people who make the subjects must be crazy.. – motoras Feb 22 at 10:02
• I am adding something to my answer : I'd like to do more than just answer it, if you don't mind. – астон вілла олоф мэллбэрг Feb 22 at 10:03

Hint: In order to understand the sum, we should understand the terms that go into it. What is the $$n$$-digit number $$11\cdots 11$$ mod $$101$$? How many terms does it take for that sequence to repeat? Your observation that $$1111\equiv 0\mod 101$$ will be helpful here.