The problem states:

Let $p$ and $q$ be distinct prime numbers with $p \equiv q \equiv 3\pmod 4$. Prove that if the congruence $x^2 \equiv p \pmod q$ is not solvable, then the congruence $x^2 \equiv q \pmod p$ has exactly two incongruent solutions modulo $p$.

I feel like I'm supposed to do something with the fact that $p \equiv q \equiv 3\pmod 4$ means that $(\frac pq) = (-1)*(\frac qp)$, but I'm not sure how that would help me. In other words, I'm lost.

Update: I worked on it and this is my solution.

If $p \equiv q \equiv 3 \pmod 4$ then $p,q > 2$, but also it implies that $(\frac pq)(\frac qp) = (-1)^{\frac {(p-1)(q-1)}4}=-1$. This means that $(\frac pq)=1$ or $(\frac pq)=-1$ and $(\frac qp)$ is the opposite. So if $(\frac pq)=-1$ then $(\frac qp)=1$, and $x^2 \equiv p \pmod q$ doesn't have a solution and $x^2 \equiv q \pmod p$ has exactly two incongruent solutions modulo p.

  • $\begingroup$ So, one of them is $+1,$ other is $-1$ Now use the definition of mathworld.wolfram.com/LegendreSymbol.html $\endgroup$ – lab bhattacharjee Nov 2 '17 at 5:25
  • $\begingroup$ Dang, well apparently that's all the push I needed to find a solution. Thanks! I'm not sure how things work here, but I'll edit my OP and put in my solution. $\endgroup$ – Any Mous Nov 2 '17 at 18:58

Your Answer

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

Browse other questions tagged or ask your own question.