# $p\mid a^2+b^2$ Prove that $p\mid a$ and $p\mid b$ [closed]

Let $$p=4k+3$$ be a prime number and $$a,b\in\mathbb{N}$$ so that $$p\mid a^2+b^2$$

Prove that $$p\mid a$$ and $$p\mid b$$

I tried to use Fermat's little theorem, but I don't know what to do next.

• If $a,b\in\bf R$, the division is always possible, whatever $p$! Jul 25, 2018 at 21:47
• If $a,b \in \mathbb R$ which is a field, divisibility is immediate - any non-zero element of a field is a unit. Jul 25, 2018 at 21:47
• Please show us your work using Fermat's little theorem. We can't help you best without knowing whether you used it correctly, or not. So please edit your question to include this lacking context. Jul 25, 2018 at 21:55
• You know Fermat's little theorem. You also know the form of the prime $p$, namely $p=4k+3$, and $p\mid a^2+b^2$. This is where you start. (You should be clear as to why $a$ and $b$ are integers also, viz. previous comments.) Jul 25, 2018 at 22:05

Suppose $a^2 \equiv -b^2 \pmod{p}.$ If $a$ or $b$ is divisible by $p$ then it immediately implies both are divisible by $p.$ So suppose they are not. Then $(\frac{a}{b})^2 \equiv -1 \pmod{p}.$ Which implies $-1$ is a square mod $p.$ However, $(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}.$ Thus, since $p \equiv 3 \pmod{4}$ this is a contradiction. Hence, both are divisible by $p.$
Another solution: Since $p \equiv 3 \pmod{4}, p$ is a Gaussian prime. Hence $p \mid a^2 + b^2$ implies $p \mid a + bi$ or $p \mid a - bi.$ Thus, $p \mid 2a$ which implies $p \mid a.$ Similarly, $p \mid b.$
• I don't understand the part: $(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$ and the contradiction. Jul 26, 2018 at 0:11
• $(\frac{a}{p})$ is the Legendre symbol. Look it up. It turns out $(\frac{a}{p}) = a^{\frac{p-1}{2}}.$ As a result, $p \equiv 1 \pmod{4}$ implies $\frac{p-1}{2}$ is even hence $(\frac{-1}{p}) = 1.$ $p \equiv 3 \pmod{4}$ gives you that $\frac{p-1}{2}$ is odd. Jul 26, 2018 at 1:21