How do you prove that there are infinitely many primes of the form $5 + 6n$?

Solution 1:

Primes of the form $6n+5$ is particularly easy:

Suppose that there are finitely many primes of the form $6n+5$, namely $p_1,\cdots, p_n$.

Consider $p^*=6p_1\cdots p_n -1$.

Note that any odd prime other than 3, is of the form $6n+1$ or $6n+5$.

Thus, prime divisors of $p^*$ are either of the form $6n+1$ or $6n+5$.

The prime divisors of $p^*$ should have at least one prime divisor of the form $6n+5$.

This is a contradiction.

For primes of the form $6n+1$, use the following:

"Existence of $x$ in $x^2-x+1\equiv 0\textrm{ mod }p$ $\Longleftrightarrow$ $p$ is of the form $6n+1$."

Suppose there are only finitely many $6n+1$ primes, namely $p_1,\cdots, p_n$,

Then consider $p^*=(p_1\cdots p_n)^2-(p_1\cdots p_n) + 1$.

Prime divisor of $p^*$ should be of the form $6n+1$ according to the above equivalence.

This is a contradiction.

Solution 2:

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 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.