Fundamental Theorem of Arithmetic - Is my proof right?

Question

My goal was to prove the Fundamental Theorem of Arithmetic without using Euclid's Lemma. There are some proofs online but I haven't found one that uses this idea, so I want to make sure it's right.

Please make me aware of any mistakes, I've only be writing proofs for a semester so you would be helping me.

I have already proven, and will be using the fact that the smallest divisor of any integer $\neq$ 1 is prime.

Lemma: The smallest divisor of some number is unique. If it were not, and there were 2 distinct smallest divisors $p,q~,~p\neq q$, we have $\lvert p\rvert\neq\lvert q \rvert$. One of them is smaller than the other so one of them is not the smallest divisor.

Proof: Every prime number has a unique prime factorization (itself). Begin with the smallest composite number 4, the prime factorization of 4 is uniquely $2\cdot2$. Now suppose that every composite number up to but not including $n$ has a unique prime factorization. $n$ has a unique smallest divisor, which is prime, call it $p$. We can uniquely write $n$ as $p\cdot t$. If $t$ is prime then we have a unique prime factorization for $n$. If $t$ is composite, because it is less than $n$, $t$ has a unique prime factorization, and therefore so does $n$.

Applying this reasoning inductively, every composite number has a unique prime factorization. Every prime number also has a unique prime factorization, and so every number has a unique prime factorization.

Answer 1

I don't think your argument establishes what you want.

Let's take for granted that your Lemma is modified so that it shows that every positive integer $n\gt 1$ has a unique smallest divisor $p\gt 1$ (and that this is prime).

Now, you take $n$, and you let $p$ be its smallest divisor $p\gt 1$, and you write $n=pt$, and then you factor $t$. Okay as far as it goes.

But here's the problem: you do not prove that any factorization of $n$ into primes will include $p$ among the factors. How do we know there isn't some other way of factoring $n$ that does not involve $p$, and with all factors greater than $p$? Sure, the smallest divisor of $100$ greater than $1$ is $2$, but maybe there is a way to factor $100$ that doesn't involve $2$ at all?

This happens in other settings; for example, if you consider numbers of the form $a+b\sqrt{-5}$ with $a,b$ integers, and you define the size of a number $a+b\sqrt{-5}$ to be $a^2+5b^2$, then $2$ has the smallest size among all divisors of $6$ (that are not $1$ or $-1$), but in addition to being able to write $6$ as $6=2\times 3$, you can also write it $6=(1+\sqrt{-5})(1-\sqrt{-5})$, with $1\pm \sqrt{-5}$ both having size $6$, while $2$ has size $4$.

What goes wrong here is precisely the lack of the analogue of Euclid's Lemma. I doubt you'll be able to prove the result without having something that is equivalent to Euclid's Lemma.

(In addition, your argument has another small flaw, which is that you do not consider the case in which $t=1$; that is, when $n$ is prime. This is easy to fix, of course. And once you do, note that you do not need to consider the cases of $t$ prime and composite separately when $n$ is not itself prime...)

Answer 2

You continually extract the least factor $> 1$ to get one "least" prime factorization of $\,n.\,$ That the steps of the algorithm are unique does not imply that the prime factorization is unique, e.g. in the Hilbert naturals $\,\Bbb H =1+4\Bbb N\,$ your algorithm finds the "least" prime factorization $441 = 9\cdot 49,\,$ but there is also another prime factorization $\,441 = 21\cdot 21$.

For more on such uniqueness misinferences see KCd's question unique steps leading to a non-unique answer on MathEd.SE. There I give an analogous example: factoring out the linear factors of a polynomial $\!\bmod n\,$ by successively testing the possible roots $\,x\equiv 0,1,\ldots m\!-\!1.\,$ Applied to $\,x^2-1\pmod{\!8}\,$ we find the least root $\,x\equiv 1,\,$ yielding the "least" factorization $\,(x\!-\!1)(x\!-\!7).\,$ But there is also another factorization $\,(x\!-\!3)(x\!-\!5).$

Your argument proves existence of prime factorizations, but not uniqueness. The most common way to prove uniqueness is by EL = Euclid's Lemma: if a prime divides a product then it divides some factor. By EL it does not matter which order we pull out prime factors since if a prime $\,p\,$ occurs in one factorization $A$ then it occurs in any other factorization $B;\,$ so deleting $\,p\,$ from both must yield the same prime factorization $C$ (by induction), thus $A$ and $B$ are the same - obtained by appending $\,p\,$ to the factorization $C$.

Notice that Euclid's Lemma fails in both of the above examples: we have $\,21\cdot 21 = 9\cdot 49\,$ but the Hilbert-prime $21$ divides neither $9$ nor $49$, and $\!\bmod 8\!:\ (x\!-\!1)(x\!-\!7)\equiv (x\!-\!3)(x\!-\!5)\,$ but $x\!-\!1$ divides neither $x\!-\!3$ nor $x\!-\!5\,$ (here is more on nonunique factorization of modular polynomials).

Answer 3

Consider the following argument:

Statement: Every integer $n>1$ can be uniquely (up to an ordering) represented as a sum of twos and threes.

"Proof": If $n$ is $2$ or $3$, then it is uniquely represented as itself. Now suppose that $n\geq 4$, and every integer from $2$ up to but not including $n$ has a unique representation as a sum of $2$s and $3$s. $n$ has a unique smallest number $p\in\{2,3\}$ such that $n$ can be represented as $p+t$, where $t$ is an integer $>1$ (it's easy to see that this $p$ is $2$). This $t$ is also unique (for this $p$). Since $2\leq t<n$, $t$ has a unique representation as a sum of $2$s and $3$s, and therefore so does $n$.

And yet, $6$ can be represented either as $2+2+2$ or as $3+3$. The problem is that while there is indeed the unique smallest $p\in\{2,3\}$ which can be used in a representation of $n$ as a sum of $2$s and $3$s, it doesn't mean that it has to be used in every such representation. Similarly, in your case, while it's true that the there is the unique smallest prime $p$ which can be used in a prime decomposition of $n$, it doesn't follow that it has to be used in every such prime decomposition.

Answer 4

We can uniquely write $n$ as $p\cdot t$.

This is an ambiguous sentence, and your proof relies on the ambiguity to jump to the conclusion.

Consider the two following sentences instead:

(1) There is a unique $t$ such that $n = p \cdot t$.

(2) The only way to factor $n$ is by writing it as $n = p \cdot t$ for some $t$.

Sentence (1) is true, and it leads to a prime factorisation of $n$, but it doesn't prove that this factorisation is the unique factorisation of $n$.

Sentence (2) remains to be proven. Just because $n$ is divisible by $p$ doesn't imply that the only way to factor $n$ is by writing is as $n = p \cdot t$. Of course, that turns out to be true in retrospect, thanks to the fundamental theorem of arithmetic, but you need to prove it.