Basically I am trying to understand why Fundamental Theorem of Arithmetic (FTA) exists, i.e why a natural number cannot be factored primely in two or more different ways.
There are two proofs given on the wikipedia page for the uniqueness,
- Via Euclid's lemma 2. Elementary proof.
The second one, it is a proof by contradiction. The underlying reason behind this proof is a combination of the two facts,
- That there must exist a smallest number which can be uniquely
factorized–kind of presumption of FTA's existence for a finite
number of natural numbers–. - A prime number cannot be factored. (The
contradiction that we get at last is $p_1(k+1)=q_1$ but $q_1$ was
assumed to be prime.)
The first fact makes sense to me as: We can show this for a finite number of natural numbers by brute-force, e.g. we can show that the numbers 1 to 15 can be uniquely factorized by making all the possible combinations of numbers less than 15.
My main problem in this elementary proof is the second fact. It doesn't give me an intuitive satisfaction which it could give if it were not the contradiction achieved but the starting point of our proof. The discoverer of this elementary proof must have it the other way round, i.e without contradiction. He should have used the fact $p_1(k+1)\neq q_1$ to prove the uniqueness of FTA(for natural numbers only). I don't know if he really had but is this possible?
The intrinsic fact (precisely the definition of a prime) that a prime cannot be factored should somehow directly imply the uniqueness of FTA. If there is some direct mathematical proof like that then this would give me a lot of satisfaction.
For a complete understanding of the first proof, I studied Euclid's lemma–which needed Bezout's identity–which further needed the concept of euclidean division. I've read all the stuff carefully but I am still not satisfied with them. I cannot grasp them for some reason, which I don't know.
How a simple Euclid division process can imply the Bezout's identity? That is what is the underlying reason (intuitive)?
In Bezout's identity we see that any number of form $ax+by$ is of the same form as the reminder obtained by dividing $a$ (or $b$) with $ax+by$ and the reminder should be 0. This is the kinda of the underlying reason. But this is not quite satisfactory to me. It's a weird fact! How the discoverer of the proof of Euclid's lemma would know that the fact that $ax+by$'s least value is $\gcd(a,b)$ implies Euclid's lemma? Is there some intuitive way to understand the chain,
Euclid's division $\implies$ Bezout's identity $\implies$ Euclid's lemma.
Or any intuitive way to understand directly why Euclid's lemma exists.
I don't know how to put it in words. I am not grasping all these things. All these mathematical proofs are just a way to justify the truth but they do not provide the answer to "Why is it the way it is?"
Please tell me some exhaustive intuitive explanation of some kind so that I could grasp all this stuff.
Thank you.
Best Answer
Here's a proof of the uniqueness of FTA by induction that is different from the proof you cite from Wikipedia. It is due to Zermelo, and isn't as widely known as the other proofs.
Suppose we already proved uniqueness for all numbers $<n$ and are now proving for $n$. If $n$ is prime, there is nothing to prove. Otherwise let $p$ be the smallest divisor of $n$ that is not 1. Clearly $p$ must be prime, otherwise it would not be the smallest.
We claim that any way to write $n$ as a product of primes must include $p$. If we succeed in proving this, our work is done - why? Because if any two factorisations of $n$ must both include $p$, we can take $p$ out, get a smaller number, invoke uniqueness as the inductive assumption and see that the factorisations are really the same.
Consider any factorisation $n=q_1*q_2*\dots*q_s$. If $q_1=p$, we are done. Otherwise we can form a number $n'=p*q_2\dots*q_s$, where we replaced the first factor $q_1$ by $p$. Because $p$ is the smallest divisor, $n'$ must be smaller than $n$. Note that their difference can be written
$n-n' = (q_1-p)*q_2*\dots*q_s$
We know that $p$ divides this number $n-n'$, because it divides both $n$ and $n'$. And this number is less than $n$, so by inductive assumption it only has one factorisation, in which $p$ must participate. But look at the product above: $p$ does not divide $q_1-p$, so the only way it can participate is by being one of $q_2\dots q_s$, which is what we wanted to prove.