Suppose $p$ is an odd prime and $p\mid n$. Also $r^2 + s^2 \equiv 0 \pmod{n}$. Now prove that if $p \nmid r,\quad p \nmid s$, then $p \equiv 1 \pmod{4}$.

My work:

Since $r^2 + s^2 \equiv 0 \pmod{n} \implies r^2 + s^2 \equiv 0 \pmod{p} \implies (r + s)^2 \equiv 2rs \pmod{p}$

If $p \nmid r, p \nmid s \implies p \nmid 2rs$

Now I don't know how to proceed further.

  • $\begingroup$ Then $p\nmid r, p \nmid s$. Then we can say $(r/s)^2 \equiv -1 \pmod p$ so by quadratic reciprocity, the conclusion follows. $\endgroup$ – Sandeep Silwal Dec 3 '15 at 19:24
  • 1
    $\begingroup$ @SandeepSilwal: Where does the statement $(rs^{-1})^2 \equiv -1 \pmod{p}$ come from? $\endgroup$ – user110219 Dec 3 '15 at 20:05
  • $\begingroup$ Details posted in the answer. $\endgroup$ – Sandeep Silwal Dec 3 '15 at 21:08

$p\mid n$ and $r^2+s^2\equiv 0\pmod{n}$ implies $r^2+s^2\equiv 0\pmod{p}$, i.e. $r^2\equiv -s^2\pmod{p}$. Now, $p\nmid s$ implies $s^{-1}\bmod p$ exists, so multiply both sides by $\left(s^{-1}\right)^2\bmod p$ to get $\left(rs^{-1}\right)^2\equiv -1\pmod{p}$.

There are many ways to continue. It's immediate by Quadratic Reciprocity, but here are some other ways:

$1)\ $ For contradiction, assume $p\equiv 3\pmod{4}$. Raise both sides to the $(p-1)/2$'th (which is an odd number) power: $\left(rs^{-1}\right)^{p-1}\equiv (-1)^{(p-1)/2}\equiv -1\pmod{p}$. This contradicts Fermat's Little theorem.

$2)\ $ Notice $\text{ord}_p\left(rs^{-1}\right)=4$. Combine this with Fermat's Little theorem to get $4\mid p-1$ (see below Lemma).

Lemma: If $x^k\equiv 1\pmod{n}$, then $\text{ord}_n(x)\mid k$. Proof: For contradiction, let $k=\text{ord}_n(x)t+r$ with $0<r<\text{ord}_n(x)$. Then $1\equiv x^{k}\equiv \left(x^{\text{ord}_n(x)}\right)^tx^{r}\equiv 1^tx^r\equiv x^r\pmod{p}$, contradiction.


We have $r^2+s^2 \equiv 0 \pmod n$ so $r^2+s^2 = nk$ for some integer $k$. Then $p|n$ so $p|nk$ and hence $p|(r^2+s^2)$. Then since $p\nmid r$ and $p\nmid s$, then there exist a $s^{-1} \pmod p$.

Then multiply through by $(s^{-1})^2$ gives you $(rs^{-1})^2 +1 \equiv 0 \pmod p$ or equivalently, $-1$ is a quadratic residue $\mod p$. This implies that $p \equiv 1 \pmod 4$ by quadratic reciprocity.


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.