Solution

Prove that there are infinitely many prime numbers of the form $4k+3$.

---

With the exception of 2, we first note all primes must be of the form $4k+1$ or $4k+3$ where $k$ is an integer, as $2 \mid 4k + 0$ and $2 \mid 4k+2$.

Now, let's consider what happens when we multiply primes (or any numbers for that matter) of these forms together.

For example, the following shows that multiplying two numbers of the form $4k+1$ together yields another number of the same form.

$$\begin{array}{rcl} (4k_1 + 1)(4k_2 + 1) &=& 16k_1 k_2 + 4k_1 + 4k_2 + 1 \\ &=& 4(4k_1 k_2 + k_1 + k_2) + 1 \\ &=& 4k_3 + 1 \quad \textrm{ for some integer } k_3 \end{array}$$

When multiplying two numbers of the form $4k+3$, we again get a number of the form $4k+1$:

$$\begin{array}{rcl} (4k_1 + 3)(4k_2 + 3) &=& 16k_1 k_2 + 12k_1 + 12k_2 + 9 \\ &=& 4(4k_1 k_2 + 3k_1 + 3k_2 + 2) + 1 \\ &=& 4k_3 + 1 \quad \textrm{ for some integer } k_3 \end{array}$$

Multiplying a number of the form $4k+1$ by another of the form $4k+3$, however, results in a number of the form $4k+3$

$$\begin{array}{rcl} (4k_1 + 1)(4k_2 + 3) &=& 16k_1 k_2 + 12k_1 + 4k_2 + 3 \\ &=& 4(4k_1 k_2 + 3k_1 + k_2) + 3 \\ &=& 4k_3 + 3 \quad \textrm{ for some integer } k_3 \end{array}$$

Turning our attention back to the claim to be proven, let us now argue indirectly...

Assume that there are a finite number of primes of the form $4k+3$, namely:

$$p_1, p_2, p_3, \ldots , p_n$$

If $n$ is even, consider the value

$$q = p_1 p_2 p_3 \cdots p_n + 2$$

If $n$ is odd, consider the following instead

$$q = p_1^2 p_2 p_3 \cdots p_n + 2$$

In either case, we have an even number of primes of the form $4k+3$ multiplied together, producing a value of the form $4k+1$. With the additional "$+2$", it must be the case that $q$ is a number of the form $4k+3$.

Consequently, $q$ must have a prime divisor of the form $4k+3$. Consider the alternative, if all of its prime divisors were of the form $4k+1$, then it too would be of that form.

However, this contradicts the fact that $q$ has no prime divisors of this form, as primes of this form are precisely $p_1, p_2, p_3, \ldots, p_n$ and each of these leaves a remainder of $2$ when used to divide $q$.

Since our assumption led to a contradiction, we must reject it.

Hence, there are an infinite number of primes of the form $4k+3$, where $k$ is an integer.