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$
4
  • $\begingroup$ Do you know the divisibility rule for 239?? $\endgroup$ Apr 16, 2017 at 21:39
  • 1
    $\begingroup$ Take the digits in blocks of seven from right to left and add each block. $\endgroup$ Apr 16, 2017 at 21:40
  • $\begingroup$ That's why it works beautifully w/ this problem $\endgroup$ Apr 16, 2017 at 21:40
  • 1
    $\begingroup$ This is because $239 \times 41841 = 9999999$ $\endgroup$
    – DHMO
    Apr 16, 2017 at 21:41

2 Answers 2

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$
3
  • 1
    $\begingroup$ How did you get the sum modulo $239$? $\endgroup$ Apr 16, 2017 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$ Apr 16, 2017 at 21:46
  • 1
    $\begingroup$ @user19405892 Because $$1+2+3+...n=\frac{n(n+1)}{2}$$ $\endgroup$ Apr 16, 2017 at 21:46
1
$\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.