guided proof that there are infinitely many primes on the arithmetic progression $4n + 3$

The exercise is to prove this proposition using the following lemmas:

1) Prove Lemma A: every prime ≠ 2 is either of the form $4n + 1$ or $4n + 3$

2) Prove Lemma B: the product of numbers of the form $4n + 1$ is of the form $4n + 1$.

I'll omit the proofs of the lemmas, since I'm not doubtful about their demonstrations. Again I ask if there is any flaw on the following proof.

Proof:

Suppose, by contradiction, that there are finitely many primes of the form $4n + 3$, say, $p_1, p_2, ..., p_k.$ Define $N = 4p_1...p_k - 1 = 4(p_1...p_k - 1) + 3.$ $N$ > $p_k$ and is of the form $4n + 3$, therefore is not prime. So $N$ must be divisible by some prime. Since $N$ is not divisible by any $p_i$ or 2, this prime divisor must be > $p_k$ and consequently, due to lemma A, of the form $4n + 1$. Now, the fundamental theorem of arithmetic states that any non-prime number must be factorable in prime numbers. Since $N$ is not divisible by any $p_i$, there must be primes $f_1, ..., f_l$ on which $N$ is factorable. From the hypothesis and from lemma A follows that these primes must be of the form $4n + 1$ and, by lemma B, so must be $N$, a contradiction.

• Your proof looks good, however you may be interested in the following strategy: Define N as you did, and show that it must be divisible by a prime of the form 4n + 3 or be a prime itself, a contradiction. It is essentially what you have there but in one fewer step. – Legendre Aug 2 '16 at 2:11
• I don't see why it should be divisible by a prime of the form 4n + 3. It surely should be divisible by a prime or be a prime itself, but how can you justify the restriction about the form? – izzorts Aug 2 '16 at 2:15
• A prime number must either be of the form 4n + 3, or 4n+1, because otherwise it is divisible by two. Because you have constructed a number of the form 4n + 3, it is either a prime number itself, or divisible by some other prime numbers. But if these other prime numbers were all of the form 4n+1, this is a contradiction since the product of such numbers must be of the form 4n+1. Thus the number has a prime factor less than it of the form 4n + 3, a contradiction since the finitely many primes listed do not divide it. – Legendre Aug 2 '16 at 2:17

Your proof is good, however consider the following(slightly shorter) version:

Suppose there are finitely many primes of the form $4n + 3$, call them $p_1, p_2, \dots p_k$. Then consider $$N = 4(p_1p_2\dots p_k) - 1$$ This is still of the form $4n + 3$ since it is congruent to $-1 \equiv 3(\mod 4)$. Note also that none of the $p_i$ divide $N$. Thus, $N$ is either prime or composite. If $N$ is prime, we reach a contradiction since it is a new prime of the desired form. Suppose $N$ is composite, then there must be a prime of the form $4n+3$ dividing it by your lemma, also a contradiction since none of the $p_i$ divide $N$.

This proof is nearly identical to yours, however the thing to note is that you can just leave it in the form $4k - 1$ since this is equivalent to $4(k-1) + 3$.

The proof is sound, depending on the course you may be asked (at the very least should be readily able to) justify the statement

"N is not divisible by any $p_i$, or 2.

Otherwise looks good.

• Indeed. By the way, since it was a guided proof, it was to be taken for granted that it was the case (and intuitively it seems true). So I gave it a thought and find that it's not divisible by 2 because it's odd (which is quite immediate), and not divisible by any $p_i$ (which is not that obviously justifiable) because if you divide $N = 4p_1...p_k - 1$ by any $p_i$ you will necessarily come to a rational. – izzorts Aug 2 '16 at 2:25