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 = 10² = 3² 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 ten	residue mod 7
  10	3
  100	2
  1 000	6
  10 000	4
  100 000	5
  1 000 000	1

  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 10⁰ = 1 we can write:

  power	minimal residue
  0	1
  1	3
  2	2
  3	-1
  4	-3
  5	-2
  6	1

  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
  		total		0	0

  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.)