The fundamental theorem of arithmetic is made of two parts:
- The existence part:
There exist primes
such that for any natural number $j$, we can write $j$ as a product of prime numbers.
- The uniqueness part:
That we can write any natural number $j$ as a unique product of primes.
For the purpose of this post we shall concentrate only on the existence part. From wikipedia, we learn that the existence part of the FTA can be proven via mathematical induction:
We need to show that every integer greater than 1 is a product of primes. By induction: assume it is true for all numbers between 1 and n. If n is prime, there is nothing more to prove (a prime is a trivial product of primes, a "product" with only one factor). Otherwise, there are integers a and b, where n = ab and 1 < a ≤ b < n. By the induction hypothesis, a = $p_1p_2…p_j$ and b = $q_1q_2…q_k$ are products of primes. But then n = ab = $p_1p_2…p_jq_1q_2…q_k$ is a product of primes.
But I'm not very satisfied with this proof, it seems to be very non intuitive. Can someone show me a proof of the FTA that doesn't require the use of mathematical induction and is intuitive?
I mean why intuitively would numbers who can't be factorized be the building blocks of all other numbers via multiplication? Is there any fundamental reason?
Thanks in advance.
Best Answer
You can argue it by contradiction, using the well-ordering axiom, which is equivalent to induction but feels rather different in a proof. It works like this:
Suppose there exists some natural number that is not a product of primes. Let $S$ be the set of all such numbers. There is a least element in $S$; call it $n$. We know that $n$ cannot be prime, or it would not be in $S$. Therefore, it can be written as a product of two numbers smaller than itself: $n=ab$, $1<a,b<n$. However, since $n$ is the smallest number in $S$, we know that $a$ and $b$ are not in $S$. Therefore, they can be written as the product of primes, but then so can $n$. This is our contradiction.
Does that make more sense?