Background

One thing that has been on my mind lately is why a number of simple rules work for determining if some large number is a multiple of some other number. In base 10, I was taught the following divisibility rules:

• 2: Ends with an even digit


• 3: Sum all the digits. If that number is a multiple of 3, so is the whole number


• 4: The last two digits are a multiple of 4


• 5: Last digit is a 5 or 0


• 6: Number is an even multiple of 3


• 8: The last 3 digits are a multiple of 8


• 9: Sum all the digits. If that number is a multiple of 9, so is the whole number


• 10: Last digit is 0

Multiples of 1 are trivial. I also don't know any rule for 7 in base 10, but I noticed some interesting patterns that might apply to some other bases. In base 6, you get these rules:

• 2: Ends with even digit


• 3: Ends with 0 or 3


• 4: Last two digits are a multiple of 4


• 5: Sum all the digits. If that number is a multiple of 5, so is the whole number.


• 6: Last digit is 0

So there are some general rules given some radix R:

1. Multiples of R end in 0


2. Factors of R can use the last digit only for multiples


3. R-1 and its factors can use the "sum the digits" trick


4. You can compose rules from a existing multiples:
   
   
   
   
   1. If A and B have no common multiples, then the rule for AB is the rule for A anded with the rule for B
      
      
      
      
      • For instance, in base 10, 6 uses both rules for 2 and 3 in conjunction because 2 and 3 are its prime factors
      
      
      
      
   
   
   2. If A is a rule that uses the last digit, then Aⁿ can use the last n digits.
   
   
   3. If A has a divisibility rule, then RⁿA can exclude the last n digits and use the rule for A.
   
   
   
   

Given these rules, 12 rules should work for base 10 as a combination of the 3 rule and the 4 rule.

The Question

• Is my reasoning here sound? Are there any formal proofs already done on the subject?


• Are there other reasonable rules that could be used for, say, multiples of 7 in base 10?

Your observations are all correct.

Formal proofs for all of them are known, and not too hard. They start with the expansion
$$
n = a_k R^k + a_{k-1} R^{k-1}+ cdots + a_1 R + a_0
$$
and use the remainder of $R$ and its powers when you divide by the $d$ you are interested in.

One more trick: to test for divisibility by $11$ (in base $10$) look at the alternating sum of the digits. That generalizes.

There is no good test for divisibility by $7$ in base $10$.

Since $7 times 11 times 13 = 1001$ you can test for divisibility by any of these primes by testing the alternating sum of the blocks of three digits instead.

Check out https://en.wikipedia.org/wiki/Divisibility_rule and other links in a search for "divisibility tests".

Maybe these are too obvious to need pointing out, but I will anyway. But note that they're shortcuts with the limitations I mention.

Trick 1

• If $n$ can be broken into two or more parts all divisible by $a$, then $n$ is automatically divisible by $a$.

Example: $6526$ is divisible by $13$, since $65$ and $26$ both are.

(But if $n$ can't be split in this way, the test doesn't rule out diviibility by $a$. )

Trick 2

In base $10$:

• Split $n$ into two parts $A$ and $B$. Any number which isn't divisible by $2$ or $5$, and is a factor of only $A$ or only $B$, can't be a factor of $n$.

Example: $16956$ isn't divisible by $13$, because $169$ is but $56$ isn't.

Neither is it divisible by $7$, since $169$ isn't but $56$ is.

If you really insisted, you could also split it up into $16$ and $956$, and find that it's not divisible by $239$.

(Obviously there are other numbers which don't divide $n$: this trick only checks the ones which happen to be factors of $A$ or $B$.)

It's straightforward to extend Trick 2 by splitting $n$ into more sections and looking for numbers which divide all but one of the sections: for example splitting $142857$ as $14, 28, 57$ shows that it's not divisible by $7$.