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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook