If $k|3^{(k-1)/2}+1$, then $ord_{k}(3)=k-1$, because $k-1=2^{n}$. If $ord_{a}b=a-1$, a is prime.

HERE MY SOLUTION(I don't read Rust's solution) If $2^{2^{n}}+1$ prime then $p=-1 mod 3$ therefor $(3|p)(p|3)=1$ Hence $3^{\frac{p-1}{2}}+1=0 mod p$ If $3^{\frac{k-1}{2}}+1 =0 mod k$ then k is prime . Use lemma : If $(x,y)=1$ then $x^{2^{n}}+y^{2^{n}}$ has only prime factor form $2^{n+1}m+1 : lol:$HAHAHAHA Cuopbientcd.

Solution with Aahan Catterjee, Aditya Khurmi, Anshul, Anushka Aggarwal, Derek Liu, Grant Yu, Max Lu, William Wang, Eric Shen, Paul Hamrick, and others: First, suppose $k$ is prime. We know $k \equiv 1 \pmod 4$, and $k \equiv 2 \pmod 3$. Then \begin{align*} 3^{\frac{k-1}{2}} &= \left( \frac 3k \right) \pmod k \\ \left( \frac k3 \right) &= \left( \frac 3k \right) \qquad \text{by quadratic reciprocity} \\ \left( \frac{k}{3} \right) &= \left( \frac{2}{3} \right) = -1. \end{align*}So this completes one direction. Conversely, assume \begin{align*} 3^{\frac{k-1}{2}} &\equiv -1 \pmod k \\ 3^{k-1} &\equiv 1 \pmod k \end{align*}The order of $3 \pmod k$ should divide $k-1 = 2^{2^n}$, but it shouldn't divide $\frac{1}{2}(k-1) = 2^{2^n-1}$. So the order is $k-1=2^{2^n}$ exactly. In particular, by Euler's little theorem, we get $k-1 = 2^{2^n} \mid \varphi(k)$ and in particular $\varphi(k) \ge k-1$. Obviously this can only occur when $k$ is prime.

v_Enhance wrote: First, suppose $k$ is prime. We know $k \equiv 1 \pmod 4$, and $k \equiv 2 \pmod 3$. Then \begin{align*} 3^{\frac{k-1}{2}} &= \left( \frac 3k \right) \pmod k \\ \left( \frac k3 \right) &= \left( \frac 3k \right) \qquad \text{by quadratic reciprocity} \\ \left( \frac{k}{3} \right) &= \left( \frac{2}{3} \right) = -1. \end{align*}So this completes one direction. Can you give me concepts or a explain for this?

Read the article https://en.wikipedia.org/wiki/Legendre_symbol Everything you need is in the first and third section.

Solved with fukano_2, E_6. If $k\mid 3^{\frac{k-1}2}$, then \[-1\equiv 3^{\frac{k-1}2}\equiv 3^{\frac{2^{2^n}}2}\equiv 3^{2^{2^n-1}}\pmod k\implies 3^{2^{2^n}}\equiv 1\pmod k. \]From this we have that the order of $3$ mod $k$ is just $2^{2^n}=k-1$, so $k$ must be prime. Now suppose that $k$ is prime. Note that $k\equiv 2^{2^n}+1\equiv 1\pmod 4$ and $k\equiv 2^{2^n}+1\equiv (-1)^{2^n}+1\equiv 2\pmod 3$, so \[3^{\frac{k-1}2}\equiv \left(\frac3k\right)=(-1)^{\frac{(3-1)(k-1)}4}\left(\frac k3\right)=\left(\frac k3\right)=\left(\frac 23\right)=-1\pmod k,\]as needed.

Start with if.We have that $k$ is congruent to $1$ mod $4$,but $2$ mod $3$.Thus,by quadratic reciprocity,$3$ is a non-quadratic residue mod $p$,which proves the if part by Euler's criterion. Now,the only if part.We have that $3^{2^{2^n}}$ is $1$ mod $k$.This gives that order of $3$ mod $k$ is ${2^{2^n}}$.Thus,$k-1 | \varphi(k)$,which is sufficient to give $k$ prime.

For one direction, suppose that $k \mid 3^{(k-1)/2} + 1$. Then $3^{k-1} \equiv 1 \pmod k$ is the precise order by definition of $k$, so $k-1 \mid \phi(k) \leq k-1$, and $k$ must be prime. On the other hand, if $k$ is prime, Euler's criterion suffices as $\left(\frac 3k\right) = \left(\frac k3\right) = \left(\frac 23\right) = -1$.