Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a proof of there are infinitely many primes of the form $4m+3$, but have trouble understanding it. The proof goes like this: Assume there are finitely many primes, and take $p_k$ to be the largest prime of the form $4m+3$. Let $N_k = 2^2 \cdot 3 \cdot 5 \cdots p_k -1$, where $p_1=2, p_2=3, p_3=5,$... denotes the sequence of all primes. We find that $N_k$ is congruent to $ 3 \pmod {4}$, so it must have a prime factor of the form $4m+3$, and this prime factor is larger than $p_k$—contradiction.

My questions are:

  1. Why is $N_k$ congruent to $3 \pmod{4}$?
  2. Why must $N_k$ have a prime factor of the form $4m+3$ if it's congruent to $3 \pmod{4}$?

It seems that those should be obvious, but I don't see it. Any help would be appreciated!

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

For the first question, if $N_k=2^2\cdot 3\cdot 5\cdots p_k-1$, then $$ N_k-3=2^2\cdot 3\cdot 5\cdots p_k-1-3=4(3\cdot 5\cdots p_k-1) $$ which implies $4|N_k-3$, that is, $N_k\equiv 3\pmod{4}$.

For the second question, suppose instead that $N_k$ has no prime factors of form $4m+3$. Then all its prime factors must be of the form $4m+1$, as they can not be of the form $4m$ or $4m+2$, (except possibly for $2$). But notice $$(4m+1)(4k+1)=16mk+4m+4k+1=4(4mk+m+k)+1$$ so by an inductive argument, you see that a product of primes of the form $4m+1$ again has the form $4m+1$. In terms of congruences, if $p_i\equiv 1\pmod{4}$ and $p_j\equiv 1\pmod{4}$, then $p_ip_j\equiv 1^2\equiv 1\pmod{4}$. This would contradict the fact that $N_k$ has form $4m+3$, since $N_k\equiv 3\pmod{4}$.

share|improve this answer
add comment
  1. $\rm\ N\ =\ 4\ M - 1\ \equiv\: -1\ \equiv\ 3\ \ (mod\ 4)\:,\ \ $ (where $\rm\ M \ =\ 3\cdot 5\:\cdots\:p_{\:k}\:$)

  2. Every prime factor of an odd natural is odd, hence $\rm\equiv \pm 1\ (mod\ 4)\:.\:$ But if every factor is $\rm\equiv 1$ then the number is $\rm\: \equiv\ 1^j\ \equiv\ 1\ \ (mod\ 4)\:.$

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.