<s>[INST] 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?
 [/INST] 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$.
</s>