## Sunday, 17 February 2019

### Fun With Numbers - divisibility tests

I got a bit lost on YouTube, via Chinese Remainder Theorem and Modular Functions, I ended up with divisibility tests.

Telling by eye whether a number divides by 2, 3, 4, 5, 6, 8, 9 or 10 is pretty straight forward, non-prime numbers like 12 or 15 are also easy enough, you just usually have to do more than one tests; if it divides by 3 and by 4, then it must divide by 12 and so on.

There is a neat way of checking whether a long number divides by a prime number, short of actually doing long division. I have no idea what practical purpose this serves, it's just a bit of Fun With Numbers.

You just have to remember the "magic numbers" in this table of all prime numbers:

1,-0......11,-1.....21 n/a.....31,-3
3,+1.....13,+4....23,+7..... 33 n/a
7,-2......17,-5.....27 n/a.....37,-11
9,+1.....19,+2....29,+3..... 39 n/a

See caveats/footnotes!

If you can remember the first column, the "magic number" for the prime numbers go up/down by -1 or +1 for numbers ending in 1 or 9, and by +3 or -3 for numbers ending in 3 or 7. So you can reconstruct the whole table just with those two rules. It goes on forever AFAIAA, so the "magic number" for 73 would be +22. There's no such thing as -0 of course, that's just to help you remember the pattern.

What do we do with the "magic number"?

If you have to work out whether a large number divides by a particular prime, you proceed as follows:

1. Multiply the last digit by the "magic number" for that particular prime and add that to the remaining digits (i.e. subtract it if the "magic number" is negative, or add it if both the "magic number" and the last digit are negative).

2. Do the over and over again until either:
a) you get to zero; a number that divides by the prime you are testing for; or a circular calculation where the answer remains constant (pass); or
b) you end up with a number that clearly doesn't divide by the prime you are testing for; or the calculations start flipping between positive and negative numbers without settling down (fail).

Let's test if 169,682 divides by 37:
16,968 - (11 x 2) = 16,946
1,694 - (11 x 6) = 1,628
162 - (11 x 8) = 74
If it's not obvious to you that 74 = 37 x 2, then keep going...
7 - (11 x 4) = -37
-37 clearly divides by 37, that's a pass.
Interestingly, if you keep going...
-3 - (11 x -7) = 74
A nice circular calculation that will flip back and forth forever, or until you notice it's a pass, whichever is sooner.

Let's test if 169,680 divides by 37 (it clearly doesn't):
16,968 - (11 x 0) = 16,968
1,696 - (11 x 8) = 1,608
160 - (11 - 8) = 72
Clearly a fail, but let's keep going...
7 - (11 x 2) = -15
-1 - (11 x -15) = 164
16 - (11 x 4) = -28
-2 - (11 x -8) = 86
At this stage you are flipping from positive to negative numbers without settling down, so we can declare this a fail.
--------------------------------------
Caveats/footnotes

a) 21, 27, 33 and 39 are not prime numbers. The entries would be 21,-2; 27, -8; 33,+10; and 39,+4. But I put n/a because the test does not necessarily work for non-prime numbers. The "magic numbers" for both 13 and 39 are/would be +4, and not all numbers that divide by 13 also divide by 39, obviously.

b) I've completed the table for the easiest to remember/smallest "magic numbers". This is a modular function, so for 7, you can use -2 or +5; for 11 you can use -1 or +10 etc.

Test:
Does 121 divide by 11?
12 - (1 x 1) = 11 (pass)
or
12 + (10 x 1) = 22 (pass).

This is also an example of a circular calculation where the answer is itself, if you overlook that 22 divides by 11, then here's the clue - apply the calculation to 22, you get 22:
2 + (10 x 2) = 22 (pass)