13

Thirty or so years ago, someone showed me a clever proof of the Fundamental Theorem of Arithmetic that did not make use of the lemma "If $p\mid ab$ then $p\mid a$ or $p\mid b$". I'm unable to reconstruct the argument; all I remember is that it used induction and that it didn't generalize to other number rings. Can anyone provide such a proof, or provide other offbeat elementary proofs of unique factorization of natural numbers into primes?

Martin Sleziak
  • 4,608
James Propp
  • 19,363
  • 4
    Perhaps it was the proof on Wikipedia?

    https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Uniqueness_without_Euclid's_lemma

     – Steven Gubkin Jul 28 '21 at 15:29
  • No; that proof says "We see $p_1$ divides $q_1 q_2 \cdots q_k$, so $p_1$ divides some $q_i$ by Euclid's lemma." – James Propp Jul 28 '21 at 16:06
  • 5
    There are two proofs on that page; the second one does not use Euclid's lemma, or at least it claims not to. But it seems to me that it does, under the covers, by assuming that $p_1 | (q_1 - p_1) Q$ implies $p_1 | (q_1 - p_1)$ or $p_1 | Q$ – Matthew van Eerde Jul 28 '21 at 16:09
  • 2
    You are looking at the wrong proof. Just below that one is another, called "Uniqueness without Euclid's Lemma" – Steven Gubkin Jul 28 '21 at 16:10
  • 4
    @MatthewvanEerde This is not obtained by Euclid's lemma, but rather the minimality of s. – Steven Gubkin Jul 28 '21 at 16:12
  • 7
    Perhaps it's Zermelo's proof? https://planetmath.org/inductionproofoffundamentaltheoremofarithmetic. See also https://mathoverflow.net/questions/339853/zermelos-proof-for-unique-factorisation. – Ira Gessel Jul 28 '21 at 16:22
  • 5
    Ah, Steven Gubkin has it right! It's the same as Zermelo's proof (thanks Ira), which Pete Clark calls attributes to Lindemann as well. Sorry to have wasted people's time on something that was on Wikipedia; I stopped reading too soon. (Steve, if you want the MathOverflow points, just repost your comment as an answer and I'll upvote and approve it.) – James Propp Jul 28 '21 at 19:03
  • 7
    The claim that a proof of Theorem A "does not use" Theorem B does not mean much if (as is the case here) A and B are easily deduced from each other. In fact, the proof under consideration here is similar to the "direct proof" of Euclid's lemma given in https://en.wikipedia.org/wiki/Euclid%27s_lemma. – Laurent Moret-Bailly Jul 29 '21 at 07:04

1 Answers1

21

To summarize the comments, this is also known as Zermelo's proof. A version can be found on wikipedia. I will give the proof here to avoid link rot.

The proof is by contradiction. If FTA did not hold, then use the well ordering principle to select the smallest number $s$ which can be factored in two distinct ways into products of primes, $s = p_1p_2 \dots p_m = q_1q_2\dots q_n$. No $p$ can be equal to a $q$, for otherwise $s/p = s/q$ would give a smaller example, violating minimality.

Assume without loss of generality that $p_1 < q_1$. Let $P = p_2 \dots p_m$ and $Q = q_2 \dots q_n$. Then $s = p_1P = q_1Q$, so that

$$t=(q_1-p_1)Q = p_1(P-Q) < s$$

Since $t$ is less than $s$, then by minimality of $s$ there is only one way to factor it into a product of primes, namely the prime factorization of $q_1-p_1$ times the (known) prime factorization of $Q$. Since $p_1$ is a prime factor of $t$, $p_1$ must either be one of the prime factors of $q_1 - p_1$ or be one of the prime factors $q_i$ of $Q$. We already said that $p_1$ is not equal to any of the $q_i$, so $p_1$ is one of the prime factors of $q_1-p_1$. In particular, $p_1$ divides $q_1$. But $q_1$ is a prime not equal to $p_1$, a contradiction.

Steven Gubkin
  • 11,945
  • 1
    I took the liberty of slightly rewriting the last part of the proof to make it clearer that Euclid's lemma is not being assumed. – Timothy Chow Jul 29 '21 at 22:39
  • If I recall correctly, this is the proof showcased in Niven & Zuckerman's "An Introduction to the Theory of Numbers" (at least in the 2nd. edition of the text; I don't have a copy of the edition that was revised by H. Montgomery)... – José Hdz. Stgo. Jul 30 '21 at 03:52
  • 2
    `Since $p_1$ is a prime factor of $s$' is the wrong reason. – Wilberd van der Kallen Jul 30 '21 at 06:58
  • @TimothyChow I am not sure, but I seem to detect an implicit application of Eucl. VII-30 in the part that says "Since $p_{1}$ is a prime factor of $t$, $p_{1}$ must either be one of the prime factors of $q_{1}-p_{1}$ or be one the prime factors $q_{i}$ of $Q$." What do you think about this concern of mine? – José Hdz. Stgo. Mar 16 '24 at 04:35
  • @JoséHdz.Stgo. No, Euclid's lemma is not needed here. Every prime factor $p_1$ of $t$ is involved in some factorization of $t$ into primes; $t/p_1$ is either prime or has a prime factor that we can strip off, and the process of stripping off prime factors must terminate because we're getting smaller and smaller. But the minimality of $s$ implies that the prime factorization of $t$ is unique, so every prime factorization of $t$ (in particular, the prime factorization of $q_1 - p_1$ times the prime factorization of $Q$) must include $p_1$. – Timothy Chow Mar 16 '24 at 07:26