# A Complete Proof of the Fundamental Theorem of Arithmetic?

UPDATE

My second (and final) 'proof correction attempt' answer has been completed. It 'takes a stab' at addressing John Hughes's answer/criticisms of the proof given in this question and his comment on my first 'proof correction attempt' answer.

Note: I changed the title from

$$\quad$$ A Simple Proof of the FTA using only elementary theory?

to the one that now appears.

END UPDATE

By elementary theory, we mean avoiding as much number theory as possible. The exposition below is sketchy but the necessary details involve 'primitive' constructions, like using the fact that the natural numbers come with a well-order.

Let $$n$$ be any integer greater than $$1$$.

Let $$p$$ be any prime factor of $$n$$.

Consider any factorization of $$n$$,

$$\tag 1 n = ab$$

Write both $$a$$ and $$b$$ using their unique $$\text{Base-p}$$ representations.

$$\tag 2 a = a_0 + a_1 p + a_2 p^2 + a_3 p^3 + \dots$$

$$\tag 3 b = b_0 + b_1 p + b_2 p^2 + b_3 p^3 + \dots$$

By the elementary theory found here, the only way $$p$$ can divide the product $$ab$$

$$\quad$$ = rhs of $$\text{(2)}$$ $$\times$$ rhs of $$\text{(3)}$$

is if $$a_0 = 0$$ or $$b_0 = 0$$.

Summarizing,

Proposition 1: Let $$n$$ be any integer with a prime factor $$p$$ and let $$n = ab$$.
Then $$p$$ must divide either $$a$$ or $$b$$.

Continuing, we know that if $$n \gt 1$$ the first integer greater than $$1$$ that divides into $$n$$, $$\gamma(n)$$, is a prime, the minimal prime factor.

Any integer $$n$$ can be factored into prime numbers, but an easy argument using proposition 1 guarantees that $$\gamma(n)$$ must appear in any factorization.

Theorem 2: Any two factorizations of an integer $$n \gt 1$$ into primes must agree.
(in the sense elaborated in any accepted exposition of FTA/uniqueness),
Proof
Let

$$\tag 4 n = \gamma(n)\, p_1 p_2 \dots$$

$$\tag 5 n = \gamma(n)\, q_1 q_2 \dots$$

be any two factorizations. We can factor out $$\gamma(n)$$ in both representations. Now each remaining representation is either empty or contains more factors. If necessary, then, repeat, factoring out

$$\gamma(\frac{n}{\gamma(n)})$$

In this way all factors are matched up and uniqueness is guaranteed. $$\quad \blacksquare$$

Is this argument valid?

Note: The question has the proof verification tag.

• Here it seems you are attempting to rediscover the common proof of the uniqueness of prime factorizations using Euclid's Lemma (a prime divides a product $\iff$ it divides some factor), But that proof has been given here many times, e.g. the theorem here.. So it's not clear why you don't simply refer to the well-known common proofs. – Bill Dubuque May 22 at 18:12
• @BillDubuque Still, the exposition is a bit different... I just voted to close my own question! – CopyPasteIt May 22 at 18:31
• If you can elaborate more on what you are attempting to do then perhaps I can be or more help. But I'm still puzzled about your goals. – Bill Dubuque May 22 at 18:38
• @BillDubuque Thanks. My goals might be more of moving target. I noticed so many questions on FTA concerning intuition, and it would be nice if some new approach and/or exposition could take care of that. Certainly coming up with a new approach is not easy, considering the amount of analysis that has gone into this over the millennia. – CopyPasteIt May 22 at 18:45
• There are many ways to organize such proofs. But there is usually little interest in enumerating all the possibilities since number theorists are usually interested in employing concepts that generalize to other number rings so are more to the essence of the matter. – Bill Dubuque May 23 at 14:14

Well, I didn't bother reading the linked stuff, but there are certainly omissions here.

For instance, talking about "the first integer greater than $$1$$ that divides into $$n$$" should probably be supported with two facts: the set $$S$$ of integers greater-than-one dividing $$n$$ contains $$n$$, hence is nonempty, hence, by the well-ordering principle, has a least element.

Then you also need to make the point that this least element is indeed prime.

The claim that "any integer can be factored into primes" again requires some proof (and again, the well-ordering principle might want to be involved). You probably want to talk about positive integers here, too9.

For your claim that any two factorizations "agree," I think you need to define "agreement." For instance, 2 is the smallest prime factor of 12, but

12 = 2 * 2 * 3
12 = 3 * 2 * 2


