# Prove that if $a^{(n-1)/2}\equiv\pm1\pmod{n}$, then $\left(\frac{a}{n}\right)\equiv a^{(n-1)/2}\pmod{n}$

Let $$a,n\ \in \mathbb Z$$ and suppose that $$n>1$$ is odd, $$n\equiv3\pmod{4}$$, and that $$\gcd(a,n)=1$$.

Prove that if $$a^{(n-1)/2}\equiv\pm1\pmod{n}$$, then $$\left(\frac{a}{n}\right)\equiv a^{(n-1)/2}\pmod{n}$$

I have no idea how to prove the desired result. I started by noting that $$a$$ is therefore not a Miller-Rabin Witness by our assumption. Further we know that for $$n=2^kq+1$$, $$k=1$$ since $$n\equiv3\pmod{4}$$. However, putting this all together I just got back to the initial assumption that $$a^{(n-1)/2}\equiv\pm1\pmod{n}$$.

Should I focus more on the other side of the equation (i.e. the Jacobi Symbol)? I was thinking this but I couldn't figure out anything to do with it other than to break it up into: $$\left(\frac{a}{n}\right)=\left(\frac{1}{n}\right)\left(\frac{a}{n}\right)=\left(\frac{-1}{n}\right)\left(\frac{-1}{n}\right)\left(\frac{a}{n}\right)$$ This didn't seem to take me very far either, however, since $$\left(\frac{1}{n}\right)=1$$ and $$\left(\frac{-1}{n}\right)=-1$$. Any help would be appreciated.

• It looks close to Euler's criterion. – rtybase Apr 11 '19 at 20:33
• yeah it's essentially the same thing without $n$ necessarily being a prime number – joseph Apr 11 '19 at 20:35

## 1 Answer

From $$n \equiv 3 \pmod{4}$$, we have $$\exists q\in\mathbb{N}$$ s.t. $$n=4q+3$$.

Now, let's assume $$a^{\frac{n-1}{2}} \equiv \color{blue}{1} \pmod{n}$$ then $$a^{2q+1}\equiv 1\pmod{n} \Rightarrow \left(\color{red}{a^{q+1}}\right)^2\equiv a\pmod{n}$$ which means $$\left(\frac{a}{n}\right)=\color{blue}{1}$$.

Similarly, let's assume $$a^{\frac{n-1}{2}} \equiv \color{blue}{-1} \pmod{n}$$ then $$a^{2q+1}\equiv -1\pmod{n} \Rightarrow \left(\color{red}{a^{q+1}}\right)^2\equiv -a\pmod{n}$$ which means $$\left(\frac{-a}{n}\right)=1$$. But $$1=\left(\frac{-a}{n}\right)=\left(\frac{-1}{n}\right)\cdot\left(\frac{a}{n}\right)$$ and $$\left(\frac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}=(-1)^{2q+1}=-1$$ as a result $$\left(\frac{a}{n}\right)=\color{blue}{-1}$$.

• how did you get $(a^{q+1})^2\equiv a \pmod{n}$? – joseph Apr 12 '19 at 0:34
• did you just multiply both sides by $a$? – joseph Apr 12 '19 at 0:39
• @joseph yes, multiply both sides by $a$. – rtybase Apr 12 '19 at 5:49