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.
No comments:
Post a Comment