All 3 digit numbers are written into one long number $N=100101102...999$. Find $N \pmod {210}$.

Question

I have no idea how to solve this, but I feel that $210=2\times3\times5\times7$ has something to do with the problem.

Answer 1

Let's solve it explicitly based on JMoravitz's suggestion.

For clarity, let's write out the number with spacing between 3 digits:

$$ N = 100 101 102 103 ... 998 999. $$

We claim the following:

$$ \begin{align} N &\equiv 1 \pmod 2, \quad (1) \\ N &\equiv 0 \pmod 3, \quad (2) \\ N &\equiv 4 \pmod 5, \quad (3) \\ N &\equiv 2 \pmod 7. \quad (4) \\ \end{align} $$

Once $(1)$ through $(4)$ are verified, it is straightforward to see that $N \equiv 9 \pmod 210$ where $210 = 2\cdot3 \cdot5\cdot7.$

Proof:

1. Note that $(1)$ and $(3)$ are obvious.

2. Prove (4) using the divisibility rule for 7 stated in the reference above:

"Form the alternating sum of blocks of three from right to left"

Based on this rule:

$$\begin{align} N &\equiv 999 - 998 + 997 - 996 + ... + 101 - 100, \pmod 7 \\ &\equiv 1 + 1 + ... + 1, \pmod 7 \\ &\equiv 450 = 7 \cdot 64 + 2, \pmod 7\\ &\equiv 2 \pmod 7 \end{align} $$

3. Prove (3) using the divisibility rule for 3 stated in the reference above:

"Subtract the quantity of the digits 2, 5, and 8 in the number from the quantity of the digits 1, 4, and 7 in the number. The result must be divisible by 3"

To count the digits correctly, we can rely on the pseudo code below to generate (print) the number N:

for (i = 1; i < 10; i++) {
    for (j = 0; j < 10; j++) {
        for (k = 0; k < 10; k++) { 
           print one three-digit block: i, j, k
        }
    }
}

Thus,

• There are 100 blocks having the same 'i' digit occur in the leftmost digit of the block: 10 'j' values times 10 'k' values. The total counts are 300 blocks with 'i' in the {1,4,7} group and 300 with 'i' in {2, 5, 8}.

• Similarly, there are 100 blocks having the same 'j' digit occur in the middle digit of the block: 10 'i' values times 10 'k' values. The total counts are 300 in the {1,4,7} group and 300 in {2, 5, 8}.

• There are 100 blocks having the same 'k' digit occur in the rightmost digit of the block: 10 'i' values times 10 'j' values. The total counts are 300 in the {1,4,7} group and 300 in {2, 5, 8}.

Thus, the total counts are 900 in the {1,4,7} group and 900 in {2, 5, 8}, which means:

$$ N \equiv 0 \pmod 3$$

Answer 2

Your number is $$\begin{align} &100(1000)^{899}+101(1000)^{898}+\cdots+999(1000)^0\\ &=\sum_{n=0}^{899}(999-n)(1000)^{n}\\ &=\sum_{n=0}^{899}999(1000)^{n}-\sum_{n=0}^{899}n(1000)^{n}\\ &=999\frac{1000^{900}-1}{1000-1}-\left.x\frac{d}{dx}\sum_{n=0}^{899}x^{n}\right\rvert_{x=1000}\\ &=1000^{900}-1-\left.x\frac{d}{dx}\frac{x^{900}-1}{x-1}\right\rvert_{x=1000}\\ &=1000^{900}-1-\left.x\frac{(x-1)900x^{899}-(x^{900}-1)}{(x-1)^2}\right\rvert_{x=1000}\\ &=1000^{900}-1-1000\frac{(999)900(1000)^{899}-1000^{900}+1}{999^2}\\ &=1000^{900}-1-1000\frac{898100(1000)^{899}+1}{999^2}\\ &\equiv1-1-6\frac{0+1}{5^2}\mod{7}\\ &\equiv1/5^2\mod{7}\\ &\equiv3^2\mod{7}\\ &\equiv2\mod{7}\end{align}$$

Since the last digit is $9$, the number is $\equiv1$ modulo $2$ and $\equiv4$ modulo $5$.

Mod $3$, use the familiar digit summing rule. Each nonzero digit appears the same number of times, and $1+2+\cdots+9=45$ is divisible by $3$. So the sum of digits is divisible by $3$. So the number is $\equiv0$ modulo $3$. To finish, I didn't need the Chinese Remainder Theorem or anything like that, because it just sort of stands out that $9$ (a small number) satisfies all the conditions.