Euclid’s Method of proving Unique Prime Factorisatioon
It is often said that Euclid (who devoted Books VII – XI of his Elements to Number Theory) recognized the importance of Unique Factorization into Primes and established it by a theorem (Proposition 14 of Book IX). This is not quite correct. Modern authors usually present UPF in the following way
THEOREM Any positive integer N can be written as a product of primes in one and only one way barring changes in order. i.e. N = pa qb rc…..
But what Euclid establishes by Book IX Proposition 14 — Heath, whose translation I use throughout calls ‘theorems’ ‘propositions’ — is
“If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it.”
Now, from this one can, with the help of one or two other theorems, deduce Unique Prime Factorization (UPF), but Euclid does not actually do so. For one thing, Euclid would need to show that every (natural) number can be presented as a product of primes if Proposition 14 is to have a universal application. He goes some way to doing this in Propositions 31 and 32 of Book VII : Any composite number is measured by some prime number” and “Any number either is prime or is measured by some prime number”. But, for some reason, we lack the clinching Proposition, that all numbers can be written as a product of primes and that there is only one way of doing this barring changes in order.
Euclid’s presentation of Number Theory is so idiosyncratic, not to say perverse, that many readers, flipping through the Elements, do not even realize that he ever dealt with numbers at all. This is because Euclid insists on presenting (whole) numbers as line segments
A ______________ B __________ and not, as one would expect, as collections of discrete elements, e.g. by such sequences as ● ● ● ● ● ● ● ● or □ □ □ □ It is true that, by presenting numbers as lines Euclid gains generality : we can see in the above that A > B but we are not limited to specific magnitudes. Also, Euclid did not have the … facility which we have.
However, I doubt if this was the real reason. By Euclid’s time geometry had almost entirely ousted arithmetic as the dominant branch of mathematics much in the way that algebra subsequently ousted geometry. Pride of place in the Elements is given to the theory of proportion developed by Eudoxus. In the books devoted to Number Theory Euclid only deals with whole numbers (presented as line segments) and ratios between whole numbers which mimic ratios between sides of triangles and other figures. He does not mention ‘fractions’ as such though Greek housewives and practical people must have been well acquainted with them. Why is this? Partly no doubt because of the influence of Plato who, though not himself a mathematician, was well versed in the higher mathematics of his time and remains one of the most important theorists in the history of mathematics. Plato’s view that the ‘truths of mathematics’ are in some sense independent of human experience, while nonetheless underlying it, is the view held by many pure mathematicians today. Plato considered mere calculation with numbers to be a lowly activity, the affair of craftsmen and merchants, while geometry was a discipline that ennobled the practitioner by fixing his eye on the eternal. This explains the radical ‘geometrization’ of number that we find in Euclid.
In his Books on Number Theory, it would seem that Euclid was building on a much older arithmetic tradition which not only presented numbers as discrete entities but actually used objects such as pebbles or shells in calculations and formed them into shapes — which is why we still speak of ‘triangular numbers’, ‘square numbers’ and so forth (Note 1). The material of Book VII, the basic Book dealing with Number Theory, looks as if it goes back a very long way indeed and this is at once an advantage and a drawback.
It is an advantage because Euclid kicks off with an eminently practical procedure (rather than an abstract theorem in our sense), the so-called Euclidian Algorithm, and makes it the foundation of the entire edifice. Most of Euclid’s proofs are by contradiction and thus ‘non-constructive’ but the Euclidian Algorithm not only demonstrates that a ‘least common measure’ of two or more numbers always exists, but actually shows you how to obtain it. Remarkably, the Euclidian Algorithm works perfectly well in any base, or indeed without any base at all — and this suggests that it is a very ancient procedure. It was quite possibly discovered before written numbers even existed : in effect, it shows you how to group or bag up two different collections of similarly sized objects without anything being left over, using the largest possible bag size. Proposition 1 is a special case of this : when the largest bag size possible turns out to be the unit. Such an outcome situation must have seemed extraordinary to the people who first discovered it, and indeed mankind has ever since been fascinated by ‘prime numbers’ — they were originally called ‘line numbers’ because they could only be laid out in a line or column, never as a rectangle.
However, probably because they are based on an ancient source, Euclid’s presentation in the Books devoted to Number Theory is not so impeccably logical as in the other Books. Euclid does not introduce any new Axioms in Book VII, the first of the four books dealing with Number Theory, though he does give twenty-two Definitions. He presumably assumed that the general Axioms, given in Book I, sufficed. In fact, they do not. Operations with or on numbers differ from operations on geometric figures since plane figures and solids do not have ‘factors’ in the way that numbers do. As Heath notes, Euclid does not state as an Axiom that factorisation is transitive (as we would put it), i.e. “If a ∣ B & B ∣ C, then a ∣ C”, nor does he prove it as a theorem though he assumes it throughout. The Euclidian Algorithm would not work without this feature and a large number of other Propositions would be defective. Indeed, as Heath specifies, we not only need the above but the Sum and Difference Factorisation Theorems which, in Euclid’s parlance, would be
If A measures B, and also measures C, then A measures the sum of B and C, also the difference of B and C when they are unequal and B is greater than C.
i.e. a ∣ B & a ∣ C, then a ∣ (B + C), also a ∣ (B ‒ C) when B > C
An even more serious admission, from our point of view, is that Euclid does not explicitly state the Well-Ordering Principle, namely that Every non-increasing sequence of natural numbers has a least member though he assumes it in various propositions. Given the strong anti-infinity bias of Greek thought, Euclid would doubtless have thought it unnecessary.
Euclid proves Proposition 14 (If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it) in the following way :
“Let N = pqrs… where p, q, r…. are primes. Suppose a prime u different from primes p, q, r… and which divides N. Then N = u × b.
But if any prime number divides (m × n) and does not divide m, it must divide n [VII. 30].
Now, pôN and p does not divide u since u, p are primes and u ≠p Therefore, p ∣ b. And the same applies to q, r….
Therefore, pqr… ∣ b
But this is contrary to the hypothesis, since b < N and N is the smallest number that can be divided by pqr….
Therefore, N has no prime factors apart from p, q, r… “
It should be noted that this is a Proof by Contradiction and that it applies only to the case where p, q, r… are each of them distinct primes.
What Propositions does this proof rely on?
Firstly, on VII. Proposition 30 “If two numbers by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers.”
This is one of the most important theorems in the whole of Number Theory and I call it the Prime Factor Theorem. What applies here is the special case when one at least of the two original numbers is prime — and a different prime from the ‘dividing number’.
But Euclid also needs to prove, or to have proved, that, N really is, in our terms, the Least Common Multiple of p, q , r…. This he has done in Book VII. Propositions 34 and 35 which detail the procedure for finding the Least Common Multiple, first of two numbers (Prop. 35), and secondly of three or more numbers (Prop. 36). As a special case, Euclid shows that the LCM of two numbers a, b that are prime to each other is ab and that the procedure can be applied as many times as we wish so that the LCM of a,b,c…. where a, b, c are primes is abc… (He is also scrupulous enough to show (Proposition 29) that a prime and any other ‘number it does not measure’ are prime to each other, which makes any two primes ‘prime to each other’.)
Euclid does not generalize Proposition 14 to powers of these primes, i.e. to our pa qb rc… though this extension is in effect covered by the propositions about Least Common Multiples VII. 34, 35 and 36 taken together with VII. 31 and 32.
The propositions concerning LCMs are very much what one would expect and are easily assented to. The same does not apply to the Prime Factor Theorem which is by no means ‘intuitively obvious’ nor that easy to establish.
In modern terms Euclid’s proof of the Prime Side Theorem is as follows:
“Suppose p ∣ N (= ab) where p is prime, and p does not divide a.
Then (p, a) = 1 [VII. 29]
Let ab = pm = N where m is some number.
Then p ∣ a = b ∣ m [VII. 19]
But since (p, a) = 1, p/a is in its lowest terms. Therefore m must be a multiple of a and b a multiple of p [VII. 20, 21].
So, if p ∣ ab where p is prime, then either p ∣ a or p ∣ b (or both).”
The key proposition here is VII. 19, the Cross Ratio Theorem: “If four numbers be proportional, the number produced from the first and fourth will be equal to the number produced from the second and third; and, if the number produced from the first and fourth be equal to that produced from the second and third, the four numbers will be proportional.”
This cumbersome statement shows the importance of algebraic notation which the Greeks did not have. Remember that Euclid is speaking only of ratios between hypothetical line segments, not of ‘rational numbers’ as modern mathematicians understand them. However, bearing this in mind, Euclid’s proof may be presented thus :
“Let ac/ad = c/d = a/b
But a/b = ac/bc
So ac/ad = ac/bc
This can only be true if ad = bc
Conversely, let ad = bc
Then ac/ad = ac/bc
However, ac/ad = c/d
Also ac/bc = a/b
Therefore a/b = c/d“
The above itself depends on the legitimacy of ‘cancelling out’, likewise the legitimacy of multiplying and dividing numerator and denominator by the same factor. Euclid has already dealt with such issues and I will not trace the derivation any further back. He has, I think, made a proposition by no means obvious — the ‘Prime Factor Theorem’ — entirely acceptable and, if we accept the latter, we must accept Book IX Proposition 14. Apart from some tidying up and expansion, Unique Prime Factorization in the Natural Numbers has been established.
There was in fact another way to prove the Prime Factor Theorem which is more in keeping with the general plan of Book VII since the above theorem can be made to depend on the Euclidian Algorithm. The latter, for those who are not familiar with it or need a reminder, is a foolproof method for finding the lowest common factor of two numbers. Algebraically, take two different whole numbers M and N where M > N
M = a N + R1
N = b P + R2
P = c Q + R3
…….
This sequence will eventually come to an end since the divisors are diminishing i.e. Q < P < N < M
(This is an example of Euclid appealing to the Well-Ordering Principle without stating it as such.)
Suppose, the very next line leaves no remainder.
Q = d T
For N = b P + R2 = b (cQ + R3) + R2
N = b P + R2 = b (cQ + R3) + R2
Note 1 : “It seems clear that the oldest Pythagoreans were acquainted with the formation of triangular and square numbers by means of pebbles or dots; and we judge from the account in Speusippus’s book On the Pythagorean Numbers, which was based on the works of Philolaus, that the latter dealt with linear numbers, polygonal numbers, and plane, and solid numbers of all sorts….” (Heath, History of Greek Mathematics p. 76)
Origins of Mathematics 