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

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

To instigate a contradiction, postulate $q_1,q_2,\dots,q_n$ as all the primes $\neq 2 (=$ the only even prime) of the form $3k+2$. Consider $N=3q_1q_2\dots q_n+2.$ None of the $q_i$ divides $N$, and $3 \not | N$.

$N$ = 3(the product of odd numbers) + 2 = odd number + even number = odd. Because $N \ge 2 $,
$\color{brown}{♯}$ because $N$ is odd $\implies 2 \not | N$,
thence by $\color{brown}{♯}$ and the Fundamental Theorem of Arithmetic, N = a product of one or more $\color{brown}{odd}$ primes. The prime divisors of $N$ cannot be all of the shape $3k+1$. At least one of these primes is of the form $3k+2$ — Why? $(3a + 1)(3b + 1) = 3(...) + 1$, thence 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$. Overhead in first paragraph, we proved $q_i \not|N$ for all $i$. Therefore $p \notin$ $\{q_1,\dots,q_n\}$ of primes of the form $3k+2$, contradiction.

  1. The general proof just starts with primes. Therefore how can you prefigure this proof's different start with odd primes ?

  2. Where did this choice of $N$ hail from — feels uncanny?

  3. I don't understand how none of the $q_i$ divides $N$?

share|cite|improve this question
  1. Purport that you start with all primes of the form $3k+2$ including $\color{red}2$, thence you start with $M = 3q_1 ... q_n \color{red}2 + 2$ You will quickly realize that the argument don't work, because $\color{red}2$ always divides $M$ and we want a number outside the list to divide $M$. You would not be able to conclude that there are primes of the form $3k+2$ NOT on the list.
    So remove $\color{red}2$ from the list is just a natural thing to do.
  2. You want a number that doesn't divide any primes on the list and is of the form $3k+2$. You know that the number have to be of the form $3k+2$. So start out by thinking what is the possible value of $k$. If $k$ is not divisible by a prime $q_{i}$ on the list, you will quickly find that $q_{i}$ divides $N$. Because you want all $q_{i}|k$, their product $\Pi \, q_i$ is just one possible choice.

  3. $q_{i}$ divide $N-2$ by definition. So if $q_{i}$ divide $N$ too, you end up with $q_{i}$ divide $2$, which is not possible because $q_{i}$ is odd and is a prime.

  4. $N$ is odd so it is not divisible by any even number, prime or not.

share|cite|improve this answer
Thanks. Upvote. Can you please explain and work out 'If $k$ is not divisible by a prime $q_i$ on the list, you will quickly find that it would be difficult to rule out the possibility that $q_i$ divide N. So make you want k to be divisible by all $q_i$, and their product is just one possible choice.' I'm flustered by this. – Dwayne E. Pouiller Jan 6 '14 at 6:34
@DwayneE.Pouiller: let's say your list of $q_{i}$ consist of 3 primes $5,11,17$ and you want to find a prime number not on the list. Now let's say you pick $k=561$, with this value $5$ does not divide $k$ but $11$ divide $k$ and $17$ divide $k$. With this value of $k$ you have $3k+2=1685$. Easily check that now both $11$ and $17$ does not divide $3k+2$. However, we got a problem: $5$ divide $3k+2$ so this simple argument are not enough to show that there are primes of that form outside the list $5,11,17$. If you picked $k=935=5\times 11\times 17$ instead you would not have that problem. – Gina Jan 6 '14 at 6:42
Thanks again. Can you please move your comment into your answer and answer only in your answer? How'd you pick $k = 561$? Is it by reason of $561 = 3.11.17$? I refashioned your answer to 2 - edify me if it's astray. – Dwayne E. Pouiller Apr 8 '14 at 6:55

Let's see if the following observations help:

  1. Different statement $\Rightarrow$ different proof :-)
  2. $N$ was chosen to be of form $3k+2$ precisely to guarantee that it must be divisible by at least one prime of the form $3k+2$.
  3. Look at the form of $N$: It was chosen so that $(N-2)$ is divisible by all of $q_i$, so if $N$ was to be divisible by $q_i$ too, $q_i$ would have to divide $2$. But that's impossible, since $q_i$ is an odd prime and thus strictly greater than $2$.
  4. If you multiply several natural numbers and at least one of them is even, the product will be even. Thus, if we're looking at an odd number and its factorization to primes, no even prime (i.e. no $2$) can occur in it.
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.