don't "agree", at least not term-by-term. So there's more work to do here.

If you're going to give an elementary proof, you need to actually prove everything.

One example of something that needs proving: that a (positive) integer has a unique base-$$p$$ representation. That claim might well depend on FTA (although I doubt it, offhand). Anyhow, without a citation to a proof, I have to regard your very starting point as suspect.

In short: you've got an OK idea here, but not something I'd accept as an elementary proof.

• Thank you - I made some changes. – CopyPasteIt May 22 at 16:31
• to show base-b representations are unique, for any $b \gt 1$, you can use logic and algebra. – CopyPasteIt May 22 at 16:45
• To show FTA, you can use logic and algebra, too. The question is "does that logic rely on FTA?" Without knowing that, you don't know whether your overall proof is circular. Also: changing the question after you've gotten a detailed answer is kind of rude -- it makes the answer/answerer look stupid. The right thing to do is to ask a new question. (By the way, the changes you made really represent no improvement to my way of thinking. The claim "there has to be a match up" is vague, and all you can really claim is that for some $i$, you know that $\gamma(n)$ divides $p_i$.) – John Hughes May 22 at 21:50
• I am going to roll back the question to the original and post an updated answer. – CopyPasteIt May 22 at 22:02
• Just to clarify - Base-b representations have nothing to do with FTA. But I reworked the proof so it is now a moot point. – CopyPasteIt May 22 at 22:34

I made some changes to the proof based on input from John Hughes.

Let $$n$$ be any integer greater than $$1$$.

Let $$p$$ be any prime factor of $$n$$.

Consider any factorization of $$n$$,

$$\tag 1 n = ab$$

Take the remainder residue $$a_0$$ of $$a$$ and the remainder residue $$b_0$$ of $$b$$ after using Euclidean division with divisor $$p$$. By the elementary theory found here, the only way $$p$$ can divide the product $$ab$$ is if $$a_0 = 0$$ or $$b_0 = 0$$.

Summarizing,

Proposition 1: Let $$n$$ be any integer with a prime factor $$p$$ and let $$n = ab$$.
Then $$p$$ must divide either $$a$$ or $$b$$.

Continuing, we know that if $$n \gt 1$$ the first integer greater than $$1$$ that divides into $$n$$, $$\gamma(n)$$, is a prime, the minimal prime factor.

Any integer $$n$$ can be factored into prime numbers, but an easy argument using proposition 1 guarantees that $$\gamma(n)$$ must appear in any factorization:

Let $$n = p_1 p_2 p_3 \dots p_k$$ be any factorization into primes. If $$\gamma(n) = p_1$$ we are done. Otherwise, applying proposition 1 to

$$\quad (p_1) \times ( p_2 p_3 \dots p_k)$$

we deduce that $$\gamma(n) \mid p_2 p_3 \dots p_k$$.

Again, if If $$\gamma(n) = p_2$$, we are done. Otherwise, applying proposition 1 to

$$\quad (p_2) \times ( p_3 p_4 \dots p_k)$$

we deduce that $$\gamma(n) \mid p_3 p_4 \dots p_k$$.

Continuing, you might have to keep dropping factors until you get to the 'end',

$$\quad \gamma(n) \mid [(p_{k-1}) \times (p_k)]$$

The only way a prime can divide into another prime is if they are equal, so if you go this far then $$\gamma(n) = p_{k-1}$$ or $$\gamma(n) = p_{k}$$.

So, no matter what, $$\gamma(n) = p_i$$ for some $$1 \le i \le k$$.

Theorem 2: Any two factorizations of an integer $$n \gt 1$$ into primes must agree.
(in the sense elaborated in any accepted exposition of FTA/uniqueness)
Proof
Let

$$\tag 2 n = \gamma(n)\, p_1 p_2 \dots$$

$$\tag 3 n = \gamma(n)\, q_1 q_2 \dots$$

be any two factorizations. We can factor out $$\gamma(n)$$ in both representations. Now either both of the factor-reduced representation are empty or both contain more factors. If necessary, then, repeat, factoring out

$$\gamma(\frac{n}{\gamma(n)})$$

from the two reduced expressions.

And continue until both reduced/factored quantities are empty (representing $$1$$).

In this way all factors are matched up and uniqueness is guaranteed.

More formally, we can simultaneously construct two finite sequences of integers using recursion:

Set $$a_0 = n$$ and $$p_0 = 1$$.

For $$k \ge 1$$ set

$$a_k = \frac{a_{k-1}}{\gamma(a_{k-1})}$$

