(a) Prove there are infinitely many primes of the form $4n + 1$.
(b) Provide another proof that there are infinitely many primes of the form $4n + 3$.
(c) Let $p$ prime such that $p > 3$. Prove that $p$ is of the form $6n + 1$ or $6n + 5$.
Part (c) means that every prime > 3 can be written as $6n + 1$ or $6n + 5$.
(a) We use Dirichlet’s Theorem (2.17):
Let $a$ and $b$ be relatively prime positive integers, then the arithmetic progression
$$a, \; a + b, \; a + 2b, \; a + 3b, \; \ldots$$
contains infinitely many primes.
Numbers of the form $4n +1$ are an arithmetic progression, $1, 1+4, 1+2(4), 1 + 3(4), \ldots$.
Dirichlet's Theorem with $a=1$ and $b=4$, and noting that 4 and 1 are coprime, tells us the sequence contains infinitely many primes.
(b) Dirichlet's Theorem, taking $a=3$ and $b=4$, noting 3 and 4 are coprime, tells us the sequence of numbers of the form $4n+3$ contain infinitely many primes.
(c) We use the Division Algorithm
For $a$ and $b ≥ 1$, there exist $q$ and $r$ such that $a = bq + r$ where $0 ≤ r < b$
So for a prime $p$ such that $p>3$, there exist $n$ and $0 \le r < 6$ such that
$$ p = 6n+ r $$
Let's consider each case of $r$.
- $r=0$ means $p=6n$ which is divisible by 6, and so $p$ is not prime. Therefore $r \ne 0$.
- $r=2$ means $p=6n+2 = 2(3n+1)$ which is divisible by 2, and contradicts $p$ is prime. Therefore $r \ne 2$
- $r=3$ means $p=6n+3 = 3(2n+1)$ which is divisible by 3, and contradicts $p$ is prime and greater than 3. Therefore $r \ne 3$
- $r=4$ means $p=6n+4 = 2(3n+2)$ which is divisible by 2, and contradicts $p$ is prime. Therefore $r \ne 4$
This leaves $r=1$ and $r=5$, corresponding to $p=6n+1$ and $p=6n+5$.