Prove that there are infinitely many primes of the form $6n + 5$

Question

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$?

Answer 1

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.

Answer 2

Note that the only primes not of the form $6n\pm 1$ are $2$ and $3$. A number of the form $6n+5$ is not divisible by $2$ or $3$.

Now note that the product $(6n+1)(6m+1)=36nm+6n+6m+1=6(6mn+m+n)+1$, and you can show by induction that any product of integers of the form $6n+1$ has the same form.

Any number of the form $6n+5=6(n+1)-1$ therefore has at least one prime factor of the form $6r+5$.

If you had a finite number of primes $p_i$ of the form $6r+5$ consider $n=4+\prod p_i^2$

You should be able to prove that this is of the form $6m+5$ and is not divisible by any of the $p_i$ (or by $2$ or $3$), but it is divisible by a prime of the form $6k+5$.

The essential step is showing that you can find a number of the form $6m+5$ which is not divisible by any of the $p_i$.

Answer 3

If we cross out from sequence of positive integers all numbers divisible by $2$ and all numbers divisible by $3$ then all remaining numbers will be in one of two forms:

$S1(n)=6n+5=5,11,17,...$ or $S2(n)=6n+7=7,13,19,....n=0,1,2,3,...$ So all prime numbers also will be in one of these two forms and ratio of number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$. http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13752&lngWId=3