and

$$p_k = \gamma(a_{k-1})$$

when $$a_{k-1} > 1$$. When $$a_{k-1} = 1$$ set $$a_k = 1$$ and $$g_k = 1$$.

The prime factors are the numbers $$p_k$$ with $$p_k \gt 1$$. $$\quad \blacksquare$$

• This "proof" fails to restrict to positive integers in a few places where it should, omits the hard work of characterizing uniqueness, has a hidden well-ordering assertion, two hidden inductions, and a hidden lemma about prime factors of primes. It. It's not "simpler" than the usual proofs, it's incomplete (which allows it to be shorter). – John Hughes May 22 at 23:06

Proof Objective: Since $$\Bbb N$$ is well-ordered, we know that the minimum prime factor of any number greater than $$1$$ is uniquely defined. The proof strategy here was to use that as a 'hook' into the proof and avoid using Euclid's lemma. But we did not really sidestep the lemma, since the construction of lemma 5 in the next section is such a 'close relative' to Euclid's lemma.

However, the more general 'no such thing as a smaller prime appearing in two different factorizations' logic can be found in Zermelo's and others proof (see this); they don't use any advanced number theory or lemmas.

We will prove the fundamental theorem of arithmetic working in the natural numbers,

$$\Bbb N = \{0,1,2,3,\dots\}$$

We refer to the non-zero natural numbers as the counting numbers. If $$a$$ and $$b$$ are two distinct counting numbers then the difference, another counting number, is defined as the $$u$$ making the following a true statement,

$$a + u =b \; \text{ XOR } \; b + u =a$$

Let $$n \gt 1$$ and $$0 \le r \lt n$$. We employ the following notational definitions,

$$\tag 1 n \Bbb N \oplus r = \{nq + r \, | \, q \in \Bbb N \}$$

The statement of the Euclidean division theorem for natural numbers states that these sets form a partition of $$\Bbb N$$. Moreover, we can define a mapping that sends any integer to its remainder when dividing by $$n$$,

$$\text{mod}_n: \Bbb N \to \{0,1,2,\dots,n-1\}$$

So if $$a = nq + r$$ with $$r \lt n$$, then $$\text{mod}_n(a) = r$$, also written as $$\rm\ a\ mod\ n$$.

