# Sum of Two Squares not Congruent to 3 modulo 4

## Theorem

Let $n \in \Z$ such that $n = a^2 + b^2$ where $a, b \in \Z$.

Then $n$ is not congruent modulo $4$ to $3$.

## Proof

Let $n \equiv 3 \pmod 4$.

Aiming for a contradiction, suppose $n$ can be expressed as the sum of two squares:

$n = a^2 + b^2$.

From Square Modulo 4, either $a^2 \equiv 0$ or $a^2 \equiv 1 \pmod 4$.

Similarly for $b^2$.

So $a^2 + b^2 \not \equiv 3 \pmod 4$ whatever $a$ and $b$ are.

Thus $n$ cannot be the sum of two squares.

The result follows by Proof by Contradiction.

$\blacksquare$