1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinetely many primes of the form 3n+1

  1. Jan 23, 2005 #1
    prove that there are infinetely many primes of the form

    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. jcsd
  3. Jan 23, 2005 #2
    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.
  4. Jan 24, 2005 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Here's a thought :

    Assume a finite number of such primes, [itex]q_1, q_2, ..., q_n [/itex]

    Let [tex]N = 3(\Pi_i q_i) + 1 = 3A + 1 [/tex]

    And let its prime factorization be of the form [tex]N = \Pi_i p_i [/tex]

    Clearly no [itex]p_i[/itex] can be of the form 3k.

    And since [itex]3k-1 \equiv -1 (mod 3)[/itex] and [itex]3A + 1 \equiv 1 (mod 3) [/itex], 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.
  5. Jan 25, 2005 #4
    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
  6. Jan 25, 2005 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Infinetely many primes of the form 3n+1
  1. Primes to 1 (Replies: 3)

  2. Primes of form 10^k + 1? (Replies: 21)