Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Prime Proofs

Date: 10/08/2002 at 19:19:23
From: Julie
Subject: If a^(n) - 1 is prime, show that a=2 and that n is prime.

Please help.

   If a^(n) - 1 is prime, show that a=2 and that n is a prime.

   If a^(n) + 1 is a prime, show that a is even and that n is a power 
   of 2.

I'm sure these questions are very similar, but I can't get my mind 
around them.


Date: 10/10/2002 at 20:32:27
From: Doctor Paul
Subject: Re: If a^(n) - 1 is prime, show that a=2 and that n is prime.

>(a) if a^n -1 is prime, show that a=2 and that n is a prime.

a^n - 1 can always be factored as:

   (a - 1) * (a^(n-1) + a^(n-2) + ... + a + 1)

If a^n - 1 is prime, it must be the case that one of the factors above 
is equal to one. Can you argue that the second factor cannot be equal 
to one?  If so, then you know that a - 1 = 1, which implies that 
a = 2.

So to show that n has to be prime, suppose that n is not prime and 
then exhibit a nontrivial factorization of a^n - 1. This nontrivial 
factorization contradicts the supposed primality of a^n - 1 and so 
the conclusion we must make is that our assumption that n is not 
prime must in fact be false. 

There's more here:

   If 2^n-1 is prime, then so is n. - Prime Pages Proofs
   http://www.utm.edu/research/primes/notes/proofs/Theorem2.html 


>(b) if a^n + 1 is prime, show that a is even and that n is a power 
> of 2.

If n is not a power of two, then it has an odd prime factor m.

So we can write n = m*r where we know for sure that m is odd. Since m 
is odd, we can write m = 2*k + 1 for some integer k.

Thus n = 2*k*r + r

Now exhibit a nontrivial factorization of a^n + 1:

a^n + 1 = a^(2*k*r + r) + 1 = 

(a^r + 1) * 

(a^(2*k*r) - a^(2*k*r - r) + a^(2*k*r - 2*r) - ... + a^(2*r) - a^r + 
1)

To see that a has to be even note that if a were odd, then we could 
write:

a = 1 mod 2.

We know that n has to be a power of two, so n is even. So we can write 
n = 2*q for some integer q.

Then

a^n = a^(2*q) = 1^(2*q) = 1 mod 2.

So if a is odd and n is even, a^n will always be odd.

Then a^n + 1 will always be even and hence cannot be prime.

So if a^n + 1 is to be prime, we cannot have a odd.

I hope this helps. Please write back if you'd like to talk about 
this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/