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.

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

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.