[Math] Proof – There’re infinitely many primes of the form 3k + 2 — origin of $3q_1..q_n + 2$

elementary-number-theoryintuitionproof-verification

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

Best Answer

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