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

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?

• Do you know the divisibility rule for 239?? – Saketh Malyala Apr 16 '17 at 21:39
• Take the digits in blocks of seven from right to left and add each block. – Saketh Malyala Apr 16 '17 at 21:40
• That's why it works beautifully w/ this problem – Saketh Malyala Apr 16 '17 at 21:40
• This is because $239 \times 41841 = 9999999$ – DHMO Apr 16 '17 at 21:41

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

• How did you get the sum modulo $239$? – user19405892 Apr 16 '17 at 21:44
• @user19405892: according to the $7$ years old Gauss, $0+1+2+\ldots+9999999 = 9999999\cdot 5000000$ is a multiple of $239$ as well. – Jack D'Aurizio Apr 16 '17 at 21:46
• @user19405892 Because $$1+2+3+...n=\frac{n(n+1)}{2}$$ – Jaideep Khare Apr 16 '17 at 21:46

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