Proof with congruence and primes. $(p\mid a^2+b^2)(p\not\mid a,p\not\mid b)\implies \exists c\in\mathbb Z( c^2=-1\pmod {p})$.

114 Views Asked by At

The statement is as follows:

$ p|(a^2+b^2), p\not\mid a, p\not\mid b$ . Prove there exists an integer $c$ such that $c^2\equiv -1 \pmod p$.

What I tried to do is apply definition of congruence to get $a^2\equiv -b^2 \pmod p$ and divide both sides by $b^2$ to get $\frac{b^2}{a^2}\equiv -1 \pmod p $ but I'm stuck here.

1

There are 1 best solutions below

0
On BEST ANSWER

Since $p$ does not divide $b$, there is a $w$ (the inverse of $b$ modulo $p$) such that $bw\equiv 1\pmod{p}$. We know that $a^2+b^2\equiv 0\pmod{p}$. Multiply through by $w^2$. We get $(aw)^2+1\equiv 0\pmod{p}$, so there is an $x$, namely $aw$, such that $x^2\equiv -1\pmod{p}$.

Remark: Note this is not far from what you tried. We just dealt with "division" more formally. Ordinary division by $b^2$ (that is, multiplication by $\frac{1}{b^2}$) will not work. But division modulo $p$, that is, multiplication by the inverse of $b^2$, does work.