Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime.

Question

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime.

$(\mathbb{Z} / m \mathbb{Z})^{\ast} =$ unit group modulo $m.$

Suppose that $3^{(m-1)/2} \equiv -1\pmod m.$ Then $(3^{(m-1)/2})^2 \equiv 3^{m-1}\equiv (-1)^2 \equiv 1 \pmod m.$ Suppose that the order of $3 \in (\mathbb{Z} / m \mathbb{Z})^{\ast}$ is $k.$ Then $3^{m-1} \equiv 1\pmod m \Longrightarrow k \mid m-1$ and $3^{(m-1)/2} \equiv -1\pmod m \Longrightarrow k$ is not a proper divisor $\Longrightarrow k = m-1.$ Thus $|(\mathbb{Z} / m \mathbb{Z})^{\ast}| \geqslant m-1 \Longrightarrow m$ is prime.

Answer 1

Bill Dubuque provides a hint for one part. Here is the other:

Hint: If $\,m=4^n+1\,$ is prime with $n\ge 1$, by Euler's criterion and Quadratic Reciprocity:

$$\,3^{\frac{m-1}{2}}\equiv \left(\frac{3}{m}\right)\equiv \left(\frac{m}{3}\right)\equiv -1\pmod{m}$$

Note $\,4^n+1\equiv 1^n+1\equiv 2\ \pmod{\!3}$

Bill's mentioned Lucas primality test can be used as follows:

Theorem: if $\, a^{n-1}\equiv 1\,\,$ mod $n\,$ and $\ p\mid n-1\,\,\Rightarrow\,\, a^{(n-1)/p}\not\equiv 1\,\,$ mod $n$,

then $\,n\,$ is prime (if $n\ge 2$). Equivalently: $\,\text{ord}_n a=n-1\,\,\Rightarrow\,\, n$ is prime (if $n\ge 2$).

Note in above facts the $a$ could be any integer. Existence of such $a$ proves $n$ is prime.

Note $\,m\ge 2\,$.$\,$ Also $\,\,3^{(m-1)/2}\equiv -1\,\,\stackrel{2}\Rightarrow\,\, \underline{3^{m-1}\equiv 1}\,\,\,$ mod $m$

and $\, m-1=2^{2n}$,$\,$ so $\,p\mid m-1\,\Rightarrow\, p=\color{#0ab}{2}\,$ and $\,3^{(m-1)/\color{#0ab}{2}}\equiv -1\not\equiv 1\,\,$ mod $m$.

Answer 2

Use the Lucas primality test, a simple converse of Fermat's little Theorem: $\,m>1\,$ is prime if $\,{\rm mod}\ m\!:\ a^{m-1}\equiv 1,\,$ $\, a^{(m-1)/p}\not\equiv 1$ for all primes $\,p\mid {m-1}\,$ (i.e. some $\,a\,$ has order $\,m\!-\!1).$