# Relevance of prime being divisble by $4k+1$ in proof that 'There are infinitely many primes of the shape $4k+3$'

Show that there are infinitely many primes of the shape $4k+3$

Proof:

$1)$ Suppose that there are only finitely many such primes, say $p_1,...p_n$.

$2)$ Consider the integer $Q=4p_1...p_n-1$

$3)$ The integer $Q$ is odd and of the shape $4k+3$ so cannot be divisible exclusively by primes of the shape $4k+1$

$4)$ Moreover, none of the primes $p_1,...,p_n$ divide $Q$

$5)$ Thus $Q$ is divisible by a new prime of the shape $4k+3$ not amongst $p_1,...,p_n$

$6)$ Contradicting our hypothesis, therefore there are infinitely many primes of the form

Contention:

Why do we have step $3)$ in the proof? Surely all we need to show is that none of the primes $p_1,...,p_n$ divide this new prime.

Even if the proof is complete without this step $3)$, why is it even there?

What relevance is it that it cannot be divisible by primes of the shape $4k+1$?

• $Q$ can be - and generally is - divisible by some primes of the form $4k+1$. The point is that it is impossible that all prime divisors of $Q$ have the form $4k+1$. – Daniel Fischer May 13 '15 at 13:17
• The point is that we want to find some prime of the form $4k + 3$ not $p_1, p_2, ..., p_n$. To do this, we show that $Q$ is divisible by at least one prime of the form $4k + 3$ and that none of $p_i$s divide $Q$. Step $(3)$ provides a proof of the fact that $Q$ is divisible by at least one prime of the form $4k + 3$, since the only odd primes are either of the form $4k + 1$ or of the form $4k+3$. – Balarka Sen May 13 '15 at 13:20

Since you are looking for a new prime of form $4k+3$, you need to make sure that you have a candidate amongst the factors. If all the factors were of the form $4k+1$ you would have some larger primes than you had before, but they wouldn't be of the right form, and the proof would fail.
Fortunately it is east to show that the product of numbers of the form $4k+1$ has the same form, so we see that we must be able to find a new prime of form $4k+3$.
To see why this is important, try it the other way around - if we added $1$ rather than subtracting $1$ in order to try to find an infinite number of primes of form $4k+1$, we'd run into a problem. For example $3\times 7=21$ and $21$ has the form $4k+1$ - but it doesn't have a prime factor of that form, so we can't assume one exists in general.
We need step 3 in order to conclude that $Q$ is divisible by at least one prime of the form $4k+3$ (prime divisors of the form $4k+1$ can appear, but the important thing is that at least one prime of the other form appear).