Question

Adapt the proof in the text that there are infinitely many primes to prove that there are infinitely many primes of the form \(4k + 3\), where k is a non negative integer. (Hint: Suppose that there are only finitely many such primes \({q_1),{q_2),...,{q_n)\), and consider the number \(4{q_1){q_2)...,{q_n) - 1\)).

Short answer

Suppose that there are only finitely many primes of the form \(4k + 3\)where k is a non-negative integer. Say there are only n of them and they are \({q_1),{q_2),...,{q_n)\).

Step-by-step solution

Step 1

Proof:

Suppose that there are only finitely many primes of the form \(4k + 3\)where k is a non-negative integer. Say there are only n of them and they are \({q_1),{q_2),...,{q_n) - 1\). Now consider the number \(N = 4{q_1),{q_2),...,{q_n) - 1\). Notice N is of the form \(4k + 3\)if we let \(4k + 3\).(Observe that \(N = 4{q_1){q_2)...{q_n) - 4 + 4 - 1 = 4(4{q_1){q_2)...{q_n) - 1) + 3 = 4k + 3\)).

Now notice that \({q_i)\bcancel{|)N\)for all \(i = 1,2,...,n\)and since N is odd, \(2\bcancel{|)N\), so N is either a prime or a product of primes of the form \(4j + 1\) (where j is a positive integer) only. However, neither case is possible.

• N can’t be a prime because it’s of the form \(4k + 3\)and it’s greater all the existing primes of that form.
• N can’t a product of primes of the form \(4k + 1\) (where k is a positive integer) only because then N itself is of the form \(4k + 1\). Recall that N is of the form \(4k + 3\).

Since neither case is possible, we’ve arrived a contradiction. That is, our assumption that there are only finitely many primes of the form \(4k + 3\) (where k is a non-negative integer) is false. It must be true that there are infinitely many primes of the form \(4k + 3\) (where k is a non-negative integer).