The Fundamental Theorem of Arithmetic

Abstract

The Fundamental Theorem of Arithmetic (FTA) states that every integer greater than 1 has a factorization into primes that is unique up to the order of the factors. The theorem is often credited to Euclid, but was apparently first stated in that generality by Gauss. Note that the statement has two parts: First, every integer greater than 1 has a factorization into primes; second, any two factorizations of an integer greater than 1 into primes must be identical except for the order of the factors. The proofs of each of those parts will thus be considered separately.

The Fundamental Theorem of Arithmetic (FTA) states that every integer greater than 1 has a factorization into primes that is unique up to the order of the factors. The theorem is often credited to Euclid, but was apparently first stated in that generality by Gauss.¹ Note that the statement has two parts: First, every integer greater than 1 has a factorization into primes; second, any two factorizations of an integer greater than 1 into primes must be identical except for the order of the factors. The proofs of each of those parts will thus be considered separately.

The first part is the subject of propositions VII,31 and VII,32 of the Elements. Proposition VII,31 states that any composite number (that is, any number that has a proper divisor other than one) is divisible by some prime. Having established that, Euclid then immediately concludes in proposition VII,32 that any number greater than 1 is either prime or is divisible by some prime.

Euclid’s proof of VII,31: Let A be a composite number. By definition, A has a proper divisor B other than one. If B is prime, we are done. If not, B has a proper divisor C other than one, and then C is a proper divisor of A. If C is prime, we are done. Otherwise, C has a proper divisor other than one. Continuing in this fashion, one must eventually obtain a prime divisor of A, since otherwise there would be an infinite sequence of divisors $B,C,\ldots$ of A, each smaller than the one before, which is impossible.

Second proof (of VII,31 and VII,32 together): By complete induction on the integer A > 1. Suppose every integer greater than 1 and less than A is divisible by some prime. Consider A. If A is prime, we are done. Otherwise, A = BC with 1 < B, C < A. By the inductive hypothesis, B is divisible by some prime, and that prime divides A.

Repeated application of VII,32 then establishes the existence of a prime factorization for any integer greater than 1.

Note that the first of the proofs above is a reductio, while the second is a direct proof that explicitly uses induction. Euclid takes for granted that there cannot be an infinite strictly decreasing sequence of positive integers — a statement that nowadays would be deemed to require proof. The most direct proof is by means of the well-ordering principle, which is equivalent to induction (or complete induction). Indeed, the statement in question is itself logically equivalent to induction.

There is little more development of the first part of the FTA, since the second argument above is so simple. (Some further remarks about the first part will, however, be made at the end of the chapter). Consider then the second part of the FTA.

A corollary of the FTA is Euclid’s Lemma, which asserts that if a prime divides a product it must divide one of the factors. A strong form of Euclid’s Lemma, but restricted to products of just two factors, was stated by Euclid as proposition VII,30 of the Elements. A consequence of that result is Euclid’s proposition IX,14 (‘If a number be the least that is measured by [three distinct] prime numbers, it will not be measured by any other prime number except those originally measuring it.’).

Euclid did not consider products of more than three primes, nor products involving repeated factors. However, his proof of IX,14 can be applied to conclude that the representation of a number as a product of distinct primes is unique except for the order of the factors. To extend to products involving repeated factors one can apply proposition IX,13 of the Elements (which states that the only divisors of $p^{k}$ are the numbers $1,p,p^{2},\ldots,p^{k}$) in combination with VII,30. Alternatively, one can argue, as Gauss later did, that if a prime p appears to the power j in one factorization of a number n and to the power k in another, with j ⩽ k, then dividing by p ^j will yield two factorizations of another number, at most one of which involves the factor p. Applying VII,30 repeatedly then shows that p must in fact occur in neither, so j = k. Any other repeated prime factors may be similarly eliminated, so only products of distinct prime factors need be considered.

Consequently, Euclid’s Lemma also implies the second part of the FTA, and it is useful to distinguish proofs of the second part of the FTA that do not first prove Euclid’s Lemma from those that do. Proofs of the second part of the FTA may also be distinguished according to what extent (if any) they use mathematical induction, whether they are direct or indirect, whether they invoke the concepts of least common multiple or greatest common divisor, and whether they employ the division algorithm, the Euclidean algorithm, or neither.

