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$?


2 Answers 2


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.
  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.

  • $\begingroup$ 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. $\endgroup$ Jan 6, 2014 at 6:34
  • $\begingroup$ @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. $\endgroup$
    – Gina
    Jan 6, 2014 at 6:42
  • $\begingroup$ 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. $\endgroup$ Apr 8, 2014 at 6:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .