# Infinetely many primes of the form 3n+1

1. Jan 23, 2005

### b0mb0nika

prove that there are infinetely many primes of the form
3n+1

we used :
Assume there is a finitely # of primes of the form 3n+1
let P = product of those primes.. which is also of the form 3A+1 for some A.
Let N = (2p)^2 + 3.
Now we need to show that N has a prime divisor of the form 3n+1, which is not in the list of the ones before. This would be a contradiction. But I'm not sure how to show that.
any help would be appreciated

2. Jan 23, 2005

### ramsey2879

I think your trying to make use of the technique to prove infinitely many primes of the form 4n + 1. I think you need to show that N is of the form 3X+1, none of the factors of which belong to the list. If N is prime or has a factor of the form 3Y+1 then that would be a contradiction. Then show respectively what happens if the factors of N are respectively of one of the forms 3Y or 3Y-1. Unfortunately as I am typing this I can't rule out two prime factors of the form 3Y-1. Anyway, that is my thought on this.

3. Jan 24, 2005

### Gokul43201

Staff Emeritus
Here's a thought :

Assume a finite number of such primes, $q_1, q_2, ..., q_n$

Let $$N = 3(\Pi_i q_i) + 1 = 3A + 1$$

And let its prime factorization be of the form $$N = \Pi_i p_i$$

Clearly no $p_i$ can be of the form 3k.

And since $3k-1 \equiv -1 (mod 3)$ and $3A + 1 \equiv 1 (mod 3)$, there can only be an even number of factors of the form 3k-1.

Also, if there is a factor of the form p = 3k+1, you a contradivtion of your assumption, because p can not be any of the q's (else p|1, which is not true).

So, this leaves the only possibility that N is a product of an even number of primes of the form 3k+2. If you can show this is impossible, you are through. I think this would be doable by comparing this product with the corresponding product obtained from terms 1 less than each of the above terms.

Very likely, there's a nicer way, so just wait around while you're thinking about it, and someone will show up and state the obvious.

4. Jan 25, 2005

### robert Ihnot

bOmbOnika: Assume there is a finitely # of primes of the form 3n+1
let P = product of those primes.. which is also of the form 3A+1 for some A.
Let N = (2p)^2 + 3.

I have an idea that may work. I am going to use the form (2P)^2 +3, granting that the capital P in the second line above is the small p in the third.

The form 3n+1 would represent the product of primes of the form 3k+1, and so we look at (6N+2)^2+3 = Q=36N^2+24N+7 ==7 Mod 12. (which is a reduction since we could have used 24, and in fact since the form is actually 6k+1 for the primes since 2 is the only even prime, we could do better.) But anyway, we use the form Q=12K+7, which is of the form 3X+1, so it can not be prime, or we have a contradiction.

Now all primes but 2 are of the form 4k+1 or 4k+3. Suppose Q has a prime factor q of the form 4k+1. Then we have:

(2P)^2 +3 == 0 Mod q. This gives (2P)^2 ==-3 Mod q, and since -1 is a quadratic reside of q, we have a U such that (U)^2==3 Mod q.

Thus by the law of quadratic reciproicity, we have an X such that X^2 =q Mod 3. But 1 is the only quadratic residue Mod 3, so in this case we are through since we have q==1 Mod 3.

Thus a prime factor q is of the form 4k+3 and of the form 3k+2. Modulo 12 the forms are 12k+1, 12k+5, 12k+7, 12k+11, since 2 or 3 could not divide Q.
But the only form available of both the forms 4k+3 and 3k+2, is 12k+11.

But the products and powers of primes involving -1 Mod 12, are only +-1Mod 12, so they can not equal Q==7 Mod 12.

Well, if that works, it involves understanding that -1 is a quadratic residue for primes of the form 4k+1 and the Law of Quadratic Reciprocity. Thus, maybe, that is why the form (2P)^2+3 was involved.

Last edited: Jan 25, 2005
5. Jan 25, 2005

### shmoe

Suppose you have a prime that divides N=(2P)^2+3, say p. You know that p is not 2 and that it's congruent to 2 mod 3. I assume you're familiar with quadratic reciprocity at this point. Use what you know about the legendre symbol to determine if -3 is a Quadratic Residue mod q.

Next, use the special form of N and the fact that p divides it to come to a contradiction.