Physics Forums

## infinetely many primes of the form 3n+1

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

PhysOrg.com  science news on PhysOrg.com  >> Front-row seats to climate change>> Attacking MRSA with metals from antibacterial clays>> New formula invented for microscope viewing, substitutes for federally controlled drug

Blog Entries: 2

Quote by 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
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.

Recognitions:      Gold Member        Science  Advisor     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.

Recognitions:
Gold Member

## infinetely many primes of the form 3n+1

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.

Recognitions:      Homework  Help     Science  Advisor  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.

Thread Tools

|                                                              |                               |         |
|--------------------------------------------------------------|-------------------------------|---------|
| Similar Threads for: infinetely many primes of the form 3n+1 |                               |         |
| Thread                                                       | Forum                         | Replies |
|                                                              | Calculus & Beyond Homework    | 1       |
|                                                              | Linear & Abstract Algebra     | 11      |
|                                                              | Introductory Physics Homework | 14      |
|                                                              | Introductory Physics Homework | 10      |
|                                                              | Introductory Physics Homework | 1       |
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9582432508468628, "perplexity_flag": "middle"}