Proof involving prime numbers

Printable View

March 5th 2011, 09:09 PM
demode

Proof involving prime numbers

I need to prove that if either of the numbers $2^n-1$ and $2^n+1$ is prime for $n>2$ , then the other one is not.

Attempt: If we name them $a=2^n-1$ and $b=2^n+1$ , we realize that $b=a+2$ . And the the smallet prime for the first number is when n=3, so $a=2^3-1=7$ . For the other number the first prime occurs at n=4 and it's 17.

So, how should I prove this question? If we suppose $2^n-1$ is prime, it will have only the two divisors $\{ 1, 2^n-1 \}$ . Then what does that say about $2^n+1$ ?

(We can't say that the second number is not prime because it is two digits larger than the first one, since many prime numbers are distrubuted at intervals of 2. And there is a chance it can be prime since it will be odd).
March 5th 2011, 10:41 PM
Chris11

Look mod 3.
March 7th 2011, 12:12 AM
demode

Quote:

Originally Posted by Chris11

Look mod 3.

What do you mean "look mod 3"? Please explain.
March 7th 2011, 01:14 AM
chisigma

Quote:

Originally Posted by demode

I need to prove that if either of the numbers $2^n-1$ and $2^n+1$ is prime for $n>2$ , then the other one is not.

Attempt: If we name them $a=2^n-1$ and $b=2^n+1$ , we realize that $b=a+2$ . And the the smallet prime for the first number is when n=3, so $a=2^3-1=7$ . For the other number the first prime occurs at n=4 and it's 17.

So, how should I prove this question? If we suppose $2^n-1$ is prime, it will have only the two divisors $\{ 1, 2^n-1 \}$ . Then what does that say about $2^n+1$ ?

(We can't say that the second number is not prime because it is two digits larger than the first one, since many prime numbers are distrubuted at intervals of 2. And there is a chance it can be prime since it will be odd).

In...

Twin Primes -- from Wolfram MathWorld

... is written that, with the only exception of $(3,5)$ , all the twin primes are of the form $6\ k \pm 1$ . But if $n>2$ the equation $2^{n} = 6\ k$ has no solutions for n and k integer so that...

Kind regards

$\chi$ $\sigma$
March 7th 2011, 02:38 PM
Chris11

Quote:

Originally Posted by demode

What do you mean "look mod 3"? Please explain.

Look at remainders upon division by 3