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!

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?