6.1 Direct proofs of Euclid’s Lemma

The statement of proposition VII,30 in Euclid’s Elements is just that of Euclid’s Lemma: ‘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.’ The proof, however, only uses the assumption that the number measuring the product is prime to deduce that it is relatively prime to each of the original factors. It thus establishes the following stronger result, stated earlier in Chapter 4

Theorem:

If a divides bc and is relatively prime to b, then a divides c.

Proof

(a modern paraphrase of Euclid’s argument): Suppose a divides bc, say bc = ad, and a is relatively prime to b. Then a must be the least natural number that, when multiplied by d, yields a multiple of c; that is, ad must be the least common multiple of c and d. For let f denote the least such number, and suppose fd = ec. By the division algorithm, $a = \mathit{qf } + r$ for some q, r with 0 ≤ r < f, so $bc = \mathit{ad} = \mathit{qfd} + \mathit{rd} = \mathit{qec} + \mathit{rd}$. Hence $\mathit{rd} = \mathit{bc} -\mathit{qec} = (b -\mathit{qe})c$. By the minimality of f, r must equal 0, so a = qf and (since c ≠ 0) b = qe. q is thus a common factor of a and b, which implies that q = 1. Therefore a = f, as claimed.

To finish the proof, Euclid appealed to his proposition VII,20 (whose proof, however, was faulty; cf. footnote 1 in Chapter 4): a is the least natural number for which $a/b = c/d$, so a divides c. Alternatively, one may apply the division algorithm again to deduce that $c = \mathit{pa} + s$ for some p, s with 0 ≤ s < a. Then, $s = c -\mathit{pa}$, so

$$\displaystyle{\mathit{sd} = \mathit{cd} -\mathit{pad} = \mathit{cd} -\mathit{pbc} = (d -\mathit{pb})c.}$$

That is, sd is a multiple of c, so by the minimality of a, s = 0. Thus c = pa, so a divides c. q.e.d.

Whichever method is used to complete the proof above, the argument as a whole invokes the division algorithm twice, since (again as noted in footnote 1 of Chapter 4) a correct proof of Euclid’s VII,20 employs the division algorithm.

By contrast, the next proof (from Rademacher and Toeplitz 1957, pp. 71–72) of the weaker form of Euclid’s Lemma does so only once, to show that the least common multiple of two numbers divides any common multiple of them, but it makes use of an additional fact (displayed as (7) below) not employed in Euclid’s argument.

Second proof:

If m is the least common multiple of two numbers a and b and M is any common multiple of them, then m divides M; for, by the division algorithm, $M = \mathit{qm} + r$ for some q and r with 0 ≤ r < m, so the minimality of m implies that $r = M -\mathit{qm}$ must be 0. In particular, m must divide ab, say md = ab, where

$$\displaystyle{ \mbox{ $d$ must divide both $a$ and $b$.} }$$

(7)

(For if $m = \mathit{ka} = \mathit{lb}$, then $\mathit{md} = \mathit{kad} = \mathit{ab}$ and $\mathit{md} = \mathit{lbd} = \mathit{ab}$, so kd = b and ld = a.) Now suppose the prime p divides BC, and let L be the least common multiple of p and B. Since BC and pB are both common multiples of p and B, L divides both of those products — say LE = BC and LF = pB. By (7) above, F divides both p and B, and since p is prime, either F = 1 or F = p; that is, either L = pB or L = B. In the former case, $\mathit{LE} = \mathit{pBE} = \mathit{BC}$, so pE = C, that is, p divides C. In the latter case, p divides B, since L is a multiple of p. q.e.d.

That the quantity d in (7) is actually the greatest common divisor of a and b is nowhere used in the proof above. However, Euclid’s Lemma is an almost immediate consequence of the following well-known characterization of greatest common divisors.

Linear representation theorem:

