Infinitely many primes of the form $6x + 5$ I am working on the following problem:

Prove that there are infinitely many primes in the sequence: $5, 11,17,23, 29, 35, 41...$   Hint: these numbers satisfy $x \equiv 5 \pmod 6$. Try a proof similar to Euclid

My approach:
We notice that the numbers in the sequence are either prime of the form $6x + 5$ or composite of the form $(6x + 5)(6x + 1)$ e.g.
$35 = 5 \cdot 7$
$65 = 5 \cdot 13$
$77 = 11 \cdot 7$
$95 = 5 \cdot 19$
We can see that $(6x + 5)(6x + 1) = (6x)^2 + 6x + 5\cdot6x + 5 = 6(6x^2 + x + 5) + 5 = 6k + 5$ where $k = 6x^2 + x + 5$
So indeed we have closure if we multiply numbers of this form.
We also notice that the product of primes of the form $(6x +5)$ belongs to a different equivalent class depending on if the total of numbers multiplied is odd vs even.
I.e.
Even number:
$(6x + 5)(6x + 5) = (6x)^2 + 6\cdot 5x+ 5\cdot 6x + 25 = 6k + 25 \equiv 1 \pmod 6$
Odd number:
$(6x + 5)(6x + 5)(6x + 5) = (6k + 25)(6x + 5) = (6kx)^2 + 6\cot 5k + 25 \cdot 6x + 5\cdot 25 = 6j + 5\cdot 25\equiv 5\cdot 1= 5 \pmod 6$ where $j = 6kx + 5k + 25x$
Assume that the set of primes of the form $6x + 5$ is finite i.e. $P = {p_1, p_2, p_3, ...p_n}$
Let $N$ be the product of the set of primes: $N = p_1\cdot p_2 \cdot p_3...p_n$
Note we have $2$ cases: Either $N\equiv 5 \pmod 6$ or $N \equiv 1 \pmod 6$ (depending on the size of the set.
Case 1:
Assume that $|P| \equiv 1 \pmod 2 \implies N \equiv 5 \pmod 6$
This means that $N$ is of the form $6x + 5$.
To create a composite number we multiply by $(6m + 1)$ i.e.
$S = N \cdot (6m + 1) = (6x + 5)(6m + 1)$
But this means that $S$ is of the form $6k + 5$
Now a prime $p$ from the $P$ is a factor of $N$ and must also be a factor of $S$. I.e.
$p \mid N \And p \mid S \implies p \mid 6x + 5 - (6k + 5) \Leftrightarrow p \mid 6x - 6k = 6(x - k) \Leftrightarrow p \mid 6q$ where $q = x - k$
But none of the primes is a factor of $6$ since they are of the form $6x + 5$ so we end up with an impossible case.
Similar logic for case 2 also leads to impossibility.
Hence the primes in the sequence must be infinite.
Note:
I am interested to understand the problems in the thought process of my proof.
I found this post that seems to be similar, but so far, the book I am reading has not discussed about "quadratic reciprocity" at this point (also not familiar with it), and I'd like to understand if my proof is valid or what are the problems with it
 A: I admit to struggling to follow your proof OP, and there is a simpler more consise way.
HINT: Let $p_1, p_2,\ldots, p_n$ be the first $n$ primes satisfying $p_i \equiv_6 5$ for each $i=1,\ldots n$.
If $n$ is even, then
$$N \doteq \left(\prod_{i=1}^n p_i\right)+4$$
is odd and satisfies $N \equiv_6 5$ and so there is a prime $p$ satisfying both $p \equiv_6 5$ and $p|N$ [in fact there is precisely an odd number of such $p$]. Can $p$ be any of $p_1,p_2,\ldots,p_n$?
If $n$ is odd then instead let
$$N \doteq \left(\prod_{i=1}^n p_i \right)+6.$$
A: You should imitate Euclid more closely. In your construction of the number $S$, you set
$$S:=N\times(6m+1),$$
for some unspecified $m$. Of course every prime factor of $N$ will also be a prime factor of $S$. In particular, you are not guaranteed to get new primes of the form $6x+5$. You say you arrive at an impossible case, but you simply arrive at $p\mid(x-k)$, which is not impossible at all.
Instead, pick an integer $m$ wisely and set
$$S:=N+m,$$
so that $S$ is guaranteed to have a prime factor of the form $6x+5$ that does not divide $N$. As you have noticed, what is a good choice for $m$ may depend on whether the number of primes in the product $N$ is even or odd.
A: Your case distinction makes a lot of sense. I find that it helps me personally to think about $\mathbb Z_6$ as $\{-2,-1,0,1,2,3\}$ or so. At least to me, this suggests more strongly that getting a factor of $2$ or $3$ into any product will propagate to the end: if any of the prime factors of a composite number is $\equiv\pm2$ or $\equiv\pm3$, then the whole composite number must be congruent to one of $\{-2,0,2,3\}$. If on the other hand a composite number is congruent to $1$ or $-1\equiv 5$, then you know all of its factors (both prime and composite) will be $\equiv 1$ or $\equiv -1$. So looking at only these two kinds of factors you can tell from the remainder of the composite number whether you have an even or an odd number of $-1$ factors, thus the case distinction.
What doesn't make sense is your approach of multiplying to get a composite number. Yes, sure, you get a composite that way, but not one with any new prime factors. Euclid added one to the product of all primes. So you too should focus on adding. Adding one, however, will not align well with your modulo group.
If you have a product that is $N\equiv-1\pmod 6$ then adding $2$  will lead to $N+2\equiv1\pmod 6$ which you know contains an even number of prime factors of the desired kind. Perhaps none. So that's actually the harder case.
If on the other hand you have $N\equiv1\pmod6$ then you might go for example for $N-2$ or $N+4$. For either of these numbers you would need to show that it must contain at least one factor that is $\equiv-1$ and coprime to all the factors in $N$.
Can you also think of a way to use the simpler case to solve the hard case?
A: I can still not find a question in the OP, so here is an answer - assuming the question is "How to prove there are infinitely many primes $\equiv -1$ modulo six along the lines of Euclids proof of the infinity of the set of primes?"

Assume the set $\mathbb P$ of primes $p$ with $p\equiv -1$ modulo six is finite.
Its elements are $5,11,17,\dots$, at any rate $\mathbb P$ is not empty. Let $P$ be

*

*the product of the elements of $\mathbb P$, if $\mathbb P$ has odd cardinality,

*$5$ times the product of the elements of $\mathbb P$, if $\mathbb P$ has even cardinality.

So $P$ is divisible only by prime numbers which are in $\mathbb P$.
The primes $2,3$ do not divide $P$.
By design, $P$ is - taken modulo six - an odd product of minus ones, so it is minus one (modulo six).
Let $q$ be the number:
$$
q=P+6\ .
$$
Then $q$ is bigger than all the numbers in $\mathbb P$, and is minus one when taken modulo six. By assumption it is not a prime. By the unique factorization theorem, we can and do write it as a product of primes. In such a product there are no $2$ and/or $3$ factors. (Since $2,3$ divide the term $6$ in $q=P+6$, but do not divide the term $P$.)  In such a product there is also no $p\in\mathbb P$ factor. (Since $p$ divides the term $P$ in $q=P+6$, but does not divide the term $6$.) But any prime number $\ne 2,3$ is of the shape $6k\pm 1$, so each of the factors in the factorization of $q=P+6$ is congruent to one modulo six. So their product $q=P+6$ is one modulo six. By construction it is minus one modulo six. Contradiction.
Our assumption is false, leading to the wanted conclusion.
