Answer to Question #96992 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.

Answer 1

Using mod 6, we can conclude that a prime number p has one of the following two forms: 6n+1 or 6n+5.

It cannot have 6n+2 since this is 0 mod 2, neither 6n+3 since this is 0 mod 3, nor 6n+4 since this is 0 mod 2.

Let two integers p=6n+1 and q=6m+1. Then p*q=(6n+1)(6m+1)=36nm +6n+6m+1 =6(6nm+n+m)+1 =6r+1, where r=6nm+n+m+1 since Z is closed under addition and multiplication. Thus, the product of 2 numbers with form 6n+1 will have the same form.

Let's assume for contradiction the no. of prime numbers with form 6n+5 is finite. This means it is upper bound (there is a prime number of this form which is the biggest).

The first no. of this sequence is 5 since 5=6*0+5.

The rest of the sequence is as below:

5< p₁ <....< p_n=6n+5.

We built the following number 6*p₁*....*p_n -1 = 6(p₁*....*p_n -1) +5 which is practically of the form 6K+5.

It has a prime divisor either of the form 6n+1 or 6n+5, since those are the only two forms for a prime number (see above).

If we assume that all its prime divisors have the form 6k+1, then the whole number would have that form, using the above observation about the product of two numbers of that form. However this is not possible since we saw it has the form 6K+5.

This means it must have at least one prime divisor of the same form as it. Let that divisor be p.

Since the sequence above contains all those numbers, it means that p is a member of the sequence.

This means that p divides the product p₁*....*p_n and, by consequence p also divides 6 times that product.

But p also divides 6*p₁*....*p_n -1

Then p divides the difference between 6*p₁*....*p_n and 6*p₁*....*p_n -1 , which is 1.

But p/1 means that p=1 only. Or this is false as per assumption, since p must be at least 5.

This means the initial assumption is false and there are infinite prime numbers of the form 6n+5, as required.