Prove that $N$ is a multiple of $239$

Question

Consider the $10$ million $7$-digit numbers, where numbers smaller than one million have been padded with zeros on the left to make them $7$ digits long as well: $$\{0000000, 0000001,\ldots, 0000099, 0000100,\ldots,0999999,1000000,\ldots,9999998,9999999\}.$$ Let $N$ be a $70$ million digit number formed by concatenating these $10$ million $7$-digit numbers together in any order. Prove that $N$ is a multiple of $239$.

I didn't see how to use the fact that $N$ is a concatenation of these strings to prove divisibility by the prime $239$. How can we do that?

Answer 1

$239$ is a divisor of $9999999=10^7-1$, i.e. $10^7\equiv 1\pmod{239}$. It follows that by concatenating such strings in any order, the resulting number $N$ is $$ \equiv 0+1+2+3+\ldots+9999999\pmod{239} $$ i.e. $\equiv\color{red}{0}\pmod{239}$.

Answer 2

Here's some intuition as to why would $10^7\equiv 1\pmod{239}$ have to be true.

If you concatenate two $7$ digit numbers $a$ and $b$ then you have that their concatenation is equal to $a\cdot10^7+b$,and for three numbers $a,b,c$ you get $a\cdot 10^{14}+b\cdot 10^7+c$ and the pattern continues.

Now if $10^7\not\equiv1\pmod{239}$ then the concatenation of $a,b$ and $b,a$ aren't the same $$a\cdot 10^7+b\equiv b\cdot 10^7+a\pmod{239}\\10^7(a-b)\equiv a-b\pmod{239}\\(a-b)(10^7-1)\equiv 0\pmod{239}$$ unless $a\equiv b\pmod{239}$ now take $N$ which ends with $00000010000002$ and take the same $N$ but change the ending to $00000020000001$ instead.

Those two numbers don't give same remainders $\mod{239}$ since $2\cdot10^7+1\not\equiv10^7+2\pmod{239}$ by assumption which contradicts that $N$ must be a multiple of $239$.

So we must have that $10^7\equiv 1\pmod{239}$ so $$N\equiv 1+2+3+\cdots+9999999\pmod{239}$$