### Code to Zero

Find all 3 digit numbers such that by adding the first digit, the square of the second and the cube of the third you get the original number, for example 1 + 3^2 + 5^3 = 135.

### N000ughty Thoughts

Factorial one hundred (written 100!) has 24 noughts when written in full and that 1000! has 249 noughts? Convince yourself that the above is true. Perhaps your methodology will help you find the number of noughts in 10 000! and 100 000! or even 1 000 000!

### Mod 3

Prove that if a^2+b^2 is a multiple of 3 then both a and b are multiples of 3.

# Divisibility Tests

### Multiples of 2 and 5

The easiest divisibility tests are for $2$ and $5$. A number is divisible by $2$ if its last digit is even, by $5$ if its last digit is $0$ or $5$.

These tests refer to 'digits' in the (usual) base $10$ representation of the number, so that (for example) $2645$ represents the number $(5\times 1)+(4\times 10)+(6\times 100)+(2\times 1000)$. The tests for $2$ and $5$ work because the rest of the number (apart from the last digit) is a multiple of 10, and so is always divisible by $2$ and $5$. If the last digit is a multiple of $2$ (or $5$), then the whole number must be.

### Multiples of 4 and 8

Since $100$, $1000$ and so on are multiples of $4$, it follows (as for $2$) that a number is divisible by $4$ if the number represented by its last two digits is a multiple of $4$.
Example: $3728$ is divisible by $4$ because $28$ is.

Powers of $10$, from $1000$ on, are divisible by $8$, therefore it follows that a number is divisible by $8$ if the number represented by its last three digits is a multiple of $8$.
Example: $3728$ is divisible by $8$ because $728$ is.

Note: if you think that you need a calculator to decide whether (for example) 728 is divisible by 8, then it will help you to learn the 8 times table and to practice some divisions which you can check on your calculator until you are confident that you can divide by 8 and don't need the calculator.

### Multiples of 3 and 9

A slightly more complicated version of such reasoning gives rise to a test for divisibility by $3$.

Now $10$ is $(3\times 3)+1$, so (for example) $50$ is $(15\times 3)+5$. To decide whether 57 is divisible by $3$, we can take out the $15$ lots of $3$ in $57$ and just check whether the remaining $5+7$ is divisibly by $3$: which it is, since $5+7=12$.

Put slightly differently, we reason that $57=($a multiple of $3)+(5+7)$.

Therefore $57$ is a multiple of $3$ if and only if $12$ is.

For $257$, we note that $100$ is $(33\times 3)+1$, so $200=(66\times 3)+2$. We looked at $57$ above.

Therefore $257=($a multiple of $3)+(2+5+7)$.

Once again, $257$ is a multiple of 3 if and only if the sum of its digits is a multiple of $3$.

Actually, that sum is $14$, which is a multiple of $3$ if and only if $1+4$ is.

Since $5$ is not a multiple of $3$, neither is $257$.

In general, $10=9+1$, $100=99+1$, $1000=999+1$ and so on:

every 'power' of $10$ (like $10$, $100$, $1000$, $10000$ and so on) is just $1$ more than a multiple of $3$, and so the method for divisibility can be applied to a number with any number of digits.

Example: is $1997$ divisible by $3$?

Now $1+9+9+7=26$, and $2+6=8$ which is not divisible by $3$.

Therefore $1997$ is not divisible by $3$.

Note: in this example, we added the digits of $1997$, then we added the digits of the answer, and so on, until we arrived at an answer with just one digit, sometimes called the 'digital root' of the original number. So we can say that a number is divisible by $3$ if and only if its digital root is $3$, $6$ or $9$.

Because $10=9+1$, $100=99+1$, $1000=999+1$ and so on, we can see that every power of $10$ is just $1$ more than a multiple of $9$, and so the method for divisibility by $3$ actually transfers to $9$ too: a number is divisible by $9$ if and only if its digital root is $9$.

### Multiples of 6 and 12

A number is divisible by $6$ if and only if it is divisible by both $2$ and $3$.

This is not at all obvious: it is true because $2\times 3=6$ and because 2 and 3 are 'coprime' - i.e. they have no common factor (apart from $1$).

Example: $1638$ is even and its digital root is $9$. Therefore it is a multiple of $6$.

Similarly, a number is divisible by $12$ if and only if it is divisible by both $3$ and $4$ - because $3\times 4=12$, and $3$ and $4$ are coprime.

### Multiples of 11

The test for $11$ is a modified version of that for $3$ and $9$.

Whereas every power of $10$ is $1$ more than a multiple of $3$ (or $9$), an alternating pattern emerges for multiples of $11$. That is to say, $10$ is $1$ less than $11$, $100$ is $1$ more than $9\times 11$, $1000$ is $1$ less than $91\times 11$, $10000$ is $1$ more than $909\times 11$, and so on. If we write $m11$' as shorthand for 'a multiple of $11$', we see that odd powers of $10$ are $m11-1$, and even powers of $10$ are $m11+1$.

Example:

Is $54637$ divisible by $11$?

$54637=7+3\times(m11-1)+6\times(m11+1)+4\times(m11-1)+5\times(m11+1)$,

which equals $m11+(7-3+6-4+5)$ or $m11+11$. Therefore $54637$ must be a multiple of $11$.

This is only slightly more complicated than finding the digital root of a number, because we alternately add and subtract the digits, starting from the right. (We could call the answer the 'alternating digital root').

Example:

What is the remainder when $7^{10}-7$ is divided by $11$?

Solution:

