Intuitive understanding of the uniqueness of the Fundamental Theorem of Arithmetic.
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.
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.
The text A Classical Introduction to Modern Number Theory by Ireland and Rosen discusses unique factorization in Chapter 1. The way they handle unique factorization in $\mathbb{Z}$ is by defining an operator $\operatorname{ord}_pn$ as the number of times a prime $p$ divides $n$ (i.e., $\operatorname{ord}_pn=k$ when $p^kq=n$ and $p\nmid q$). This operator has the nice property that $\operatorname{ord}_p(ab)=\operatorname{ord}_p(a)+\operatorname{ord}_p(b)$, which relies on properties of prime numbers (importantly, that whenever $p\mid ab$ then either $p\mid a$ or $p\mid b$), which follow from the Bezout identity. Of course, factorization into prime numbers at all is a consequence of $\left|a\right|<\left|ab\right|$. But then uniqueness follows from applying $\operatorname{ord}_p$ to both sides of the factorization for each prime which appears, since $n=\prod_qq^{a_q}$ becomes $\operatorname{ord}_p(n)=\sum_qa_q\operatorname{ord}_p(q)$, and when $p\neq q$, we have $\operatorname{ord}_p(q)=0$.
I like this way of going about it, because it makes it more clear that the prime numbers form a kind of basis of the integers under multiplication. You are even given a nice set of homomorphisms which can be used to project onto this basis!
Rereading your question, I realize I seem to have missed that you were concerned about the fact that a prime cannot be factored into (smaller) primes. This is something that is just by definition: a prime (also "irreducible element") is an element which has no divisors. That every factorization stops with a finite list of factors follows from the well-ordering of the natural numbers ("every subset of the natural numbers has a least element"), or by "strong induction." Assume there is a prime factorization for every number less than $n$, then construct a factorization for $n$ itself by either noting it is prime already, or writing it as $n=ab$, and since $a<n$ and $b<n$, both of these have factorizations, and so $n$ has one, too.
Another thing you mention is the Bezout identity. Here is an attempt at communicating my intuition. Imagine you have two numbers $x$ and $y$, and take all multiples of these two numbers and arrange them along the number line, the multiples of $x$ marked with a red dot and the multiples of $y$ marked with a blue dot. The greatest common divisor $d$ is a number such that every number with either a red or blue dot is a multiple of it. That is, if you marked all multiples of the GCD with a green dot, then wherever there is a red or blue dot, there is also a green dot, and there aren't more green dots than needed for this to happen. Notice that the blue, red, and green dots are all evenly spaced. First, let us ask "what is division?" Essentially, dividing a number by $x$ is about finding one of the closest red dots to that number, and a number is evenly divided by $x$ if that number has a red dot next to it. Back to the GCD: if you can locate where the red and blue dots come closest without overlapping, that distance is the GCD. If the number with the red dot is $ax$ and the number with the blue dot is $by$, then $|ax-by|=d$, the Bezout identity.
Your claim that the fact a prime cannot be factored should imply unique factorization is not true. As I mentioned earlier, the definition of a prime is that it cannot be factored into smaller numbers, but here are other number systems where this is not enough to give unique factorizations. For instance, if we throw $\sqrt{-5}$ into the integers, then $2$, $3$, $1+\sqrt{-5}$, and $1-\sqrt{-5}$ are all prime, but $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$, so unique factorization does not hold.
Here are my two cents on this question. AnatolyVorobey has pointed out the ideas of the second proof with a better explanation than the one given in Wikipedia (just a remark, that proof was discovered independently by Lindemann).
First, I will focus on the usual proof of FTA. I want to remark that the chain that you wrote: "Euclid's division $\implies$ Bézout's lemma $\implies$ Euclid's lemma" is not necessary. We only need Euclid's division and the algorithm that carries his name, i.e, the euclidean algorithm. In other words, we only need the existence of GCDs for every pair of positive integers.
To prove this we need the identity: $\gcd(ac,bc)=c\gcd(a,b)$. The above result is very well-known so I'll just skip the proof. Now, going to the main result we seek: given a prime number $p$ and two positive integers $a,b$ such that $p\mid ab$, we have to prove that $p\mid a$ or $p\mid b$.
If $p\mid a$ we're done. Otherwise $p\not\mid a$, and this is the key idea here: the fact that $p\not\mid a$ implies $\gcd(p,a)=1$ and this is true because the only factors of $p$ are $1$ and $p$ itself. On the other hand, clearly $p\mid pb$ and by hypothesis $p\mid ab$, hence by the above identity and the universal definition of $\gcd$ (known also as Euclid's porism) we have $$p\mid \gcd(pb,ab)=b\gcd(p,a)=b.$$ Hence, we deduce that $p\mid b$.
Nowhere we've used Bézout's identity. So as you can see we only need the existence of GCDs and one identity to prove Euclid's lemma.
But, there is something else to say. Probably the two proofs you indicated are the most known (being the first one the most known in general), however there is another less known proof of FTA related to the uniqueness part. This third proof doesn't use Euclid's lemma, instead uses a lemma known as "Four number lemma" (also known as Euler's vierzahlensatz, but actually known since the time of Euclid).
More exactly, this third proof uses a generalized version of the four number lemma. First, let's see what this lemma says:
Given four positive numbers $a,b,c,d$ such that $ab=cd$, then there are four positive numbers $m,n,p,q$ such that $$a=mn,\; b=pq,\; c=mp,\; d=nq.$$
In other words, we can refine $a,b,c,d$ to another four numbers such that $a:c=d:b$. Now, the generalized version of the above lemma says this:
Given positive integers $p_1,\ldots, p_m, q_1\ldots, q_n$ such that $p_1\cdots p_m=q_1\cdots q_m$, then there are positive integers $x_{ij}$ ($1\le i\le m$, $1\le j\le n$) such that $$p_i=\prod_{j=1}^n x_{ij},\;\; q_j=\prod_{i=1}^m x_{ij}.$$
The generalized four number lemma can be proved by using double induction. I won't proved here because is somehow tedious to prove but you can check the first reference for the proof. What I'll proof is the four number lemma.
Proof of the four number lemma: We'll prove it by strong induction on $a$. If $a=1$ we have $b=cd$, so we can take the numbers $m=n=1$, $p=c$ and $q=d$. Now, let's suppose the lemma is true for every positive integers less than $a$. By Euclid's division applied to $d$ and $b$ we can find positive integers $q,r$ such that $d=bq+r$. Replacing we get $$ab=c(bq+r)=bcq+cr$$ $$\implies b(a-cq)=cr.$$
Now, since $a-cq<a$ by the hypothesis of induction we cand find positive integers $x,y,u,v$ such that $b=xy$, $a-cq=uv$, $c=xu$ and $r=yv$. Then $a=cq+uv=xuq+uv=u(xq+v)$ and let's put $xq+v=w$. Therefore we find that $a=uw$, $b=xy$, $c=ux$ and $$d=bq+r=xyq+yv=(xq+v)y=wy.\;\;\; \blacksquare$$
Finally let's give the promise third proof of the uniqueness part of FTA. Let's suppose that we can write a positive integer $a$ as a product of primes in two ways: $$a=p_1\cdots p_m=q_1\cdots q_n.$$
Then by the generalized four number lemma we can find positive integers $x_{ij}$ ($1\le i\le m$, $1\le j\le n$) such that $$p_i=\prod_{j=1}^n x_{ij},\;\; q_j=\prod_{i=1}^m x_{ij}.$$
Now, as the $p_i$'s are primes, there is exactly one $x_{ij}$ that's equal to $p_i$ and the other factors are $1$'s, so there are exactly $m$ factors greater than $1$. Analogously, seeing the factors of the $q_j$'s we deduce that there are $n$ factors greater than $1$. Thus $m=n$ and the terms $x_{ij}$ that are greater than $1$ give a correspondence (after rearranging if necessary) between the $p_i$'s and the $q_i$'s given by $$p_i=x_{ij}=q_i.$$
Hence, we have proved the uniqueness part of FTA.
Comments: i) I think the four number lemma is a very intuitive result because it tells you that two factorizations of a positive integer have a common refinement and this result is, as we have seen, very close to the uniqueness part of FTA.
ii) In the first reference below there is a nice geometric proof of the four number lemma.
iii) The four number lemma can be used to prove a stronger result than Euclid's lemma, namely: if $a\mid bc$ and $\gcd(a,b)=1$, then $a\mid c$. Again, see the first reference below.
iv) It turns out there is another way to prove the uniqueness part of FTA using the four number lemma. Namely, we don't need the generalized version of the lemma above, just only the classical lemma itself. The idea is to suppose there are numbers with non-unique factorization so by the well ordering principle there is the smallest number with non-unique factorization, let's say $a$. Thus we can write $a=px=qy$ with distinct primes $p$ and $q$ such that wlog $p<q$. The idea is then to use the four number lemma in order to show that $x$ and $y$ have unique factorization, and hence $a$ too has unique factorization, arriving to a contradiction.
References:
1) Paul Erdös, János Suranyi, Topics in the Theory of Numbers, Springer, 2003.
2) Steven Weintraub, Factorization: Unique and Otherwise, AK Peters, 2008.
3) David Pengelley, Fred Richman, Did Euclid Need the Euclidean Algorithm to Prove Unique Factorization?, The American Mathematical Monthly, 113(3), 196-205. Available online here.
4) Lászlo Kalmar, On the Fundamental Theorem of Arithmetic, Matematikai és Fizikai Lapok, (43) 1936, 27-45. (In Hungarian).
5) W. G. Dubuque, https://math.stackexchange.com/a/322046