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!

Primes in 4n+1/3

  1. Aug 19, 2005 #1
    I have heard a lot of talk about primes in the form of 4n+3 being infinite, but no one can seem to prove that 4n+1 is infinte. Why is this? Also, if someone disproved it, wouldn't that mean that all primes after a certain number had to be in the form of 4n+3
  2. jcsd
  3. Aug 19, 2005 #2
    Nice way to get the homework done!
    If its not, then too bad, it seemed like a good way to get the homework done :(

    Anyways, do you know Dirichlet Theorem? I guess you dont, check this out,

    This certainly shows that there infinitely many primes of the form 4n+1. Now can you show that this is true with elementary number theory?

    -- AI
  4. Aug 19, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    it is easy to prove without appeal to dirichelt's theorem that there are infinitely many primes of the form 4n+3, and the standard proof that there infinitely many primes may be used. the case of 4n+1 is harder but certainly can be proved (without appeal to dirichlet's theorem), it may help to consider the sums of squares and do some research on that.
  5. Aug 19, 2005 #4
    unfortunately for you, tenaliraman, it is not an easy way to get hw done since i haven't gone back to school yet, but thanks for the response
  6. Aug 21, 2005 #5
    I got into that sometime ago on PF on its own thead: Infinitively many primes of the form 3n+1. It can be shown by considering quadratic residues. the thread was started by bOmbOnika, january 25, 2005. Here is my reply:

    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.

    This was kind of clumsy and detailed, and Shmoe (then said,) 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
    Last edited: Aug 21, 2005
  7. Aug 21, 2005 #6


    User Avatar

    Take the primes of the form 4n+3 (n >= 1) and assume there are only finitely many. Put them in a list p1, p2, ..., pk. Consider N = 4*p1*p2*...*pk + 3. Clearly N must have a prime factor of the form 4n+3. But this prime was not in our original list; dividing N by any of the primes in our list leaves a remainder of 3. Thus our original assumption must have been incorrect and there are infinitely many primes of the form 4n+3.

    Take a positive integer N. Let M = (N!)^2 + 1. Consider the smallest prime factor of M, called P. Note P is greater than N. We have M = 0 (mod P), or (N!)^2 = -1 (mod P). Now we raise both sides to the (P-1)/2-th power: (N!)^(P-1) = (-1)^((P-1)/2) (mod P). But by Fermat's Little Theorem, (N!)^(P-1) = 1 (mod P). So (-1)^((P-1)/2) = 1 mod P. Thus (P-1)/2 is even, say (P-1)/2 = 2n. Then P = 4n +1. So given any integer N, we can find a prime P > N of the form 4n+1. There must be infinitely many primes of the form 4n+1.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Primes in 4n+1/3
  1. Primes to 1 (Replies: 3)

  2. Prime = 1 or 3 mod 4 (Replies: 6)