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 An can use the last n digits.
3. If A has a divisibility rule, then RnA 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?
• Interesting subject but I don't think it's accurate to call these "mnemonics" (aids to remembering sonerhing). Really they're convenient shortcuts to calculating something. "Divisibility tests" might be better. (I did open the question expecting mathematical memory aids.) – timtfj Dec 5 '18 at 23:35
• Good call. Renamed and retagged. – Beefster Dec 6 '18 at 17:04

2 Answers

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

• This test may tell you when something is divisible but not reliably when it's not. For example, it doesn't help when you want to test $666$ for divisibility by $7$. – Ethan Bolker Dec 6 '18 at 0:50
• Agreed. I'll clarify that in the answer. – timtfj Dec 6 '18 at 0:53
• @EthanBolker I hope my answer spells out the limitations now! – timtfj Dec 6 '18 at 1:32