Assume n is odd. Then 3n is odd and 3n+1 is even, so cannot be prime. So n is even, and proof that there are infinitely many primes of the form 6n + 1 is equivalent to the given problem.

Note this table:
(6k-1)(6l-1) = 6Q+1
(6k-1)(6l+1) = 6Q-1
(6k+1)(6l+1) = 6Q+1

where (6k+/-1)and (6l+/-1) are primes, and 6Q+/-1 is their product.

Now assume that the problem required proof of infinitely many primes of the form 6k - 1, then we would be nearly done, since following Math Man's method, we can take the product of all the primes of form (6k-1), on the assumption that they are finite in number, and the result is still 6Q-1. Accordingly, the number 6(6Q-1)-1 is either prime itself, i.e a new and larger prime of that form, or must have an odd number of prime factors of that form; see the table, none of which can be in our finite list. So there are infinitely many primes of the form 6k - 1.

Now  take the product of all the primes of form (6k+1), q, on the assumption that they are finite in number.

Since q is odd, let q=(2n+1), so that q^2 = 4n^2+4n+1.
Add 3: q^2+3 = 4n^2+4n+4 = 4(n^2+n+1).

Note next that (n^2+n+1)(n-1) = n^3-1. Assume that a prime, p, divides n^3-1. If so, Fermat comes to the rescue, and either p divides 3 (true only if p=3), or p=3k+1, but as discussed above, this must mean p=6k+1. But if every prime factor of  n^3-1 is of that form, the same must be true of its own factor (n^2+n+1).

So we can plug that back into what we had before: q^2+3 = 4(n^2+n+1), where every prime factor of n^2+n+1 is either 3 or a prime of form 6k+1. Since we eliminated every known prime of that form by adding 3 to q^2, each such prime factor must be a previously unidentified one.

Hence, there are infinitely many primes of the form 3n + 1.

Edited on July 4, 2015, 6:36 am

Posted by broll on 2015-07-04 06:28:58