Very elementary number theory redone

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

Because (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)

Furthermore we deduce from the definition of PF

(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)

From (5) and (6), relation 4 follows by the standard inference rule. (End of Proof of Theorem 0).

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)

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.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₁ p₂ ... p_r = q₁ q₂ ... q_s

Note the dots and the need to introduce the subscripts r and s. A little later, after having excluded p₁ equals q₁: “Suppose p₁ < q₁. (If q₁ < p₁, 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 10-Nov-2015 .