You may also like

problem icon

More Mods

What is the units digit for the number 123^(456) ?

problem icon

Novemberish

a) A four digit number (in base 10) aabb is a perfect square. Discuss ways of systematically finding this number. (b) Prove that 11^{10}-1 is divisible by 100.

problem icon

A Biggy

Find the smallest positive integer N such that N/2 is a perfect cube, N/3 is a perfect fifth power and N/5 is a perfect seventh power.

Multiplication Magic

Stage: 4 Challenge Level: Challenge Level:1
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).