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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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?

Answer 4

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.

Answer 5

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.