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)
In view of (1), (3) can be rewritten
 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)
we can state

Theorem 0. (An : 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)
Because (An : 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)
Furthermore we deduce from the definition of PF

(Ax, 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)
From (5) and (6), relation 4 follows by the standard inference rule. (End of Proof of Theorem 0).

Theorem 1. (Ap : 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. (Ap, 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. (An : 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)
Inspired by our proof of Theorem 0, we observe that (7) follows from (8) and (9), given by
 (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)
Of these two, (8) follows immediately from (2), (3) and the definition of UPF. Assertion (9) requires, however, a more elaborate argument.

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)
holds. Because m is composite, it can be written as
 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)
as follows. When 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
Because 1 ≤ M < m, we conclude from (10) UPF m. Because M = q.Q −p.Q = p.Pp.Q = p.(Pq), 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|(qp); 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.
(Ap, 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  of essentially the same proof of Theorem 3. I found that presentation contorted and notationally clumsy. They write (for (11))

 m = p1 p2 ... pr = q1 q2 ... qs
Note the dots and the need to introduce the subscripts r and s. A little later, after having excluded p1 equals q1: “Suppose p1 < q1. (If q1 < p1, 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.

 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 10-Nov-2015 .