Challenge Level

Given any 3 digit number you can use the given digits and name
another number which is divisible by 37 (e.g. given 628 you say
628371 is divisible by 37 because you know that 6+3 = 2+7 = 8+1 =
9). The question asks you to explain the trick. One hint is that
111, 222, 333, ... 999 are all divisible by 37. The so called magic
is simply fixing up a number which is divisible by one or other of
the numbers from this list so that it must be divisible by 37. A
second hint is to use 1000= 999+1 when breaking the number into
blocks of 3 digits

This problem was solved by **Alan Riddell** of
Madras College, Scotland; **Justin Sinz,** age 16,
Skyview HS, Billings, MT, USA; **Joel Tay,** age 13
ACS, Singapore, and **Ling Xiang Ning,** Tao Nan
School, Singapore.

This is Alan Riddell's solution:

Let the number $n$ be written using the six digits $abcdef$ where
$a + d = b + e = c + f = x.$

$$\begin{eqnarray} n &=& 10^5a+ 10^4b + 10^3c + 10^2d + 10e
+ f\\ &=& 99900a + 9990b + 999c + 100(a + d) + 10(b + e) +
(c + f)\\ &=& 999 (100a + 10b + c) + 111x\\ &=&
37[27(100a + 10b + c) + 3x] \end{eqnarray}$$ and so 37 is a factor
of $n$.

Also if $n$ has nine digits $abcdefghi$ where $a + d + g= b + e + h
= c + f + i= x$,

$$\begin{eqnarray} n &=& 10^8a + 10^7b + 10^6c + 10^5d +
10^4e + 10^3f + 10^2g + 10h +i.\\ &=& 99999900a + 9999990b
+ 999999c + 999(100d + 10e + f) + 100(a + d+ g) + 10(b + e + h) +
(c + f + i)\\ &=& 999999 (100a + 10b + c) + 999(100d + 10e
+ f) + 111x\\ &=& 37[27027(100a + 10b + c) + 27(100d + 10e
+ f) + 3x] \end{eqnarray}$$ and so 37 is a factor of $n$.

This process can be applied to 12 digit numbers, to 15 digit
numbers and to any numbers where the number of digits is a multiple
of 3.

Justin Sinz used a slightly different method as follows: Let the
number be represented by $abcdef$ where:

$$abcdef=10^5a + 10^4b + 10^3c + 10^2d + 10e + f.$$

If an integer $p$ gives a remainder of $q$ when divided by $n$, we
say that '$p$ is congruent to $q$ (mod $n$)' which is written $p
\equiv q$ (mod $n$). From this, we can see that if $p$ and $q$
satisfy $p - q \equiv 0$ (mod $n$), then $(p - q)$ is divisible by
$n$. Just for fun, let's write out

$$\begin{eqnarray} 10^5 &\equiv& g (\bmod 37)\\ 10^4
&\equiv& h (\bmod 37)\\ 10^3 &\equiv& i (\bmod
37)\\ 10^2 &\equiv& j (\bmod 37)\\ 10 &\equiv& k
(\bmod 37)\\ 1 &\equiv& l (\bmod 37) \end{eqnarray}$$

where $g,h,i,j,k,l$ are constants to be determined. It is found
that $g=j=26, h=k=10$, and $i=l=1$. Now in the top equation, add
and subtract $g,h,i,j,k,l$ from their corresponding powers of ten;
for example, replace $10^5a$ with $a(10^5 - g + g)$ (with the
exception of $f$). Regroup so that, for example,$a(10^5 - g + g)$
becomes $a(10^5 - g) + ag$, and so on. Now gather together the
terms that look like $a(10^5 - g)$ onto the left side of the right
side of the equation, and terms like $ag$ to the right side of the
right side of the equation to give:

$$abcdef = [a(10^5 - g) + ... + e(10 - k)] + ag + ... fl.$$

The term in the brackets is clearly always divisible by 37;
therefore $abcdef$ is divisible by 37 if $ag + bh + ci + dj + ek
+fl$ is divisible by 37. But $g=j=26, h=k=10,$ and $i=l=1$;
therefore

$$ag + bh + ci + dj + ek +fl = 26(a + d) + 10(b + e) + (c +
f).$$

This is always divisible by 37 if $a + d = b + e = c + f = x$,
because the expression then equals $37x$. Hence the first theorem.

In the second theorem, let the number be $abcdefghi$. One can use
exactly the same technique, noting that $10^8 \equiv 26$ (mod 37),
$10^7 \equiv 10$ (mod 37), and $10^6 \equiv 1$ (mod 37).