Of course the corresponding partition of the surjective mapping $$\text{mod}_n$$ is given precisely by the sets of the form given in $$\text{(1)}$$. Also, observe that if $$a,a^{'} \in n \Bbb N \oplus r_a\;$$ and $$a \lt a^{'}$$ then $$a^{'}$$ has the form $$a + nk$$.

Proposition 1: If $$a,a^{'} \in n \Bbb N \oplus r_a\;$$ then $$\rm\ (a + b)\ mod\ n = \rm\ (a^{'} + b)\ mod\ n$$.
Proof
Case 1: $$a^{'} = a + ns$$ with $$s \ge 0$$:
Write $$a + b = nt + r$$. Then $$a^{'} + b = a + ns + b = n(s+t) + r$$.
Case 2: $$a = a^{'} + ns$$ with $$s \gt 0$$:
Write $$a^{'} + b = nt + r$$. Then $$a + b = a^{'} + ns + b = n(s+t) + r$$.
$$\blacksquare$$

Proposition 2: If $$a,a^{'} \in n \Bbb N \oplus r_a\;$$ then $$\rm\ (a b)\ mod\ n = \rm\ (a^{'} b)\ mod\ n$$.
Proof
Case 1: $$a^{'} = a + ns$$ with $$s \ge 0$$:
Write $$a b = nt + r$$. Then $$a^{'} b = ab + nsb = n(t + sb) + r$$.
Case 2: $$a = a^{'} + ns$$ with $$s \gt 0$$:
Write $$a^{'} b = nt + r$$. Then $$ab = a^{'}b + nsb = n(t + sb) + r$$.
$$\blacksquare$$

The subset $$n \Bbb N \oplus 0 \setminus \{0\}$$ of counting numbers has the property that the difference of any two numbers from there belong to the set and also the minimum divides all of these numbers. This can be generalized,

Lemma 3: Let $$S$$ be a nonempty set of counting numbers closed with respect to taking the difference of two distinct numbers from $$S$$. Then the least $$\rm\:\ell\in S\,$$ divides every element of $$\,\rm S.$$

For a proof of lemma 3, see this from Bill Dubuque on a Euclid's lemma posting.

Lemma 4: Suppose $$n\mid a\,$$ and $$n \mid c$$ where $$c = a + b$$. Then if must follow that $$n \mid b$$.
Proof
By proposition 3, $$0 = \rm\ (a + b)\ mod\ n = \rm\ (0 + b)\ mod\ n= \rm\ (b)\ mod\ n$$.$$\quad \blacksquare$$

Lemma 5: Let $$p$$ be a prime and $$(a_i)_{\, 1 \le i \le k}$$ be a finite sequence of counting numbers with the property that for each $$i$$, $$\;a_i \lt p$$. Then the product $$\prod _{i=1}^{k}a_{i}$$ is not divisible by $$p$$.
Proof
We prove it first for just a '$$k = 2$$' family, $$a$$ and $$b$$.
To get a contradiction, assume than $$p \mid a b$$.
Let $$S = \{n \in \Bbb N \, | \, p \mid nb \}$$. Then $$p \in S$$ and $$a \in S$$. Also, if $$n, n^{'} \in S$$ with $$n^{'} = n + j$$, we can write

$$\quad pq = nb \, \text {and } \, pq^{'} = n^{'}b = (n+j)b = nb +jb$$

and by lemma 4, $$j \in S$$. So, $$S$$ is closed under subtraction and lemma 3 applies.

Let $$d = \text{min(}S\text{)}$$. By lemma 3, $$d \mid p$$, so $$d = 1$$ or $$d = p$$.

If $$d = 1$$, since $$d \in S$$, it must follow that $$p \mid (1 \times b)$$, which is absurd since $$b \lt p$$.

By lemma 3, $$d \mid a$$, so if $$d = p$$ then $$p \mid a$$, which is absurd since $$a \lt p$$.

The proof can be completed by applying induction on the number of terms and using proposition 2.
$$\blacksquare$$

Continuing, we know that if $$p \gt 1$$ is the first number greater than $$1$$ that divides into a number $$n \gt 1$$, then it is prime; denote it by $$\gamma(n)$$. Now if we divide out by $$\gamma(n)$$ what will be left is a smaller number that we can go to work on again. In this way we can demonstrate the existence of prime factorizations.

Lemma 6: Let $$p$$ be a prime and $$(p_i)_{\, 1 \le i \le k}$$ a finite sequence of prime numbers such that $$p \mid \prod _{i=1}^{k}p_{i}$$ Then there exists an index $$i_0$$ such that $$p = p_{i_0}$$.
Proof
By dividing each term of the sequence by $$p$$ we get $$k$$ remainders. If none of them are zero, proposition 2 and lemma 5 would make it impossible for $$p$$ to divide into the product. So for at least one index $$p_{i_0}$$ the remainder is $$0$$ and $$pq = p_{i_0}$$, which implies $$p = p_{i_0}$$. $$\quad \blacksquare$$

When we factor a counting number $$n$$ into primes we can always put the factorization into a standard form, by representing the factors in a family $$(p_i)_{\, 1 \le i \le k}$$ and insisting that the term are non-decreasing.

Theorem 7: Any two standard factorizations of a counting number $$n$$ are equal,
i.e. the sequence/function $$(p_i)$$ is equal to $$(q_i)$$.
Proof
Let there be given two standard factorizations of $$n$$,

$$n = \prod _{i=1}^{j}p_{i}$$

$$n = \prod _{i=1}^{k}q_{i}$$

By lemma 6 and the fact that $$p_1 \le p_i$$ for $$1 \le i \le j$$ and $$q_1 \le q_i$$ for $$1 \le i \le k$$, $$\;p_1 = \gamma(n)$$ and $$q_1 = \gamma(n)$$. But then either $$k = j = 1$$ or both of the constants $$k$$ and $$j$$ have to be greater than or equal to $$2$$. If $$j = k = 1$$, $$n$$ is a prime and we are done. Otherwise, we can 'check off' the first term and are left with

$$\frac{n}{\gamma(n)} = \prod _{i=2}^{j}p_{i}$$

$$\frac{n}{\gamma(n)} = \prod _{i=2}^{k}q_{i}$$

and you repeat the 'accounting process' to show that $$p_2 = q_2$$.

When the process ends the corresponding terms of each family will be matched up, subscript to subscript. $$\quad \blacksquare$$

• This might be premature, but all I can think of now is the one liner $\quad$"I see that it's another one of your well-calculated plans that went to pot." $\quad$ The Honeymooners: youtube.com/watch?v=gWQUwqoPWlk&t=22m54s – CopyPasteIt May 28 at 13:45