Prove that if $p \nmid r, p \nmid s$, then $p \equiv 1 \pmod{4}$.

Question

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.

Answer 1

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

Answer 2

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.