Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite primes?

  1. Oct 12, 2007 #1
    hello guys . question here
    how can i prove that there exists infinitely many primes p such that p = 3 mod 4.

    i have a little inkling as i know that if a,b=1 mod 4 then ab = 1 mod 4. Im guessing it would be along the lines of euclids theorem?
     
  2. jcsd
  3. Oct 12, 2007 #2
    well, assuming there is a finite number of such 3mod4 prime numbers, you can add them all together, multiply by 4 and add 3... and you get another 3mod4 prime, thus a contradiction
    I only checked like 3 examples but I think that works, only a suggestion, im terrible with proofs
     
  4. Oct 12, 2007 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why can't that number be a small 3 mod 4 prime multiplied by a lot of 1 mod 4 primes?
     
  5. Oct 12, 2007 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is a special case of Dirichlet's theorem. I suppose that this particular instance can probably be proven in an elementary way, though.
     
  6. Oct 12, 2007 #5
    A much tougher question is to prove that there are infinitely many primes congruent to 1 mod 4.
     
  7. Oct 13, 2007 #6
    Hint:

    The product of 2 numbers =1mod4 is a number =1mod4.
    The product of a number =1mod4 and another =3mod4 is =3mod4.
    The product of 2 numbers =3mod4 is =1mod4.
     
  8. Oct 14, 2007 #7
    is this proof correct:

    assume p1 = 3... pn are primes of form pj = 3 mod 4.
    let N = 4p1... pn-1...

    First none of the primes pj divides N since pj | N+1, so if we had pj|N then we get pj|(N+1)-N = 1, which is a contradiction.

    Now alteast 1 of the prime factors of N has form 3 mod 4. Now N is odd, so if such a prime doesnt exist then all prime factors of N have form p = 1 mod 4, which contradicts the whole construction of N.

    Therefore there exists infinitely many primes p such that p = 3 mod 4.
     
  9. Oct 22, 2007 #8
    mathusers: is this proof correct?

    Seems to be.

    werg22: A much tougher question is to prove that there are infinitely many primes congruent to 1 mod 4.

    Yes, because 2 primes of the form 4k+3 multiplied together, result in a number of the form 4m+1.

    However, here's a proof in a nutshell. For the set of p(j)==1 mod 4, we multiply them all together, multiply by 2, and then get (2A)^2+1.

    If a prime of the form q==3 Mod 4 divides this, then we have (2A)^2==-1 Mod q. Thus minus 1 has to be a quadratic residue for q.

    But, if u is a quadratic residue Mod p, then u^((p-1)/2)==1 Mod p. Proof: if X^2 ==u Mod p, then X^(p-1) ==1 ==u^((p-1)/2) Mod p.

    Thus -1 can not be a quadratic residue for a prime q=4k+3, since (-1)^(2k+1) ==-1 Mod q.
     
    Last edited: Oct 23, 2007
  10. Dec 10, 2007 #9
    supose that p_1, p_2, p_3, ..., p_r is a list of all (4n + 3) form primes

    consider the number N = 4*p_1*p_2*p_3*...*p_r - 1 = 4(p_1*p_2*p_3*...*p_r - 1) + 3

    N == 3 mod 4

    write N = q_1, q_2, q_3, ..., q_s [tex]\Rightarrow[/tex] p_i [tex]\neq[/tex] q_j [tex]\forall[/tex] i,j [tex]\in[/tex] {1,2,3,...}


    moreover as dragonfall said:

    The product of 2 numbers =1mod4 is a number =1mod4.
    The product of a number =1mod4 and another =3mod4 is =3mod4.
    The product of 2 numbers =3mod4 is =1mod4.

    the conclusion: at least one of the q_1, q_2, q_3, ..., q_s primes are in (4n+3) form, i.e., our list of (4n+3) primes is not finite
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?