# Rules of Divisibility

For those of us who like to play with different number bases it is often helpful to know the rules of divisibility for a given base.

There is a connection between the reciprocal of a prime number and the rule for testing for divisibility by that prime. (The reciprocal of a prime p is 1/p)

• If the prime we are testing is a factor of the base in use then firstly the reciprocal of will terminate and secondly there will be a simple rule for testing divisibility.
For example, 3 is a factor of *10, so if we want to know if 3 will divide a given base twelve number without remainder then we only need to look at the last digit of the number (which will be 0, 3, 6 or 9 if the number is divisible by 3 without remainder).
• If the number we are testing by is not a prime, but its prime factors are factors of the base, then there will be a similar rule - for example 9 is not a factor of *10, but its prime factor 3 is; 9 is a factor of *100 (the second power of *10) so we look at the last two digits of the number to be tested to see if these form a number divisible by 9.
• If the number (n) we are testing is not a factor of 10 or a power of 10 (where "10" is, of course, any base), but is a factor of 10+1 or 10-1, there are two further simple rules:
• if n is 10-1, then sum its digits. For example in base seven, 6 is 10-1 and the number 435 in base seven can be divided exactly by 6 because 4+3+5 = 15 (which is twelve, a multiple of six).
• if n is 10+1 we add the digits in alternate positions and subtract one total from the other. If the answer is 0 then the number can be divided by n without remainder. For example in base ten 297 can be divided by 11 since (2+7) - (9) = 0.

Life gets much more interesting when the divisor is not a factor of the base or its powers nor a factor of 10+1 or 10-1.

For a given prime, in a given base, we can find a rule for divisibility; note that the rule we find might not be simple. George S. Terry, of the DSA, described some such rules (for *15 and *17 in base twelve) to me many years ago, and they were not all that simple. We need rules for any prime and any base; what follows is the beginning of an attempt to establish such rules.

If we divide ten by 7 we have a remainder of 3. We say, in mathematical language, that 10 = 3 mod 7. In the same way *10 = 5 mod 7 and in base six, 10 = 6 mod 7 or 10 = -1 mod 7.

We can replace the powers of the base by these moduli. In base ten the square of ten is a hundred; so 100 = 102 = 32 mod 7 = 2 mod 7. (3 squared is 9, but 9 in turn is 2 mod 7). Using these moduli we can list the powers of ten mod 7 as:

powers of tenresidue mod 7
103
1002
1 0006
10 0004
100 0005
1 000 0001

after which the pattern of residues repeats. You might also note that there is another pattern in the residues if we allow negative residues as well as positive: the residue set 3,2,6,4,5,1 can also be written 3, 2, -1, -3, -2, 1. To tidy this up, since 100 = 1 we can write:

powerminimal residue
01
13
22
3-1
4-3
5-2
61

which shows the pattern quite neatly.

All very well, but what use is this in deciding if a given number can be divided by a given prime in a particular base?

Take as example the number 4956 (base ten); is 7 a factor of this number?

coefficient stands for or mod 7 mod 7 4 4000 4 x 1000 = 4 x 6 3 3 9 900 9 x 100 = 9 x 2 4 -3 5 50 5 x 10= 5 x 3 1 1 6 6 6= 6 x 1 6 -1

Totals were 3 + 4 + 1 + 6 = 20 (base seven) = 0 mod 7 and 3 + (-3) + 1 + (-1) = 0, showing 4956 is divisible by 7 in base ten.

So all we need are these "power residues" to a given base. Express the coefficients of the number given as residues to the base and then sum the products. The result should be 0 if we use positive and negative residues and a simple multiple of the prime if not.

(More to follow.)