I know this is a duplicate but I had no idea what the other solution meant or how to go about approaching this problem. At first glance I thought about using Euclid's theorem that there are infinitely many primes and just doing proof by contradiction but I'm so confused right now. I'm horrible at math and I just want to understand how to approach this problem.
I've tried proof by contradiction: Assume that there are only a finite number of primes in the form of $6n+5$. But I'm just completely lost on what to do after this.
The original question: How do you prove that there are infinitely many primes of the form $5 + 6n$?
Best Answer
First note that a prime of the form $6k+5$ is also of the form $6k-1$
Assume , there are only a finite many prime numbers of the form $6k-1$ and multiply them all together. The product must have residue $1$ or $5$ modulo $6$. If the residue is $1$, then subtract $2$. If the residue is $5$, then subtract $6$.
The resulting number is then greater than $1$ and of the form $6k+5$
It is easy to see that the resulting number cannot be divisible by $2$ or $3$, hence it must have prime factors of the form $6k\pm1$. If all prime factors were of the form $6k+1$, the number would be congruent to $1$ modulo $6$, which is not the case.
Hence, there must be a prime of the form $6k+5$ dividing the number, but because of the subtraction of $2$ or $6$ it cannot be one of the primes in the product. This gives you the desired contradiction.