$7^{10}-7=282475242$ whose alternating digital root is $2-4+2-5+7-4+2-8+2 =-6$. Our number is $6$ less than a multiple of $11$, so if we divide it by $11$, the remainder will be $5$.

A number is divisible by $11$ if its alternating digital root is $0$ or $11$ (or any other multiple of $11$).

## INTERLUDE: Remainder arithmetic

What is the final digit of $34\times 57$?

Without doing the full multiplication, we know it must be $8$, because $8$ is the final digit of $4\times 7$.

But how do we know?

Because $34\times 57=(30\times 57)+(4\times 57)=m10+(4\times 50)+(4\times 7) =m10+200+8=m10+8$.

In this example 'final digit' means 'remainder when divided by $10$'. To find the remainder in the product (of $34$ and $57$), we need only find the product of the remainders ($4$ and $7$). This rule works, for essentially the same reason, for remainders when we divide by numbers other than $10$.

Once upon a time, schoolchildren were taught a special case of this, called 'casting out nines'. Suppose, for example, I work out $256\times 77$ by long multiplication, and I get the answer $19612$. The remainders when I divide $256$ and $77$ by $9$ are their digital roots: $4$ and $5$ respectively. The product of $4$ and $5$ is $20$, with digital root (remainder) $2$. My answer $19612$ should also have a digital root of $2$; in fact it has a digital root of $1$, so I must have made a mistake in my long multiplication!

Beware: casting out nines may detect a wrong answer (like that above) but it cannot guarantee a correct one. For example, $19721$ has digital root $2$, but the 'final digit test' (which could be called 'casting out tens') shows that it cannot be the answer to $256\times 77$.

[Attending to remainders is the essence of 'modular arithmetic'. The genius C F Gauss gave the first formal account of this in his 1801 book Disquitiones Arithmeticae, which he published at the age of 24].

### Multiples of 7

A test for divisibility by $7$ (or any number, in principle) can be devised using remainder arithmetic, as follows. The remainder when $10$ is divided by $7$ is $3$, so the remainder when $100$ ($=10\times 10$) is divided by $7$ is $3\times 3=9$ (which is $7+2$, so the actual remainder is $2$).

[Editor's note:

$10 = m7 + 3$ so $10^2 = (m7+3)^2= (m7)^2 + 6\times m7 + 3^2 = m7 + 9$]

Using our shorthand: $10=m7+3$ so $100=m7+9=m7+2$.

Hence $1000=m7+2\times 3=m7+6$, or $m7-1$.

[Editor's note:
$10 = m7 + 3$ and $10^2 = m7 + 2$
so $10^3 = (m7 + 3)(m7 + 2) = m7 + 6$]
$10000=m7-1\times 3=m7-3$, and so on.

Example:
To show that $18956$ is divisible by $7$.

Working from right to left,

$18956=m7+[6+(5\times 3)+(9\times 2)-(8\times 1)-(1\times 3)]=$
$=m7+28=m7+4\times 7$

The number $a b c d e$' is divisible by $7$ if $e+3d+2c-b-3a$ is divisible by $7$.
Not very easy to remember!

[This method, using 'remainder arithmetic', can be adapted to any divisor.

The test for $11$ can be explained by the fact that $10=m11-1$, so $10^n=m11-1$ for odd powers of $n$, and $m11+1$ for even powers of $n$.

A test for $13$ would use the fact that $10=m13-3$, and associate a power of $-3$ with each digit.]

T.R.Mukundan wrote to tell us about another test for divisibility by $7$ he has thought of. See the notes for details.

## Special Tests

With some ingenuity, particular tests can be contrived for some integers, such as:

• 7: "Double the units and subtract from the tens", e.g. $1365\rightarrow 136-(2\times 5)=126\rightarrow 12-(2\times 6)=0$. If the chain ends in $0$ or a multiple of $7$, then the original number is divisible by $7$.
• 11: "Subtract the units from the tens", e.g. $1364\rightarrow 136-4$ etc.
If the chain ends in $0$, then the original number is divisible by $11$.
• 13: "Add the tens to $4$ times the units", e.g. $1365\rightarrow 136+20$ etc.
If the chain ends in a multiple of $13$, then the original number is divisible by $13$.
• 19: "Add the hundreds to $4$ times the rest", e.g. $1311\rightarrow 13+44$ etc.
If the chain ends in a multiple of $19$, then the original number is divisible by $19$.
Challenge:

Can you explain why each of these four tests works?

By a happy 'coincidence', $1001$ is the product of $7$, $11$ and $13$. This fact underlies another test for divisibility by these three prime numbers: see the entry for '1001' in David Wells' fascinating book 'The Penguin Dictionary of Curious and Interesting Numbers'.

## Composite Numbers

Suppose $m$ is composite (i.e. not prime) and $m=a b$ where $a$, $b$ are coprime.

As remarked above (for $6$, $12$), $N$ is divisible by $m$ if $N$ is divisible by both $a$ and $b$. This can be extended to writing $N$ as a product of more than two factors, as in the following:

Example:

Show that $351$ $648$ $792$ is divisible by $396$.

$396=4\times 9\times 11$, and each pair of these factors $4$, $9$, $11$ is coprime.

Applying each of the tests for $4$, $9$ and $11$ shows that $351$ $648$ $792$ is divisible by each of these three factors, and therefore by $396$.

Final Problem: If the digits $5$, $6$, $7$ and $8$ are inserted at random in $3$_$1$_$4$_$0$_$92$ (one in each space), what is the probability that the number created will be a multiple of $396$?