Answer to Question #96784 in Combinatorics | Number Theory for Dina Patel

Question

Prove that there are infinitely many prime numbers of the form 6n + 5.
Hint: any prime number p > 3 has the form p = 6n + 1 or p = 6n + 5 for some integer n. Use this fact
and the fact that the product of two numbers of the form 6n + 1 has the same form. Also, read again
the proof of Proposition 1.22, where we proved that there exist infinitely many prime numbers of the
form 4n + 3.

Answer 1

Suppose that there are finitely many primes of the form 6n+5 namely p₁,⋯,p_n.

Consider p∗=6p₁⋯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

x in x²−x+1≡0 mod p ⟺ p

is of the form 6n+1"

Suppose there are only finitely many 6n+1

primes, namely p₁,⋯,p_n,

Then consider p∗=(p₁⋯p_n)²−(p₁⋯p_n)+1.

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

This is a contradiction