# Origin of well-ordering proof of uniqueness in the FToArithmetic

In the Appendix to Ivan Niven's book "Numbers: Rational and Irrational", he proves the Fundamental Theorem of Arithmetic (FToA) without using Euclid's Lemma that if a prime divides a product, then it divides one of the factors of the product. Niven's proof instead uses well-ordering.

He assumes that m is the smallest positive integer with two different prime factorizations, say

$$m=p_1 p_2 p_3 \ldots p_r \qquad \text{and} \qquad m=q_1 q_2 q_3 \ldots q_s$$

Typically, Euclid's Lemma would now be invoked repeatedly to say that each prime in one factorization of a number must also occur in any other, giving a contradiction. (Or more typically, this idea is rewritten as a direct proof.)

Niven instead proceeds saying that the two factorizations cannot have a prime in common, since if they did, we could assume without loss of generality that p_1 = q_1. Then $m/p_1$ would be a positive integer smaller than $m$ with the two different factorizations

$$m/p_1 = p_2 p_3 \ldots p_r \qquad \text{and} \qquad m/p_1 = q_2 q_3 \ldots q_s,$$

So without losing generality, we may assume $p_1 < q_1$. Niven proceeds to show that the number $(q_1 - p_1) q_2 q_3 \cdots q_s$ is a positive integer smaller than $m$ with two different prime factorizations --- one containing $p_1$ as a factor and the other not. This contradiction proves the uniqueness part of the FToA.

My question is, who originated this proof?

-
I thought adding the "reference-request" was appropriate. –  Hagen von Eitzen May 8 '13 at 21:28

I believe the proof is due to Ernst Zermelo. It appeared in print in 1934, Elementare Betrachtungen zur Theorie der Primzahlen, Nachr. Gesellsch. Wissensch. Göttingen 1, (1934), 43-46. A critical analysis, together with an English translation, can be seen in Ernst Zermelo. Collected Works - Gesammelte Werke, vol. I: Set Theory, Miscellanea - Mengenlehre, Varia. Heinz-Dieter Ebbinghaus, Akihiro Kanamori, eds. Springer, 2010.

Zermelo states that he shared the proof as early as 1912 with Hurwitz and Landau, who indicated the argument was new.

Der vorstehende Beweis ist eine leichte Abänderung eines früheren Beweises, den ich bereits um 1912 verschiedenen Arithmetikern wie A. Hurwitz und E. Landau brieﬂich mitgeteilt hatte, ohne daß sie sich seiner Präexistenz in der Literatur erinnert hätten.

The proof stated here is a slightly modiﬁed version of an earlier proof which I communicated to various arithmeticians such as A. Hurwitz and E. Landau in writing as early as around 1912 without evoking from them any recollection as to whether it already existed in the literature.

(I have seen others claim that Zermelo had the argument as early as 1901, but this seems unsubstantiated.)

As Pete points out in his answer, Lindemann published in 1933 essentially the same argument, obtained independently. The reference is F.A Lindemann, The Unique Factorization of a Positive Integer, Quart. J. Math. 4, (1933), 319-320.

-

The proof seems to be due to Lindemann (1933) and Zermelo (1934), independently. See the beginning of this note for the references.

Strangely, the result appears earlier in the literature: in a 1928 paper of Hasse. So in an earlier draft of loc. cit. I referred to the "Hasse-Lindemann-Zermelo proof". But actually the argument was known to Zermelo in 1912: see the footnote at the bottom of p. 4 of loc. cit. for more information on that.

-