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.
- If A and B have no common multiples, then the rule for AB is the rule for A anded with the rule for B
Given these rules, 12 rules should work for base 10 as a combination of the 3 rule and the 4 rule.
- 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?
No comments:
Post a Comment