# Prove that if $2^{m+1}+1$ divides $3^{2^m}+1$, then $2^{m+1}+1$ is a prime

Let $m$ be a positive integer. Prove that if $2^{m+1}+1$ divides $3^{2^m}+1$, then $2^{m+1}+1$ is a prime.

Let $N = 2^{m+1}+1$. If $2^{m+1}+1$ divides $3^{2^m}+1$, then $3^{2^m}+1 \equiv 0 \pmod{N}$ and so $\text{ord}_N(3) \mid 2^{m+1}$. Thus $\text{ord}_N(3)$ is a power of $2$. How can we continue from here?

• Yes, it is always a good idea to say where you got the problem from - if it is an exercise somewhere, we might expect a solution within the bounds of knowledge from the book/course. Jul 10, 2017 at 18:15

As you have done, let $N:=2^{m+1}+1$, and as you mentioned $order_N(3) \mid 2^{m+1}$, but notice that $order_N(3)$ must equal to $2^{m+1}$, since othewise we have:

$order_N(3) \mid 2^{\nu}$, where $\nu \leq m$, so must have:

$N \mid 3^{2^\nu}-1 \mid 3^{2^m}-1$, which is a contradiction, so we must have:

$order_N(3) = 2^{m+1} = N-1$.

Since $m$ is positive, then $N$ is greater than $1$; so we have:

$\phi(N) \leq N-1$.

On the other hand we know that $[N-1=]order_N(3) \leq \phi(N)$, so we can conclude that: $N-1= \phi(N)$, which implies the primitivity of $N$.

Let $N=2^{m+1}+1$. We are told $$3^{(N-1)/2}\equiv -1\mod N$$ Thus $\text{ord}_N(3)\mid N-1$ which is a power of two. However $\text{ord}_N(3)\nmid (N-1)/2$ so $\text{ord}_N(3)=N-1$. But what does this say about $N$? A numbers order can be at most $\phi(N)$, so we have $\phi(N)\ge N-1$.

The question is essentially Pépin's Test.