Divisibility Tests in Various Bases 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:


*

*Multiples of R end in 0

*Factors of R can use the last digit only for multiples

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

*You can compose rules from a existing multiples:


*

*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


*If A is a rule that uses the last digit, then An can use the last n digits.

*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?

 A: 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".
A: 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$.
