You probably learned this trick in grade school: to see whether a number is divisible by three, add all the digits and check if the sum is divisible by three. The same thing works for nine. Ever wonder why?
Actually, three and nine are just special cases of something very general. What does it mean if q divides n evenly? It means that there is ultimately no remainder in the division. So if r represents the remainder at each step of long division, then I should be able to write
r = 0
for d = digits
r = mod(r * 10 + d, q)
end
If r = 0 at the end of the loop, then the number represented by the given string of digits is evenly divisible by q. Now, it's not too difficult to show that I could rewrite the update of r as
r = mod(r * (10 + k * q) + d, q)
for any integer k. In particular, this means that I could let p = mod(10,q), and write the update formula as
r = mod(r * p + d, q)
The trick with division by three and division by nine works because mod(10,3) = mod(10,9) = 1.
Once you realize how this works, you can think of quick checks for all sorts of divisibility properties. For example, take the number 86834; is it evenly divisible by 11? Yes! I can tell because 10 and -1 are equivalent modulo 11, so that my remainder update looks like
r = mod(-r + d, 11)
I can thus check divisibility by 11 by looking at alternating sums of the digits. So since 8 - 6 + 8 - 3 + 4 = 11 is divisible by 11, so also is 86834. Or if I wanted to know whether a number written in octal (base 8) was divisible by 7, I could add the octal digits and see whether seven divided the sum.
Or I could play around for five minutes to find that the binary representation of any multiple of three matches the regular expression
(0 | 1 (00)* (1|01))*
Hooray! A meaningful regular expression which isn't absolutely trivial to parse! So such toy problems in number theory not only amuse me, but they also actually serve some use as a source of exercises for my students. We'll see whether any of them appreciate the entertainment value as I do.
- Currently drinking: Mint tea