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?
$\begingroup$
$\endgroup$
8
asked Jul 28, 2021 at 15:18
-
4$\begingroup$ Perhaps it was the proof on Wikipedia? en.wikipedia.org/wiki/… $\endgroup$– Steven GubkinCommented Jul 28, 2021 at 15:29
-
5$\begingroup$ 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$ $\endgroup$– Matthew van EerdeCommented Jul 28, 2021 at 16:09
-
7$\begingroup$ Perhaps it's Zermelo's proof? planetmath.org/inductionproofoffundamentaltheoremofarithmetic. See also mathoverflow.net/questions/339853/…. $\endgroup$– Ira GesselCommented Jul 28, 2021 at 16:22
-
5$\begingroup$ 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.) $\endgroup$– James ProppCommented Jul 28, 2021 at 19:03
-
7$\begingroup$ 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 en.wikipedia.org/wiki/Euclid%27s_lemma. $\endgroup$– Laurent Moret-BaillyCommented Jul 29, 2021 at 7:04
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
1$\begingroup$ 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. $\endgroup$ Commented Jul 29, 2021 at 22:39
-
$\begingroup$ 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)... $\endgroup$ Commented Jul 30, 2021 at 3:52
-
2$\begingroup$ `Since $p_1$ is a prime factor of $s$' is the wrong reason. $\endgroup$ Commented Jul 30, 2021 at 6:58
-
$\begingroup$ @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? $\endgroup$ Commented Mar 16 at 4:35
-
$\begingroup$ @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$. $\endgroup$ Commented Mar 16 at 7:26