Posted by 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!
April 26, 2011
April 26, 2011
April 26, 2011
April 26, 2011
