Little Joys of Discovery #2: A Theorem for Divisibility Tests

You may be familiar with the very simple divisibility test for nines and threes. If you add up the digits of a number, and the sum is a multiple of 9, then the number itself is a multiple of 9. For example, 1+8=9, so both 18 and 81 are divisible by 9. So, too, are 108, 1080, 10000008 and so on. And if the number is so long that the sum of its digits isn't immediately obviously divisible by 9, well, just add up the sum's digits, and there you go.

This is also true of multiples of 3; if the sum of the digits is divisible by 3, then so is the original number.

When I first learned this, I found it interesting, but kind of mysterious. What was so special about the numbers 9 and 3 that they should have this property, and no other numbers should have it? I spent a fair bit of time puzzling over this, and eventually came up with an even more delightful theorem. Again, as with my previous posting on Mersenne primes, I'm likely to be revealing my ignorance of math here to anyone who's actually educated in the subject, but what I'm really trying to share here is how much fun I had figuring this out for myself.

 Here's the insight I had that made it all come together. Whenever you add 9 to something, that's essentially the same as adding 1 to the tens column and subtracting 1 from the units column. So, in principle, since you're adding and subtracting 1, you're not affecting the total.

So let's start with zero. Add 10, subtract 1, you get 9. Do that again, you get 18. And so on, up to 90, which is where it gets a little bit complicated, because you have some digits ticking over and ticking back with the carrying-the-one thing, but ultimately it all works out to the same thing: You're adding 1 to the tens column (turning 90 into 100) and then subtracting 1 from the units column (turning 100 back into 99). Now, the digits add up to 18 instead of 9. But this whole divisibility test is recursive, and you can add 1 and 8 to get 9 again, and there you go.

What happens if you start with one instead of zero? Well, 1+9=10, and 1+0=1, so the sum of the digits remains 1. Add another 9, you get 19, whose digits add up to 10, whose digits again add up to 1. No matter how many times you add 9 (or add 10 and subtract 1), this property will be preserved. More generally, take any number, add up the digits until you're left with just one digit, and whatever that digit is is the remainder when the original number is divided by 9. (Er, sort of. If the remaining digit is 9, then the remainder is zero, but that's because it's impossible to add up any non-zero digits to get a result of zero.)

That's also why the test works for multiples of 3. Any multiple of 9 is, of course, also a multiple of 3, so it's trivially true that if its digits add up to a multiple of 9, it's also a multiple of 3. And if you add 3 to a multiple of 3, the result is also a multiple of 3, so a remainder of 3 (or 6) when a number is divided by 9 indicates divisibility by 3.

When I figured this out, I realized that it's actually part of a more general theorem that works in any base, not just base 10. I'll state it this way:

In any base n, the sum of the digits of any multiple of a factor of (n-1) 

will itself be divisible by that factor of (n-1).

So, for example, in hexadecimal (base 16), any multiple of 3, 5 or 15 will have digits that add up to a multiple of 3, 5 or 15 respectively. 25 in hexadecimal is 19. 1 + 9 = 10 (or in hexadecimal, A) which is divisible by 5. So there. 

This is, of course, well-known to mathematicians and has been for ages. But golly was it satisfying to figure it out for myself!

Thinking about Mersenne Primes

     It is both a blessing and a curse not to be formally trained in a field like mathematics. The blessing is that every once in a while, I get to enjoy the sublime delight of figuring out something on my own. The curse is that when I go to share these exciting discoveries with others, as I'm about to do in this posting, it's almost certain that I'm putting my grave ignorance of the field on display for everyone who knows anything about the subject to see. Fortunately, I'm quite shameless in my ignorance, and after all, admitting you have a problem is the first step towards a solution.

     Anyway, I was thinking about Mersenne primes a while ago, prime numbers that take the form 2^n-1, where n is a prime number. I remember testing it out: 2^3-1 is 7, which is prime. 2^5-1=31, also prime. 2^7-1=127, ALSO prime. Hmmm. Now, I remember reading that not all numbers of this form will be prime, and as it turns out, 2^11-1=2047, which is divisible by 23 and 89, but it is certain that if 2^n-1 is prime, then n must also be prime.

    That's the part that puzzled me. What was so special about 2, and what is it about prime numbers that gave rise to other prime numbers this way? However, I did figure it out, and it's that proof that I want to share with you here.

     Forget about powers of 2 for the time being, and consider a number like 13,131,313. Is it prime? Actually, you can tell that it's not, because its digits show a repeated pattern: 13 repeated four times. So it ought to be divisible by 13, and sure enough, you get 1,010,101 when you divide by 13.
     The same principle can be generalized to any number that consists of a repeating pattern of digits. Simply take the pattern once, and the full number must be divisible by it. So 123456712345671234567 is necessarily divisible by 1234567 (you get 100000010000001).

     Now, take a number that is made up of nothing but repeated 1s. Obviously, that means it's divisible by 1, but all numbers are, so let's ignore that pattern, and look for longer ones. If the number of digits is even, then the number's pattern can be described as a repeated "11", and thus the number itself must be divisible by 11. If the number of digits is a multiple of 3, then it can be described as a repeated "111". And so on. So we can see, for example, that 111,111,111,111 must be be divisible by 11; 111; 1111; and 111,111. (Of those, only 11 is actually a prime factor; you can see that for both 1111 and 111,111 must also be divisible by 11. 111 is divisible by 3, but that's due to a different divisibility test; its digits add up to a multiple of 3.)
   
     So let's get back to the Mersenne primes, the ones that are expressible as 2^n-1. The thing to notice about the formula 2^n-1 is that if you write out the number in binary, you get a sequence of nothing but 1s. 2^n will give you a 1 followed by n zeros, so subtracting 1 you just get a sequence of n 1s.
    And so, if n is an even number, 2^n-1 will be divisible by 11 in binary, which is 3. If n is divisible by 3, then 2^n-1 will be divisible by 111 in binary, which is 7. n=6 give us 63, which is divisible by both 3 and 7.
    Tada! That's it. I can't tell you how pleased I was when this hit me. It was one of those aha! moments that make life good. But it also led me to some other interesting questions that I'm still thinking about today.

    In particular, I'm thinking about how it applies in other bases besides 2. Now, 10^n-1 just gives you a series of n 9s in a row, which is obviously divisible by 9, so we need to tweak the formula a little to cancel that out and give us a series of n 1s instead of 9s. Easy enough. I'm interested in number of the form (a^n-1)/(a-1). Obviously they must be composite when n is a composite number, but how many are primes when n is prime?

    So, in atonement for depriving you of the opportunity to figure out that Mersenne prime thing on your own, I leave you with that question. And if you're a mathematician for whom this is already all well known, I hope you at least enjoy the opportunity to tell me something new in the comments section.