
[HM] Euclid and the unique factorization theorem
Posted:
Feb 5, 2000 9:35 AM


In his thoughtful {\it Mathematical reflections} (Amer. Math. Monthly, 1974, 827852), the "discerning antiquarian" Solomon Bochner (18991982) wrote:
\begin{quotation} [Leonard Dickson's] reluctance to present the fundamental theorem [of arithmetic] in an otherwise very conscientious historical account [Dickson's threevolume {\it History of the Theory of Numbers} (19191923)] may be due to the fact that, while this theorem is sometimes vaguely attributed to Euclid, it had apparently not been stated expressly before 1801, when Gauss featured it in his {\it Disquisitiones arithmeticae}, with some emphasis, and rather early in the work. The nearest that Euclid himself came to this theorem was his proposition (vii, 24): "if two numbers be prime to any number, their product also will be prime to the same." (...) Of course, what had discomfited Dickson was not just the fact that the fundamental theorem does not occur in Euclid, but, undoubtedly much more so, that none of the great numbertheorists in the 17th and 18th centuries, like Fermat, Wallis, Euler, Lagrange, etc., had chanced upon it either. (...) But there is no substance to assertions that the fundamental theorem had been consciously known to mathematicians before Gauss, but that they had neglected to make the fact known.ÃÂ We think that the 17th, and even the 18th, century was not yet ready for the peculiar kind of mathematical abstraction which the "fundamental theorem" involves; just as only the 19th century was comfortably prepared to conceptualize satisfactorily the notions of real number, limit, derivative, convergence, etc. \end{quotation}ÃÂ
According to Bochner, the paragraph quoted by Martin Davis from Hardy and Wright's famous book "was triggered by remarks made to G. H. Hardy by myself, and I well remember that the remarks were made, sometime in 1933, in Hardy's large living room in Trinity College".
Of course, there are some other delicate questions to be taken into consideration here. 1) Consider, for example, the Greek neglect of higher order quantifiers. I agree with Karlis Podnicks when he says that "the natural number concept of Greeks corresponds to first order arithmetic and that this concept remained unchanged up to 1870s." The relevance of this remark becomes clear when we note that the "fundamental theorem" is not a first order statement  since it involves the higher notion of a SEQUENCE of primes.
2) Consider also the existence of nonstandard models of arithmetic which "satisfies all the properties of order, addition, and multiplication which could reasonably be considered as prior to" the EXISTENCE part of the fundamental theorem, but in which that existence fails. (See J. C. Shepherdson's {\it Weak and strong induction}, Amer. Math. Monthly, 1969, 9891004, Theorem 2.9, p. 993.)
3) Compare the classical proof of the irrationality of Sqrt[2] with the more "powerful" one that rests essentially on the fact that
O[m . n, 2] = O[m, 2] + O[n, 2],
where, more generally,
O[m, n] = the greatest natural (0 included) $e$ such that $n^e  m$.
The logarithmic behavior of O with respect to $m$ for PRIME values of $n$, is due to the fact that, for a prime $p$, if $p  mn$ then $p  m$ or $p  n$  which is crucial to the UNIQUENESS part of the fundamental theorem.
4) In the light of these facts, can we really say that "Already in 300 B.C., Euclid was aware of the fundamental theorem of arithmetic"?
5) Just as a curiosity: Which fact really deserves to be called "the fundamental theorem of arithmetic"? According to J. V. Uspensky and M. A. Heaslet in their book {\it Elementary Number Theory} (McGrawHill, 1939, p. 32), the result which "is rightly called the fundamental theorem of arithmetic" is this one:
"If the product $ab$ of two integers is divisible by an integer $c$, and $c$ and $b$ are relatively prime, then $a$ is divisible by $c$."
More generally, we can prove that
IF $c  ab$ THEN $c  a (c,b)$
is true on a integral domain < R, plus, times, 0, 1 > for which
a) GCD[a,b]\neq \emptyset for all $a, b\in R$; b) Every gcd $(a,b)$ is a linear combination of $a$ and $b$.ÃÂ
If, in addition, $R$ is principal, we can prove that the notions of "prime" and "irreducible" coincide on $R$. ÃÂ Carlos C\'esar de Ara\'ujo from rainy Belo Horizonte.

