# Proof that there are infinitely many primes congruent to 3 modulo 4

I'm having difficult proving this.

As a hint the exercise to prove first, that if $a\lneqq \pm 1$ satisfies $a \equiv 3 \pmod4$, then exist $p$ prime, $p \equiv 3 \pmod 4$ such $p\mid4$. But I'm not really getting for what purpose can this be used.

If there are only finitely many primes $\equiv 3 \pmod 4$, take the product of them and denote that product by $a$. Now look at $2a + 1$, and try to deduce a contradiction.

• Yes, this really only requires a manipulation of Euclid's proof. – Newb Feb 10 '14 at 22:06
• Hey, how would you do that? Just started thys type of problems and can't see it :( @Arthur – iggykimi Feb 3 at 18:42
• @iggykimi How familiar are you with Euclid's proof that there are infinitely many primes? – Arthur Feb 3 at 18:44
• I know the one where you take all the primes and add 1, but if that isn't enough for me to understand it is fine @Arthur – iggykimi Feb 3 at 18:45
• @iggykimi That's the one. In this one, we do basically the same thing. We are exploiting the fact that if we multiply together numbers and the result is congruent to $3$ modulo $4$, then at least one of those numbers must be congruent to $3$ modulo $4$. But when we multiply together all our primes to get $a$, we don't know if the result is congruent to $1$ or $3$ (it's odd, so those are the only options). However, $2a+1$ is guaranteed to be congruent to $3$, and it's coprime to all our primes. And one of the prime factors of $2a+1$ must be congruent to $3$. Contradiction. – Arthur Feb 3 at 19:02

Lemma. If $a\equiv 3 \pmod 4$ then there exists a prime $p$ such that $p\mid a$ and $p\equiv 3 \pmod 4$.

Proof. Clearly, all primes dividing $a$ are odd. Suppose all of them would be $\equiv 1 \pmod 4$. Then their product would also be $a\equiv 1\pmod4$, which is a contradiction. $\hspace{3cm}\square$

There exist infinitely many primes $p$ such that $p\equiv 3\pmod 4$.

Suppose that $p_1,\dots,p_n$ would be all such primes. Take $a=4p_1\cdots p_n+3$. (Or you can take $a=4p_1\cdots p_n-1$.) Show that $p_i\nmid a$ for $i=1,\dots,n$. Then use the above lemma to get a contradiction.

Use Euclid's proof showing that there are infinitely many primes, i.e., find an Euclidean polynomial you can use for your arithmetic progression $l \mod k$. Since $l^2\equiv 1 \mod k$ such an Euclidean polynomial exists - see http://www.mast.queensu.ca/~murty/murty-thain2.pdf how to do it (in particular, on page one, the case $4n+3$ is given, see [5]). For $8n+1$ see Infinitely many primes of the form $8n+1$.

Show that there are infinitely many primes that are congruent to 3 mod 4. (Hint: Use that $4\mid(p_1p_2\cdots p_r + 3)$.

Solution: Suppose there are finitely many primes p congruent to 3 mod 4 and denote them by (noting that 3 is one of them) $3, p_1, p_2, p_3,\dotsc, p_r$.

Now consider $A = 4p_1p_2\cdots p_r+5$. If $A$ is prime, then we are done since it is clearly congruent to 3 mod 4 and it is not one of the $p_i$ (as it is greater than all of them). If not, then $A$ has a prime factorization:

$$A = q_1q_2\cdots q_s.$$

Now observe that any prime greater than 3 has to be congruent to 1 or 3 mod 4. This is because, if it were congruent to 0, 2 or 3 mod 4, it would be even, and if it were congruent to 3 mod 4, then it would have to be 3 (only numbers congruent to 3 mod 6 are multiples of 3). Thus each of the $q_i$ has to be congruent to 1 or 3 modulo 4.

However, not all the $q_i$ can be congruent to 1 mod 4. If they were, then their product, which is $A$, could also have to be congruent to 1 mod 4, and this is not possible by construction (note that it would be possible if we had included 3 as one of the factors in the product $4p_1p_2\cdots p_r$).

Thus there exists at least one $q_i$ which is congruent to 3 mod 4. However, this cannot be one of the primes $3, p_1, p_2, p_3,\dotsc,p_r$. If it were, then $q_i$ would divide $A$ (since it is in the prime facorization of $A$) and it would divide $4p_1p_2\cdots p_r$ (since it is one of the primes in that product), and it thus has to divide their difference, which is 3. Thus $q_i$ has to be 3, but that’s a contradiction since 3 does not divide $4p_1p_2\cdots p_r$.

• How is $A = 4p_1p_2\cdots p_r+5$ congruent to $3$ mod $4$? Isn't it congruent to $1$ mod $4$? – Al Jebr Mar 2 '18 at 0:39