How can I show that there are infinitely many prime numbers such that $p \equiv 3 \pmod4$?

There's a hint that I'm not sure how to use, they say that lets assume that $p_1,\ldots,p_r$ are ALL the prime numbers that $ p \equiv 3 \pmod4$, look at the number:

$M = p_1p_2\cdots p_r +2$ if $r$ is even


$M = (p_1)^2p_2\cdots p_r +2$ if $r$ is odd

Prove that $M$ is a prime number that solves the equation $M \equiv 3\pmod4$.

So how can I prove that $p_1p_2\cdots p_r +2 \equiv 3 \pmod4$?

  • 1
    $\begingroup$ It is incorrect to say "infinite primes" if you mean "infinitely many primes". If there were such a thing as an "infinite prime" (and in some contexts there is) then if you had two of them, you'd have infinite primes, but not infinitely many primes, since there are only two. $\endgroup$ – Michael Hardy Dec 12 '16 at 18:45
  • $\begingroup$ @MichaelHardy I'm studying with another language so it's a little bit difficult to translate it properly to english. $\endgroup$ – Ilan Aizelman WS Dec 12 '16 at 18:46
  • 1
    $\begingroup$ Many English-speaking non-mathematicians make the same mistake. $\endgroup$ – Michael Hardy Dec 12 '16 at 18:48
  • 1
    $\begingroup$ Well, I would not call that a "hint" but an answer. If $r$ is even then $M\equiv3^r+2\equiv(-1)^r+2\equiv3\pmod4$ and since clearly $p_i\nmid M$ for all $i$ then..If $r$ is odd then $M\equiv3^{2+(r-1)}\equiv(-1)^{r+1}\equiv-1\pmod4$ $\endgroup$ – CIJ Dec 12 '16 at 19:04
  • $\begingroup$ Hint. There are two types of odd numbers. Those in the form of 4k+1 and those in the form of 4k + 3. (4k+3)(4j + 3) = 4(4kj + k + j + 2) + 1=4m + 1. (4k +1)(4j + 1) = 4(4kj + k + j) +1 = 4n +1. (4k+1)(4j + 3) = 4(4kj + 3k + j) + 3 = 4o + 3. So... is M: a) even? b) 4k + 1 or c) 4k + 3? Is M prime? If not what form are its prime factors? and are any of the $p_i$ a prime factor of $M$? [The answer to the last question is "no" because $p_i|(M -2)$ and $p_i \not | 2$.] $\endgroup$ – fleablood Dec 12 '16 at 19:50

Slightly different proof: Assume $p_1,p_2,\ldots,p_r$ are all the prime numbers that are equivalent to $3$ mod $4$. But then $$(p_1p_2\cdots p_r)^2+2\equiv \left((-1)^r\right)^2+2\equiv 3\pmod{4}$$

has a prime divisor $q$ of the form $4k+3$, $k\in\mathbb Z$ (Proof: firstly, all the prime divisors must be odd, because $(p_1p_2\cdots p_r)^2+2$ is odd, so they're all equivalent to either $1$ or $3$ mod $4$. If all of them were $1$ mod $4$, then $(p_1p_2\cdots p_r)^2+2$ would be equivalent to $1$ mod $4$, contradiction)

that can't divide any of $p_1,p_2,\ldots,p_r$ (Proof: otherwise it would divide $\left((p_1p_2\cdots p_r)^2+2\right)-(p_1p_2\cdots p_r)^2=2$, contradiction).

So there's another prime $q$ of the form $4k+3$ that is not in the list $p_1,p_2,\ldots,p_r$, contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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