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.