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)
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 ten||residue mod 7|
|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 100 = 1 we can write:
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.)