**Very elementary number theory redone.**

The *natural numbers* are 0, 1, 2 and so on; for further details, see Peano.

The *positive integers* are natural numbers ≥ 1, i.e. 1, 2, 3 and so on.

The *multiples* are natural numbers ≥ 2, i.e. 2, 3, 4 and so on. The product of two multiples is larger than each of those two, in formula

(A x, y : x ≥ 2, y ≥ 2 : x.y > x ∧ x.y > y ) | (1) |

Multiples that are the product of two multiples are called *composite*, multiples that are not composite are called *prime*, in formula

prime m = m ≥ 2 ∧ (A x, y : x ≥ 2, y ≥ 2 : x.y ≠ m) | (2) | |

comp m = m ≥ 2 ∧ (E x, y : x ≥ 2, y ≥ 2 : x.y = m) | (3) |

comp m = (E x, y : 2 ≤ x < m, 2 ≤ y < m : x.y = m) | (3′) |

From (3′) it is clear that it is decidable whether a specific `m` is composite.

Note that we have ¬(prime 1) ∧ ¬ (comp 1) .

With PF —for Prime Factorization— defined by

PF n = | n is the product of (0 or more) multiples, all of which are prime (the empty product being defined as 1) |

**Theorem 0.** (**A** `n` : `n `≥ 1 : PF `n`)

**Proof**. We shall prove Theorem 0 by mathematical induction, i.e. we shall prove

(A n : n ≥ 1 : (PF n) ∨ (E i : 1 ≤ i ≤ n : ¬(PF i))) | (4) |

**A**

`n`:

`n`≥ 1 :

`n`= 1 ∨ (prime

`n`) ∨ (comp

`n`)) and the product of one number equals that number, we deduce from the definition of PF

(A n : n ≥ 1 : (comp n) ∨ (PF n)) | (5) |

(**A** `x`, `y` : `x `≥ 1, `y `≥ 1 : ¬(PF `x`) ∨ ¬(PF `y` ) ∨ PF(`x`.`y` ))

from which we deduce with (3')

(A n : n ≥ 1 : ¬(comp n) ∨ (PF n) ∨ (E i : 1 ≤ i ≤ n: ¬ (PF i ))) | (6) |

**Theorem 1.** (**A** `p` : prime `p` : (__E__ `q` : `q `> `p` : prime `q` ))

(This is Euclid's famous theorem that no prime is the largest one.)

**Proof**. Consider for arbitrary prime `p` the value `Q` defined by

`Q` = 1 + the product of *all* primes ≤ `p`.

Theorem 0 allows us to conclude that `Q` is the product
of a bag of primes, and, because `Q `> 1, that bag is
not empty. By virtue of `Q`’s construction, such a bag
contains no prime ≤ `p`. Hence it contains at least one prime >` p`, hence at least one
prime > `p` exists. (End of proof of Theorem 1.)

With UPF —for Unique Prime Factorization— defined by

UPF `n` = The bag of prime multiples whose product equals `n` is unique

we can formulate

**Theorem 2.**
(**A** `p`, `x`, `y` : `p `≥ 1, `x `≥ 1, `y` ≥ 1 :
¬(prime `p`) ∨ ¬(`p`|(`x`.`y` )) ∨ `p`|`x` ∨ `p`|`y` ∨ ¬(UPF(`x`.`y` )))

(Here “`a`|`b` ” should be read as “`a` divides `b`”.)

**Proof.** When the first two terms are false, `x`.`y` is the product
of a bag of primes containing `p` ; when the next two terms are false, `x`.`y` is also the
product of a bag of primes *not* containing `p`. Those two bags being different,
we deduce ¬(UPF(`x`.`y` )).
(End of proof of Theorem 2.)

We are now ready to state and prove

**Theorem 3**. (**A** `n` : `n `≥ 1 : UPF `n`)

**Proof.** Theorem 3 is proved by mathematical induction, i.e. by proving

(A n : n ≥ 1 : (UPF n) ∨ (E i : 1 ≤ i < n : ¬(UPF i ))) | (7) |

(A n : n ≥ 1 : (comp n) ∨ (UPF n)) | (8) | |

(A n : n ≥ 1 : ¬(comp n) ∨ (UPF n) ∨ (E i : 1 ≤ i < n : ¬(UPF i ))) | (9) |

Consider a value of `n`, `m` say, such that the first and last terms of (9) are false, i.e. such that

(comp m) ∧ (A i : 1 ≤ i < m : UPF i ) | (10) |

m = p.P = q.Q with | (11) | |

1) | prime p | |

2) | p ≤ q | |

