# Math Help - Prime numbers question

1. ## Prime numbers question

My teacher has given my class a challenge task: to prove the following implication:

Let $a$and $n$ be integers such that $n \geq 1$ and $a \geq 2$.

Prove: If $a^n + 1$ is prime, then there exists an integer $m$ such that $n = 2^m$

the following identity was given to us to use:

Let $b$ and $k$ be integers and $k \geq 1$, then
$(b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j$ <------ note, there should be a $k$ on the top of the $\sum$

2. Originally Posted by Nerdfighter
My teacher has given my class a challenge task: to prove the following implication:

Let $a$and $n$ be integers such that $n \geq 1$ and $a \geq 2$.

Prove: If $a^n + 1$ is prime, then there exists an integer $m$ such that $n = 2^m$

the following identity was given to us to use:

Let $b$ and $k$ be integers and $k \geq 1$, then
$(b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j$ <------ note, there should be a $k$ on the top of the $\sum$
Since its a challenge task, I will give you a hint. Enjoy solving it

Two hints:
Step 1) $x^n + 1$ is never prime when n is odd and greater than 1.

Step 2) $x^n + 1$ is never prime when n has an odd factor greater than 1(prove this using Step 1)

3. Originally Posted by Nerdfighter
My teacher has given my class a challenge task: to prove the following implication:

Let $a$and $n$ be integers such that $n \geq 1$ and $a \geq 2$.

Prove: If $a^n + 1$ is prime, then there exists an integer $m$ such that $n = 2^m$

the following identity was given to us to use:

Let $b$ and $k$ be integers and $k \geq 1$, then
$(b^2)^k + b^1 + 1 = (b + 1)(b^2k - b^2k-1 + ... - b + 1) = (b + 1) \sum_{j=0}(-1)^jb^j$ <------ note, there should be a $k$ on the top of the $\sum$
The question is equivalent to: If $n$ is not a power of 2, then $a^n+1$ is not prime.

Let $n=2^mk$ for some odd integer $k>1.$ Then, writing $b=a^{2^m},$ we have
$a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)$
and $1 This shows that $a^n+1$ is composite.

4. Originally Posted by TheAbstractionist
The question is equivalent to: If $n$ is not a power of 2, then $a^n+1$ is not prime.

Let $n=2^mk$ for some odd integer $k>1.$ Then, writing $b=a^{2^m},$ we have
$a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)$
and $1 This shows that $a^n+1$ is composite.
Ooh, I really liked this. Thanks, this is helping to push me in the correct direction.

5. Originally Posted by Nerdfighter
Ooh, I really liked this. Thanks, this is helping to push me in the correct direction.
You’re welcome.

By the way, in the proof that I gave, it is essential that $k$ be odd and greater than 1. Do you know why it fails if $k$ is even or $k=1?$

6. Originally Posted by TheAbstractionist
You’re welcome.

By the way, in the proof that I gave, it is essential that $k$ be odd and greater than 1. Do you know why it fails if $k$ is even or $k=1?$
Is it because $a^n + 1$ would no longer be prime if $k$ was even or equal to 1?

7. Originally Posted by Nerdfighter
Is it because $a^n + 1$ would no longer be prime if $k$ was even or equal to 1?
Correct. But, why?

There are a few details in the proof I glossed over, but it may well be worth checking everything to see that it works (or that I haven’t made any mistake ).

8. Originally Posted by TheAbstractionist
Correct. But, why?

There are a few details in the proof I glossed over, but it may well be worth checking everything to see that it works (or that I haven’t made any mistake ).
Ahhh, the bane of my existence in the number theory class! Every time I come to a conclusion, my teacher will look at what I have written and then turn to me and ask: "why?"

It's at that point that I kind of melt, and respond: "....because?"

9. Let's start by observing that every n>1 which is not a power of 2 can be written as...

$n= (2m+1)\cdot k$ with $m>0$ and $k>0$ (1)

Now we consider the identity...

$(1+a^{k})\cdot (1-a^{k} + a^{2k} -...+ a^{2mk}) = 1+ a^{k} - a^{k} - a^{2k} + ... +a^{2mk} + a^{(2m+1)k} = 1+ a^{(2m+1)k}$ (2)

From (2) and (1) is evident that if $1 + a^{n}$ is prime, n must be a power of 2...

Kind regards

$\chi$ $\sigma$

10. Originally Posted by Nerdfighter
Ahhh, the bane of my existence in the number theory class! Every time I come to a conclusion, my teacher will look at what I have written and then turn to me and ask: "why?"

It's at that point that I kind of melt, and respond: "....because?"
All right. In my proof, I wrote

$a^n+1\ =\ b^k+1\ =\ (b+1)(b^{k-1}-b^{k-2}+b^{k-3}-\cdots-b+1)$

This is for $k$ odd but not for $k$ even. Why? Because if $k$ is even, and you go $b^{k-1}-b^{k-2}+b^{k-3}-b^{k-4}+\cdots$ then your last term is going to be $-1$ not $+1.$ In that case multiplying by $b+1$ will not give $b^k+1$. Only when $k$ is odd does the result stand.

I didn’t mention this because I thought you might want to check everything carefully yourself and make sure that what I wrote made sense.

I also wrote $1 It might look okay, but don’t be fooled. It might still break down if certain conditions are not met – for example, what if $b\le1?$ Luckily the question says $a\ge2$ so $b=a^{2^n}>1$ and we’re safe. Everything has to be carefully checked and every gap must be covered.