If d is the greatest common divisor of a and b, then there are integers m and n, exactly one of which is positive, for which $d = \mathit{ma} + \mathit{nb}$ .

Proof of Euclid’s lemma from the linear representation theorem : 

If p is a prime that divides bc but not b, then the greatest common divisor of p and b is 1. Therefore $1 = \mathit{mp} + \mathit{nb}$ for some integers m and n, so $c = \mathit{mpc} + \mathit{nbc}$. Since p divides each summand on the right, p divides c. (Exactly the same argument holds if p is not necessarily prime, but merely relatively prime to b.)

The argument just given forms the conclusion of two distinct proofs of Euclid’s Lemma, which differ in how the linear representation theorem itself is derived.

Third proof

(summarized from Courant and Robbins 1941, pp. 45–47): The representation of the greatest common divisor of integers a and b as an integral linear combination of them is obtained constructively by examining the proof of the Euclidean algorithm (proposition VII,2 in Euclid’s Elements). That proof, and the implementation of the algorithm to compute m and n explicitly, involves iterated application of the division algorithm, in which the number of iterations required is not fixed, as in the two proofs given earlier, but depends on the values of a and b.² q.e.d.

Alternatively, the linear representation of the greatest common divisor may be demonstrated non-constructively as follows.

Fourth proof:

The set I of all linear combinations ma +nb, as m and n range over all integers, is an ideal within the ring of integers. Let d be an element of I whose absolute value is minimal. A single application of the division algorithm shows that d must divide every element of I, so in particular it must divide a and b. But any common divisor of a and b must also divide every element of I, including d. Therefore d must be a greatest common divisor of a and b (as must − d, so d may be taken to be positive without loss of generality). q.e.d.

A priori, the greatest common divisor of a and b is just that, the common divisor which is the largest. But one important consequence of the linear representation theorem is the following property of the greatest common divisor.

Divisibility property of the gcd:The greatest common divisor of a and b is divisible by every common divisor of a and b.

Proof.

Let c be a common divisor of a and b. Express the greatest common divisor d of a and b as $d = \mathit{ma} + \mathit{nb}$. Then, since c divides both a and b, c divides d as well.

Weintraub (in Weintraub 2008) gave the following proof of Euclid’s lemma from the divisibility property of the gcd (which itself may be proved in various ways).

Fifth proof:

Consider ac and bc. They have a greatest common divisor d. Now c divides both ac and bc, so by the divisibility property of the gcd, c divides d. Write d = cz. Now d divides bc, that is, cz divides bc, so z divides b. Similarly, cz divides ac, so z divides a. But a and b are assumed to be relatively prime, so z = 1 and d = c. Now a certainly divides ac, and a divides bc by hypothesis, so a divides d by the divisibility property of the gcd again; since c = d, a divides c.

6.2 Indirect proofs of the FTA and Euclid’s Lemma

The Fundamental Theorem of Arithmetic may also be proved outright, without first proving Euclid’s Lemma, through inductive arguments by reductio. Two such proofs, the first by Ernst Zermelo and the second by Gerhard Klappauf,³ are reproduced in Scholz (1961). Both begin by presuming, contrary to the statement of the FTA, that there are integers with distinct prime factorizations, among which there must be some least integer m. Zermelo then argued as follows.

Sixth proof:

Suppose $m = p_{1}p_{2}\cdots p_{k} = q_{1}q_{2}\cdots q_{s}$, with $p_{1} \leq p_{2} \leq \ldots \leq p_{k}$ and $q_{1} \leq q_{2} \leq \ldots \leq q_{s}$. By the minimality of m, p ₁ ≠ q ₁, so without loss of generality we may suppose that p ₁ < q ₁. Then the number

$$\displaystyle{n = m - p_{1}q_{2}\cdots q_{s} = p_{1}(p_{2}\cdots p_{k} - q_{2}\cdots q_{s}) = (q_{1} - p_{1})(q_{2}\cdots q_{s})}$$

is less than m, and so must possess a unique prime factorization. Since p ₁ is less than every q _i , it must therefore divide q ₁ − p ₁. But then p ₁ would divide q ₁, which is prime. Since $1 < p_{1} < q_{1}$, that is impossible. q.e.d.

