Like all moderately curious people, I'm sure you've often wondered whether it's possible for
\[
N=a^k-1
\]
to be a prime number, where a and k are positive integers. Well, I'm here to answer that for you!
To avoid trivial cases, we shall assume that k is at least two. Of course, I'm sure we all remember the basic factorization formula:
\[
a^2-1=(a+1)(a-1),
\]
which can only be prime if a=2. A prime number can only be written as a product of two others if one of those numbers is one, you see.
Let's grind out a few cases to see what happens when the exponent is three or four:
\[
3^3-1=26= 2 \times 13
\]
\[
4^3-1=63=3 \times 21
\]
\[
5^3-1=124=4 \times 31
\]
\[
3^4-1=80= 2 \times 40
\]
\[
4^4-1=255=3 \times 85
\]
\[
5^4-1=624= 4 \times 156
\]
Based on this sample you might surmise that
\[
a-1 \phantom{x} \textrm{divides} \phantom{x} a^k-1,
\]
which would imply that it could only be prime if a=2. Your surmise is correct, as can be observed in a number of ways. If you think of the expression defining N as a polynomial, then it is easy to see that 1 is a root. That is, if you set a=1 then we get N=0. With polynomials, every root corresponds to a factor. Indeed, it is easy to verify the factorization formula
\[
a^k-1=(a-1)(a^{k-1}+a^{k-2}+\dots+a+1),
\]
which, again, could only be prime if a=2. (As an aside, if you divide both sides of the above equation by a-1 you get the familiar equation for the sum of a geometric series.)
Having established that N can only be prime when a=2, let us turn our attention to the exponent. Grinding out the first few cases now gives:
\[
2^2-1=3
\]
\[
2^3-1=7
\]
\[
2^4-1=15= 5 \times 3
\]
\[
2^5-1=31
\]
\[
2^6-1=63=9 \times 7
\]
\[
2^7-1=127
\]
\[
2^8-1=255= 5 \times 51
\]
\[
2^9-1=511= 7 \times 73
\]
\[
2^{10}-1=1023= 3 \times 341
\]
This sample might lead you to conclude that we obtain a prime number if and only if the exponent is prime. In this case, alas, you are only half right. It is certainly true that a non-prime exponent will lead to N not being prime. You see, if the exponent is not prime then we have a nontrivial factorization k=xy. But then a small modification to our earlier factorization formula gives us:
\[
2^k-1=2^{xy}-1=(2^x-1)(2^{x(y-1)}+2^{x(y-2)}+\dots+2^x+1),
\]
showing that N is not prime in this case. Sadly, the other direction is not true. Here's a counterexample:
\[
2^{11}-1=2047=23 \times 89
\]
So we have come to the end of our investigation. We can only obtain a prime number if we have:
\[
N=2^p-1,
\]
where the exponent is prime. This is a necessary but not sufficient condition, alas. Primes of this form are referred to as Mersenne primes, after the seventeenth century French theologian and mathematician who first investigated them. It is currently an open question whether there are infinitely many such primes. So get working on that!
Wait, did I just hear you say, “Who cares?” Of course, it reflects poorly on you that you would ask such a question. But if you're curious, Mersenne primes are closely related to perfect numbers. But that's a different post!
- Log in to post comments
I have in fact worked a bit on perfect numbers. I could easily show that they divide a number of the form 2^n(2^(n+1)-1). But I couldn't show they were actually equal to such a number. Don't remember where I got stuck. It's been a while since I've tried that just for the hell of it.
Interesting post! I knew about the form of Mersenne primes, but not why "a" had to be 2 and "k" had to be prime.
Are there any established special properties of the set of primes that lead to Mersenne primes, versus those that don't? That is, what is it about 2/3/5/7/etc that allow them to make Mersenne primes, while 11/etc don't?
As it happens, I was planning to devote the next post in this series to proving that every even perfect number has the form you mention (a power of two times a Mersenne prime). That proof is highly nontrivial and has a lot of steps to it, but it does rely solely on “elementary” techniques. Stay tuned!
Alas, I am not aware of any test that will tell you ahead of time which prime exponents lead to Mersenne primes. That the base is 2 and exponent is prime is a necessary condition, but not a sufficient condition. :(
cheglabratjoe, GIMPS (the great internet Mersenne prime search) works through the list of primes. They've fully checked all exponents up to about 28000000, and some out to about 50000000, using the massive power of tens of thousands of computers across the internet. I get the impression they have done "easy" checks (to eliminate some candidates) out to an exponent of a billion. http://www.mersenne.org/primenet/
Cool, Jon. I'd heard of a distributed computer search for primes, but never looked into it and so didn't realize they were looking for Mersenne primes. Very neat! I used to participate in the gravity wave one, but stopped when the computer I was running it on died (I blamed it on that program, probably unfairly).
Jason, does the fact that (i) we don't know if there are infinitely many Mersenne primes stem directly from (ii) it's not known how to predict a priori which primes give Mersenne primes? I guess what I'm asking, in a poor way, is: if you posit that it's impossible to predict Mersenne primes, does that mean we'll never know whether or not there are a limited number of them? Or does that not logically follow? Could you prove that there are finite Mersenne primes, without having a handle on how/why certain p's give a prime M(p)?
cheglabratjoe --
It's pretty common to have what is known as a nonconstructive proof of existence. That is, you can prove that something exists without gaining insight into how to find one. A good example would be Euclid's proof that there are infinitely many prime numbers. He showed that there are infinitely many primes, but there is nothing in his proof that shows us ow to determine whether a given number is prime.
So I would say the same thing here. It would be possible to have a proof that there are infinitely many Mersenne primes that does not at all tell you which prime exponents actually give rise to them.
Interesting! That makes sense. Thanks for answering all my questions!
I love the Monday Math series. It's cool to see this approach to problems ... it's completely different than what I'm used to (I'm a grad student in chemical engineering), even though I do a ton of what can only be called "math."
Basically, we don't ever, ever give a crap about things being integers, and it seems like that fundamentally changes your outlook. If I was given a problem where I had to deal with integers rather than just general numbers, I can honestly admit that I wouldn't know where to begin ...
I have long since outgrown my inaitil curiosity about GIMPS, which I now think is childish. If you are willing to devote money and computing resource to such childish games, you can always find the next bigger Mersenne prime. But what for? It's so boring it's not even fun.An average computer consumes 200 watts of power. The collective array of computers in the GIMPS network which dedicate 99% of their idle time on GIMPS may exceeds one million of them. Running for 6 months each, it consumes 876 kwh of electricity for each user. At $0.125 per kwh it costed each user $110 in electricity bill for a chance to win the GIMPS prize. And that's not factoring the wear and tear of the computer.Would you like to buy a $110 lottery ticket, for a one-in-a-million chance to win a prize of just $50000? No one in a sane mind would do that.Collectively, these folks who run the GIMPS have collectively wasted 876x10^6 kwh of electricity, an amount of electricity that costs almost half a million tons of coal to generate. Half a million ton fossil fuel burned just for the curiosity of discovering the 43th Mersenne prime? What for?You might argue that these user's machines are running idle and wasting electricity anyway had they not been running GIMPS. But keep in mind:One: a computer which is doing intensive computation do consume more energy than one which is simply idling.Two: The users doesn't need to leave the machine idling. If they have nothing useful to do, simply turn off the computer and save some energy.Three: Even if there is idle time to be wasted. You would prefer let the idle CPU time do something more useful, like do the kind of computation that helps design cancer curing drugs, or things like that nature. It does not make sense to use the idle time for the search of prime numbers.Quantoken