3) | P standing for the product of a non empty bag of primes all of which are ≥ p | |

4) | Q standing for the product of a bag of primes all of which are ≥ q. |

We obviously have 2 ≤ `P` < `m`, 1 ≤ `Q` < `m`, and `P` ≥ `Q`.

The conclusion UPF `m`, required to prove (9), can be drawn from

p = q ∨ (comp p) | (12) |

`q`is the smallest value in a bag of primes, comp

`q`is false and from (12) we deduce

`p`=

`q`. From (11) we deduce

`P`=

`Q`, and from (10) we deduce that

`P`and

`Q`stand for the same bag of primes. Since

`p`=

`q`,

`p`.

`P`and

`q`.

`Q`then also stand for the same bag of primes, and UPF

`m`has been established

Establishing (12) is now our only remaining obligation. It is trivial in the case `p` = `q`. In
the case `p` < `q` we consider value the `M` defined by

M = (q−p) . Q |

`M`<

`m`, we conclude from (10) UPF

`m`. Because

`M`=

`q`.

`Q`−

`p`.

`Q`=

`p`.

`P`−

`p`.

`Q`=

`p`.(

`P`−

`q`), we conclude

`p`|

`M`. Since prime

`P`, we now conclude from theorem 2

p | (q−p) ∨ p|Q | (13) |

Since 1 ≤ `Q` < `m`, we conclude from (10) UPF `Q`, i.e. all the primes in the *unique* bag of
primes whose product equals `Q` are ≥ `q`, hence > `p`. The bag being unique, we
conclude ¬(`P`|`Q` ). In combination with (13) we conclude `p`|(`q`−`p`); since we were considering
the case `p` < `q`, we can conclude that `q` is composite. Having thus established
relation (12), we have fulfilled our last proof obligation. (End of Proof of Theorem 3.)

**Corollary of theorems 2 and 3. **

(**A** `p`, `x`, `y` : `p `≥ 1, `x `≥ 1, `y `≥ 1 : ¬(prime `p`) ∨
¬(`p`|(`x`.`y` )) ∨ `p`|`x` ∨ `p`|`y` ) .

The above was written in reaction to the presentation in [1] of essentially the same proof of Theorem 3. I found that presentation contorted and notationally clumsy. They write (for (11))

m = p_{1} p_{2} ... p = _{r}q_{1} q_{2} ... q_{s} |

`r`and

`s`. A little later, after having excluded

`p`

_{1}equals

`q`

_{1}: “Suppose

`p`

_{1}<

`q`

_{1}. (If

`q`

_{1}<

`p`

_{1}, we simply interchange the letters

`p`and

`q`in what follows (sic).)”. A third of a page later they conclude that “the prime decomposition of

`m`′ must be unique, aside from the order of the factors”. Theorem 2 isn't mentioned and when needed in the proof of Theorem 3 they borrow the result from a corollary of theorem 3! (Here their argument is almost cyclic.) And it is full of reductiones ad absurdum.

[1] Courant, Richard & Robbins, Herbert,
*What is mathematics?* Oxford University Press paperback,
1978.

Plantaanstraat 5 | 20 October 1980 |

5671 AL NUENEN | prof. dr. Edsger W. Dijkstra |

The Netherlands | Burroughs Research Fellow |

Transcribed by Martin P.M. van der Burgt

Last revision