A long time ago, Bengt was in school, and his teacher taught him some nifty tricks for checking divisibility.
Checking if something is divisible by 10 is obviously easy, as you only need to look at the last digit. This also applies to 2 and 5, being factors of 10.
Checking if something is divisible by 9 can be done by adding up all the digits in the number, and seeing if that number is divisible by 9. This also applies to 3, being a factor of 9.
Checking if something is divisible by 11 can be done by alternatingly adding and subtracting the digits in the number. If you get 0 or a number which is divisible by 11, the original number is also divisible by 11.
That's all good and well, but there are plenty of numbers left. How do you know if something is divisible by 7, for example? Clearly, Bengt reasons, we need to use another number base. But which one?
- If we have another number base, how will these things generalise? With base b, the first trick should clearly generalise to all factors of b. But can we also check all factors of b-1 and b+1? Or only the prime factors? Or some other restriction?
- If we can check all prime numbers, the rest shouldn't be much of a problem. What's the lowest possible base, if we want to check divisibility by 2, 3, 5 and 7?
- ...and 11?
- ...and 13?
- Is there a quick way to figure it out for the first n prime numbers?
Posts
