Proving Infinitely Many Primes p=3 mod 4

[mathusers]

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. I am guessing it would be along the lines of euclids theorem?

 

[SpitfireAce]

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, I am terrible with proofs

 

[Hurkyl]

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

Why can't that number be a small 3 mod 4 prime multiplied by a lot of 1 mod 4 primes?

 

[Hurkyl]

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. I am guessing it would be along the lines of euclids theorem?

This is a special case of http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions]Dirichlet's[/PLAIN] theorem. I suppose that this particular instance can probably be proven in an elementary way, though.

 

[Werg22]

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

 

[Dragonfall]

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.

 

[mathusers]

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 doesn't 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.

 

[robert Ihnot]

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.

 

[al-mahed]

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 \Rightarrow p_i \neq q_j \forall i,j \in {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