# Infinite primes?

1. Oct 12, 2007

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

2. Oct 12, 2007

### 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, im terrible with proofs

3. Oct 12, 2007

### Hurkyl

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

4. Oct 12, 2007

### Hurkyl

Staff Emeritus
This is a special case of Dirichlet's theorem. I suppose that this particular instance can probably be proven in an elementary way, though.

5. Oct 12, 2007

### Werg22

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

6. Oct 13, 2007

### 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.

7. Oct 14, 2007

### 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 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.

8. Oct 22, 2007

### 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.

Last edited: Oct 23, 2007
9. Dec 10, 2007

### 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