In the paper in which he presented the proof just given, Zermelo stated that his reason for doing so was to show that even in elementary number theory it was possible to simplify the proofs.⁴ His proof, in turn, then stimulated Klappauf to show that the method Zermelo had used to produce the counterexample n could be further simplified.

Seventh proof:

Let m be as in Zermelo’s proof and consider the remainders r _i , for $i = 1,\ldots,s$ that are obtained when each q _i is divided by p ₁. We have $q_{i} = a_{i}p_{1} + r_{i}$, where each $r_{i} < p_{1}$. Since p ₁ < q _i for each i, every a _i must be positive; and since each q _i is a prime different from p ₁, every r _i is also positive. Hence $m = q_{1}q_{2}\cdots q_{s}$ can be written as $m = \mathit{Ap}_{1} + R$, where $R = r_{1}r_{2}\cdots r_{s}$ and A and R are both positive. Since p ₁ divides m, it must also divide R. But p ₁ cannot divide any r _i ; so factoring each r _i into primes yields a factorization of R that is distinct from the factorization involving p ₁. Since R < m that contradicts the minimality of m. q.e.d.

Unlike Zermelo’s proof, Klappauf’s employs the division algorithm. Moreover, in Klappauf’s proof $r_{1} = q_{1} - a_{1}p_{1} \leq q_{1} - p_{1}$, and r _i  < q _i for i ⩾2, so the number R used therein to contradict the minimality of m is less than the number $n = (q_{1} - p_{1})q_{2}\cdots q_{s}$ used for that purpose in Zermelo’s proof.

Euclid’s Lemma may also be proved by reductio. Indeed, Gauss did so (for the contrapositive statement) in his Disquisitiones Arithmeticae. His proof, presented next below, is actually a double reductio that invokes the division algorithm thrice.

Eighth proof:

Gauss first showed by reductio that no prime p can divide a product of two smaller positive integers. For suppose to the contrary that p is a prime that divides such a product, and let r < p be the least positive integer for which there exists a positive integer s < p such that p divides rs. Then r ≠ 1 (since s < p), so r does not divide the prime p. Hence by the division algorithm, $p = \mathit{qr} + t$, where 0 < t < r. But then $\mathit{ts} = \mathit{ps} -\mathit{qrs}$ is divisible by p, contrary to the minimality of r.

To complete the proof of Euclid’s Lemma, suppose then (again by reductio) that a prime p divides bc but neither b nor c. Then the division algorithm gives $b = q_{1}p + r_{1}$ and $c = q_{2}p + r_{2}$, with $0 < r_{1},r_{2} < p$. So bc can be expressed in the form $\mathit{qp} + r_{1}r_{2}$. That is, $r_{1}r_{2} = \mathit{qp} -\mathit{bc}$, which is a multiple of p if bc is; but that contradicts Gauss’s earlier result. q.e.d.

Another reductio proof of Euclid’s Lemma, in the strong form stated by Euclid, was given by Daniel Davis and Oved Shisha in a little-known article in Mathematics Magazine (Davis and Shisha 1981).⁵ The last of the proofs to be considered here, it is an elegant exemplar of purity of method.

Ninth proof:

Assume that there is a triple (A, B, C) of positive integers for which both of the following properties hold:

• P ₁(A, B, C). A divides BC but is relatively prime to B.

• P ₂(A, B, C). A divides BC but does not divide C.

Then for i = 1, 2, it follows directly that

$$\displaystyle{ (1.\,i)\qquad \qquad \mbox{ If $P_{i}(A,B,C)$ and $B > A$, then $P_{i}(A,B - A,C)$}\qquad \qquad \qquad \qquad }$$

and

$$\displaystyle{ (2.\,i)\qquad \qquad \mbox{ If $P_{i}(A,B,C)$, say $\mathit{BC} = \mathit{AD}$, then $P_{i}(B,A,D)$.}\qquad \qquad \qquad \qquad }$$

