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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to prove that there are infinitely many primes with remainder of 2 when divided by 3. I started out similarly to Euclid's classic proof of an infinite number of prime numbers:

Suppose there is only a finite set of prime numbers with remainder of 2 when divided by 3, then we can write their product as:

$$ P = q_1 \cdot q_2 \cdots q_r, \qquad \text {for some integer } r, = $$ $$ (3q_1+2)\cdot(3q_2+2)\cdots(3q_r+2), $$ for integers $q_r$.

This is where I am stuck. I do not know how to get to a similar contradiction as Euclid did when he considered $P$+$1$ and how the $q_i$'s could not divide $P$+$1$ since they divided $P$. (If they divided $P$+$1$ then they would divide $P$ and $1$, where dividing $1$ is the contradiction). Any ideas on how I can get to a similar contradiction?

Origin — Elementary Number Theory — Jones — p28 — Exercise 2.6

share|cite|improve this question
Use Dirichlet's theorem on primes in Arithmetic progressions. Well it is an overkill but you don't have to do – s.b Sep 13 '12 at 6:26
This approach is not analogous to Euclid's classic proof. Euclid did not assume that there is only a finite set of prime numbers. – joriki Sep 13 '12 at 9:02
"It is often erroneously reported that Euclid proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. Although the proof as a whole is not by contradiction, in that it does not begin by assuming that only finitely many primes exist, there is a proof by contradiction within it: that is the proof that none of the initially considered primes can divide the number called q above." – Pedro Tamaroff Sep 13 '12 at 22:25
up vote 26 down vote accepted

Let $q_1,q_2,\dots,q_n$ be odd primes of the form $3k+2$. Consider the number $N$, where $$N=3q_1q_2\dots q_n+2.$$ It is clear that none of the $q_i$ divides $N$, and that $3$ does not divide $N$.

Since $N$ is odd and greater than $1$, it is a product of one or more odd primes. We will show that at least one of these primes is of the form $3k+2$.

The prime divisors of $N$ cannot be all of the shape $3k+1$. For the product of any number of (not necessarily distinct) primes of the form $3k+1$ is itself of the form $3k+1$. But $N$ is not of the form $3k+1$. So some prime $p$ of the form $3k+2$ divides $N$. We already saw that $p$ cannot be one of $q_,\dots,q_n$. It follows that given any collection $\{q_1,\dots,q_n\}$ of primes of the form $3k+2$, there is a prime $p$ of the same form which is not in the collection. Thus the number of primes of the form $3k+2$ cannot be finite.

share|cite|improve this answer
See Euclidean Proofs Of Dirichlet’s Theorem for a nice discussion of when these variants of Euclid's argument work. – lhf Sep 13 '12 at 4:08
The simplest ones are $4k+3$ and $3k+2$. After one has some information about quadratic congruences, there are a few other accessible ones. – André Nicolas Sep 13 '12 at 4:08
Note that this proof, unlike the one in the question, is analogous to Euclid's proof, since it infers the existence of a further prime without assuming that the given primes are all the primes. – joriki Sep 13 '12 at 9:09
@joriki Not that I can see that huge a difference between "assume these are all prime numbers of the given form, then arrive at a contradiction by producing a new one" and "take any finite set of primes of the given form and produce a new one" – Arthur Sep 13 '12 at 21:38
One nice advantage of using $3P-1$ rather than $3P+2$ is that the prime $2$ isn't a special case and can be treated like any other $3k+2$ prime. – Erick Wong Sep 13 '12 at 21:42

$3P - 1$ is either a prime itself or has at least one prime factor $q \equiv 2 \pmod 3.$ The reason for this is that the product of any number of primes that are $\equiv 1 \pmod 3$ is again $\equiv 1 \pmod 3.$ So, since $3P - 1 \equiv 2 \pmod 3,$ we know there is some $q$ as described.

Note that $$ \gcd(3P-1,P) = 1, $$ so the new $q$ cannot divide $P,$ and therefore is not equal to any of your original list of primes.

share|cite|improve this answer
This doesn't answer the question.. (at least I don't see how) – picakhu Sep 13 '12 at 14:34
@picakhu Hint: it's a big hint for the inductive step. For details see Andre's answer, which uses $\rm\:3P+2\:$ vs. $\rm\:3P-1.\:$ The point is that its both coprime to the other $\rm\:p_i\:$ since they divide $\rm\,P,\,$ and, being $\equiv -1\pmod 3\:$ it must have at least one prime factor $\equiv -1\pmod 3\ $ (else all prime factors are $\equiv 1\:$ so their product $\rm\:3P-1 \equiv 1\pmod 3,\:$ contradiction). $\ $ – Bill Dubuque Sep 13 '12 at 14:53
@Bill Thanks! I hope it helps others too. – picakhu Sep 13 '12 at 15:00

Let $N > 2$ be an integer. Early on in Chapter 10 of these notes, on p120 as Theorem 121, I explain how Euclid's proof of the infinitude of primes can be very slightly modified to prove the following generalization:

There are infinitely many prime numbers $p$ such that $p$ is not of the form $kN+1$.

When $N = 3$, this means that there are infinitely primes which are either of the form $3k$ or $3k+2$. Since there is only one prime of the form $3k$, this answers your question.

(The notes go on to mention that essentially the same argument proves that for any proper subgroup $H$ of $(\mathbb{Z}/N\mathbb{Z})^{\times}$, there are infinitely many primes $p$ such that the reduction of $p$ modulo $N$ does not lie in $H$.)

share|cite|improve this answer
+1, esp. for the notes! – Bill Dubuque Sep 17 '12 at 14:16
@Dwayne: I'll leave your edit as it is for now (thanks for taking an interest), but there is a reason I refer to my notes by Chapter and Section rather than page number: many of these notes are being edited and reuploaded as time passes, so a reference to a page number is less likely to stay correct than a reference to a Chapter. (A better solution would be for me to implement some kind of version-control...Maybe someday.) – Pete L. Clark Jan 6 '14 at 2:58
Thanks — no problem — please go ahead and change as it as you update. – Dwayne E. Pouiller Jan 6 '14 at 5:07
@Dwayne: Well, that's the problem. I have approximately 2000 pages of lecture notes on various topics that I tinker with at various times...e.g. when someone sends me an email pointing out a typo. I don't then have any easy way to go back and update the references I may have made to them on this site. – Pete L. Clark Jan 6 '14 at 8:09

Break it into two cases depending on the parity of $r$. Start by showing that if $r$ is even, $P$ has a remainder of $1$ when divided by $3$, while if $r$ is odd, it has a remainder of $2$. In the first case show that $P+1$ must have a prime factor of the right form; in the second case, consider $P+3$ instead.

share|cite|improve this answer

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.