7

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.

Andrés E. Caicedo
  • 79,201
user160987
  • 71
  • The multiplication part has more to do with fact of property of primes. Something is prime any number lower than it can't divide it in other words that it can't be written as product of two lower natural numbers. So if you say n isn't prime you are saying it is product of two numbers lower than it – Kamster Jul 01 '14 at 00:34
  • Also this characteristic that every natural number is product of primes or pirme is very important in number theory. I like to thinks of it as the equivalent importance as a basis is to a vector space, its irreducible building blocks of that study – Kamster Jul 01 '14 at 00:38
  • The proof is just a formal way of saying that you cannot keep factoring a natural number forever. The key property of the natural numbers that is employed in the proof is the fact that if $a \mid n$ and $a \ne n$, then $a < n$. (And also the fact that the set of positive integers less than $n$ is finite.) – Tunococ Jul 01 '14 at 00:41

5 Answers5

16

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?

G Tony Jacobs
  • 31,218
  • I don't understand well your statement: However, since n is the smallest number in S, we know that a and b are not in S... – user160987 Jun 30 '14 at 23:53
  • 1
    Well, we chose $n$ to be the smallest number that cannot be expressed as a product of primes. Since $a$ and $b$ are both smaller than $n$, then they can both be expressed as products of primes. Otherwise, $n$ wouldn't really have been the smallest such number. – G Tony Jacobs Jul 01 '14 at 01:38
  • Nice. You beat me to it. +1 – Rick Decker Jul 01 '14 at 01:43
13

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.

David
  • 82,662
5

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.)

Mathmo123
  • 23,018
  • FTA predates ring theory, so I presume that it can be proven without it. – Taemyr Jul 01 '14 at 07:28
  • 2
    Of course it does/can. But to intuitively understand why the FTA works in the natural numbers, it helps to know why it fails in other places. – Mathmo123 Jul 01 '14 at 09:28
3

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$.

user160738
  • 4,160
  • Makes sense, thanks! – user160987 Jun 30 '14 at 23:51
  • This is essentially the proof that G Tony Jackobs gives. It relies on the well ordering of the natural numbers, not the finitness of n. (Consider trying to make your argument for the reals instead, every real is finite but checking all reals less than a given number is not possible) – Taemyr Jul 01 '14 at 07:32
0

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.

Zane
  • 125