Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
