Prove the following important results:
(a) If a prime $p$ is the sum of two squares then $p$ is of the form $4n + 1$.
(b) A prime of the form $4n + 3$ cannot be written as a sum of two squares.
(a) In Exercise (1.2).2 we showed that the square of an integer is of the form $4m$ or $4m+1$ for some integer $m$.
This means we have four possibilities for the sum of two squares, where $x$ and $y$ are some integer.
- $p = (4x) + (4y) = 4(x+y)$, which is divisible by 4, and so contradicts $p$ is prime.
- $p = (4x) + (4y + 1) = 4(x+y) + 1$, is of the form $4n+1$
- $p = (4x + 1) + (4y) = 4(x+y) + 1$, is of the form $4n+1$
- $p = (4x + 1) + (4y + 1) = 2(2x +2y + 1)$, which is the divisible by 2, and so contradicts $p$ is prime.
The only cases that don't contradict $p$ is prime, are where $p$ is of the form $4n+1$, for some integer $n$.
(b) Let's take some care parsing the statement to be proven.
$$ \text{prime of form }4n+3 \quad \implies \quad \neg(\text{prime is sum of two squares})$$
This is equivalent to
$$ \text{prime is sum of two squares} \quad \implies \quad \neg(\text{prime of form }4n+3)$$
Our task is to show that if a prime $p$ is the sum of two squares then it cannot be of the form $4n+3$.
We have shown in (a) above that a if a prime $p$ is the sum of two squares, then it must be of the form $4m+1$, for some integer $m$.
Let's assume, for the purpose of contradiction, that $4m+1$ can be written as $4n+3$.
$$ 4m + 1 = 4n + 3$$
$$ 4m = 4n + 2 $$
$$ m = n + \frac{1}{2} $$
If $m$ and $n$ are integers, this is not possible, and so $4m+1$ cannot be written as $4n+3$.
We have shown that a prime that is the sum of two squares cannot be written as $4n+3$. This is equivalent to showing a prime of the form $4n + 3$ cannot be written as a sum of two squares.