Prove that $A = \{4n + 3 \mid n \in \mathbb N\}$ contains infinitely many prime numbers

Question

There are multiple answers to this question on this website, but they do not address the question that I have.

To be proved: $A = \{4n + 3 \mid n \in \mathbb N\}$ contains infinitely many prime numbers. Hint: ... Consider the number $N = 4p_1...p_m-1 = 4(p_1...p_m-1)+3$. Argue that $N$ must contain a factor $4q+3$, using the fact that $(4a+1)(4b+1)$ is of the form $(4c+1)$

What does the last part of the hint mean?

Using the fact that (4a+1)(4b+1) is of the form (4c+1)

Why is $(4a+1)(4b+1)$ in the form of $(4c+1)$ and what information does this give to me? The answer on this part that the book gives is as follows:

Since $(4a + 1)(4b + 1)$ has the form $(4c + 1)$, we know that $N/q$ has form $4n + 3$. Also, $N/q$ has a prime factor $q_1$. After a finite number of steps this will yield a prime factor $q_i$ of the form $4n + 3$, with $q_i$ != p$_1, ... , p_k$.

Could anyone explain this in more detail?

Answer 1

We have that

$$(4a+1)(4b+1)=16ab+4a+4b+1=4(4ab+a+b)+1$$

and so, taking $c=4ab+a+b,$ we see that $(4a+1)(4b+1)$ is of the form $4c+1.$

Suppose $N>1$ is an integer such that every prime factor of $N$ is of the form $4a+1$ $(a\in\mathbb{N}).$

Can you see how the above hint shows that $N$ must be a number of the form

$$4\times \text{some positive integer } +1 ?$$

By showing that there is no integer which is both of the form $4c+1$ and $4d+3,$ deduce that $$N=4(p_1\ldots p_m-1)+3$$ must have a prime factor of the form $4a+3,$ call it $q.$

Finally, if $q=p_i$ for some $1\leq i \leq m,$ then it must be a factor of $N-4p_1\ldots p_m = -1,$ absurd!

Answer 2

Note that $(4a+1)(4b+1)=16ab+4(a+b)+1=4c+1$.

Now, to the proof, let $p_1,p_2,\cdots,\ p_m$ are the only primes of the form $4n+3$. Then $N$ as defined above is either a composite number or a prime of the form $4k+1$. In any case, since none of $p_1,\cdots,p_m$ can be a factor of $N$, then, it must have prime factors of the from $p=4q+1$(because any number can be one of the four forms $4q,4q+1,4q+2,4q+3$). Then, using the hint, $N=(4q+1)$ for some $q$; but also, $N=4(p_1\cdots p_m-1)+3$. But if a number is both of the form $4x+1,4y+3$, then, $4(x-y)=2$, which is absurd. This means that $N$ cannot be composite, and hence is a prime of the form $4q+3$.

Answer 3

1) all odd numbers are either of the form $4b+ 3$ or of the form $4b+1$. So all primes other than $2$ or of one of those two forms.

2) the product of any two numbers of form $4a+1$ will be: $(4a+1)(4b+1) =16 ab + 4a + 4b +1= 4 (4ab qa +b) +1$

: also of the form $4c+1$.

3) so if $N = 4k + 3$ we know i) $N$ is odd so ii) all its prime factors are odd and therefore iii) all its prime factors are of the form $4a+1$ or $4a+3$ iv) $N $ is not in form $4a+1$ therefore v) not all of its factors are of form $4a+1$ so vi) some (at least one) of the prime factors are of form $4a+3$

4) let $M=4p_1p_2p_3...p_m -1$. Then $M $ is not divisible by any of the $p_1, p_2,....p_m $.

5) $M= 4p_1p_2p_3...p_m -1=4 (p_1p_2p_3...p_m-1) +3$

is of the form $4k+3$ so it has a prime factor that is in the form $4a+3$.

6) $p_1,...p_m $ are not prime factors of $M $ so there is a prime factor in the form $4a+3$ of $M $ that is not any of the listed $p_1... p_m $.

7) So $p_1,...p_m $ does not list all the prime numbers in the form $4a+3$.

8) As $p_1,....p_m $ could be any finite list of numbers, no finite list of numbers can list all primes of the form $4a+3$ and so the number of primes of the form $4a+3$ is infinite.