Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.

Question

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.

Answer 1

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?

Answer 2

I think this is what is essentially same to what the proof says, but:

Given a natural number $n$, repeat the procedure below:

i) check if any natural number less than n (but not equal to 1) divides n

if no number divides n: n is prime by definition. Otherwise, we have $a$ and $b$ such that $n=ab$

ii) now repeat i) with two natural numbers $a$ and $b$.

This must terminate at some point, since n is finite, and when $n$ is expressed as product of 'irreducible' primes. We then would have a prime factorisation of $n$.

Answer 3

I'll try to answer your last question: "Intuitively why would numbers who can't be factorized be the building blocks of all other numbers via multiplication?", and in doing so I'll offer some ideas behind the proof.

Let's start with an arbitrary natural number $n$. If $n$ is prime, then we can't break it down any further. Otherwise $n=ab$ for some $a,b \in \mathbb N$. The "building blocks" of arithmetic will be the numbers that can't be broken down by factorisation - i.e. the numbers that have no non-trivial factors.

We can continue breaking down $a$ and $b$, and since $n$ is finite, and $a,b<n$, this process must terminate. The broad idea is that factorisation is in some sense the opposite of multiplication - so it makes sense that numbers that can't be factorised further will be the building blocks of those that can.

The uniqueness argument is, however, much less intuitive and relies on the special structure of the natural numbers. For example, if we were only to consider the even numbers, and call "primes" numbers that can't be divided further, then we have $$60 = 6\times 10=2\times 30,$$ but neither $2,30,6$ nor $10$ can be divided further - so factorisation into "primes" is not unique here.

(What's special about the natural numbers is that we can calculate highest common factors - so that if we want to find all the numbers that are divisible by $m$ and $n$ say, this turns out to be all the numbers that are divisible by $\text{hcf}(m,n)$ - but to fully understand this, you may need to study some Ring Theory.)

Answer 4

I would suggest that the existence proof is actually very intuitive, in that it is exactly what you would do in practice to factorise an integer. For example, to factorise $72$ you might very well start with $$72=8\times9$$ and then consider whether the $8$ and $9$ can be factorised any further. If you were systematically factorising all(!) positive integers you would already know the factorisations for $8$ and $9$ and you would simply substitute them into the above product. This is exactly what the existence proof does. Induction is just a way of very carefully writing down this procedure.

Answer 5

Prime numbers are the atoms of divisibility: you cannot divide them any more.

Thus they form a set of building blocks for the natural numbers: any natural number can be built from these atoms.

The building rule for the construction is the reverse of division, i.e. multiplication.

The proof is "proof by destruction" 8^) - it tells you how to split a given number into its atoms.