Proof of (1.1): If A divides BC and B > A, then A divides $(B - A)C = \mathit{BC} -\mathit{AC}$; and if A is relatively prime to $B = (B - A) + A$ it must also be relatively prime to B − A.

Proof of (1.2): If A divides BC but not C, then A divides $(B - A)C = \mathit{BC} -\mathit{AC}$ but not C.

Proof of (2.1): If BC = AD and A is relatively prime to B, then B divides AD and is relatively prime to A.

Proof of (2.2): If BC = AD but A does not divide C, then B divides AD but does not divide D.

Among all triples (A, B, C) satisfying P ₁ and P ₂ there is at least one, say $(A_{1},B_{1},C_{1})$, that minimizes $A + B + C$. Then by P ₂, A ₁ ≠ 1, so by $P_{1}$, $A_{1}\neq B_{1}$. By (2.i), the triple (A ₁, B ₁, D) also satisfies P ₁ and P ₂, and $B_{1}C_{1} = A_{1}D$; so if B ₁ < A ₁, then D < C ₁ and therefore $A_{1} + B_{1} + D < A_{1} + B_{1} + C_{1}$, contrary to the minimality property of $(A_{1},B_{1},C_{1})$. The only remaining possibility is B ₁ > A ₁. Then by (1.i), the triple $(A_{1},B_{1} - A_{1},C_{1})$ also satisfies P ₁ and P ₂; but $B_{1} - A_{1} < B_{1}$, so $A_{1} + (B_{1} - A_{1}) + C_{1} = B_{1} + C_{1} < A_{1} + B_{1} + C_{1}$, again contrary to the minimality property of $(A_{1},B_{1},C_{1})$. Hence by reductio, no triple (A, B, C) satisfying both P ₁ and P ₂ exist. That is, if A divides BC but is relatively prime to B, then A must divide C. q.e.d.

This proof of Davis and Shisha is distinguished above all by its economy of means, for it employs nothing more than subtraction and the concepts involved in the statement of Euclid’s Lemma (divisibility and relative primality).

6.3 Summary

It should be clear from the commentary above that the two proofs of the first part of the FTA considered in this chapter, and the nine proofs of the second part, are all structurally distinct. Moreover, they exemplify several of the rationales for presenting alternative proofs enumerated in Chapter 2: the desires to simplify, to minimize conceptual prerequisites, to extend to broader contexts, to achieve methodological purity, and to find new routes to a goal. As to proofs of the first part, the second proof is direct while the first proof is a proof by reductio. As to the second part, Gauss’s proof extended that of Euclid; the second, sixth and seventh proofs, and especially the ninth, exhibit various forms of simplification; and the third and fourth proofs introduce a concept (that of representing the greatest common divisor of two integers as a linear combination of them) that is foreign to all the others, while the fifth proof deliberately avoids using that concept.

It is enlightening to examine these proofs in the context of generalizations to commutative ring theory. As to the proofs of the first part, the first proof leads directly to the concept of a Noetherian ring, and directly generalizes to show that every element in a Noetherian integral domain has a (that is, at least one) factorization into primes. The second proof, while simpler, is one that is restricted to the positive integers.

As to the proofs of the second part, again the most direct proofs, the sixth, seventh, and ninth, are restricted to the positive integers.

The other proofs generalize to commutative rings of various kinds. By definition, a Euclidean domain is one in which there is a division algorithm, properly interpreted, and these proofs show that Euclid’s lemma holds in Euclidean domains, and hence that these are unique factorization domains (that is, that the analog of the FTA holds in them). By definition, a principal ideal domain is one in which an appropriate generalization of the linear representation theorem holds, and so the third and fourth proofs, which rely on that concept, show that every principal ideal domain is a unique factorization domain. Since there are principal ideal domains that are not Euclidean, this provides a further generalization. Furthermore, not every unique factorization domain is a principal ideal domain, so the fifth proof generalizes still further (though in this case one needs some other argument to show that the divisibility property of the gcd holds). The second proof, which introduces the concept of the least common multiple, is stated for the positive integers, and directly generalizes to Euclidean domains. But that same concept is fruitful in the more general contexts we have just described, and that proof can be modified to be valid in them as well.