0
$\begingroup$

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?

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.