(i) Show that if $p \mid (x^2 + 1)$ then
$$ p \equiv 1 \pmod 4 $$
(ii) Prove that there are infinitely many primes of the form $4n + 1$ without using Dirichlet’s Theorem.
(We have already proven this using Dirichlet’s Theorem—see Exercises 2.3, question 1 (a).)
We assume $p$ is an odd prime.
(i) $p \mid (x^2 +1)$ means
$$ x^2 \equiv -1 \pmod p $$
Euler's Criterion tell us that for this congruence to have solutions
$$ (-1)^{\frac{p-1}{2}} \equiv 1 \pmod p $$
There are two cases for $p$, which are $p=4k+1$ and $p=4k+3$, for some integer $k$.
If $p=4k+1$, we have
$$ (-1)^{2k} \equiv 1 \pmod p $$
If $p=4k+3$, we have
$$ (-1)^{2k+1} \equiv 1 \pmod p $$
This is a contradiction, and so $p=3 \pmod 4$ is not possible, leaving only $p \equiv 1 \pmod 4$.
(ii) We take inspiration from Euclid's proof of infinite primes from around 300BC!
For the purpose of contradiction, we assume there are a finite number $n$ of primes of the form $4k+1$ where $k$ in a natural number, $p_1, p_2, \ldots, p_n$.
We next consider the following constructed number
$$ N = (2 \times p_1 \times p_2 \times \ldots \times p_n)^2 + 1 = 4(p_1 \times p_2 \times \ldots \times p_n)^2 + 1 $$
We have two cases for $N$, it is either prime or it is not.
If $N$ is prime, then we have constructed a prime of the form $4k+1$, that is larger than any of the $p_1, p_2, \ldots, p_n$ primes. This is a contradiction of the assumption there are only $n$ primes of the form $4k+1$.
If $N$ is composite, then it has a prime factor, which can denote $p$. That is, $p \mid N$. Since $N$ is of the form $x^2+1$, the result from (i) tells is $p$ is of the form $4k+1$. But this $p$ is not any of the $p_1, p_2, \ldots, p_n$, and so we've found a another prime of the form $4k+1$. This contradicts the assumption there are only $n$ primes of the form $4k+1$.
Both cases contradict the assumption there are a finite number of primes of the form $4k+1$. And so there are an infinite number of primes of the form $4k+1$.