Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic

Mathematicians often use "number" to refer to the positive integers {1,2,3,...} so we'll do the same.

Let's pick a number n at random and ask a very simple question. Is it possible to find two other numbers which when multiplied together give n? In other words, can we find two numbers, a and b such that..


At first glance it seems like this should be true for any n. In fact, some numbers can be broken down like this in many ways, for example..


But it's not true for any n. There are some numbers that can never be broken down into a product of two other numbers. There are some numbers for which n=a*b is never true. These numbers are called prime numbers.

Prime numbers play an important role in mathematics, probably because of this fundamental fact..

Any number bigger than 2 can be written as a product of prime numbers. This is called The Fundamental Theorem of Arithmetic or the Prime Factorization Theorem.

So we can think of prime numbers as the "building blocks" from which all numbers are made. This is an important result in mathematics, but you don't need to be a mathematician to prove it. The proof is easy. Let's do it..

Pick any number n and ask if it can be broken down into the product of two other numbers a and b. If it cannot then n is prime and we're done. If it can then break it down..


Now just repeat. Ask the same question for a and then ask the same question for b. And keep going. At some point this process must stop, because if it never stopped we would wind up with..

n=1*1*...*1=1 which is ridiculous.

So it must stop when n is written as a product of several numbers which cannot be broken down any more. But this is just the definition of a prime number. So it stops when n is written as a product of primes. That was easy!

Here are the first 10 prime numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

How many prime numbers are there in total? They never stop, there's an infinite amount. Is there a formula that predicts the next prime in the sequence? No, at least not one that any mathematician has discovered so far. Primes are mysterious numbers that seem to elude any type of prediction. They have driven mathematicians to distraction for centuries!

So any number can be written as a product of primes. Let's try one..


Which just illustrates that in the product of primes a prime may be repeated.

Interested in the proof that there are an infinite number of primes? Here it is..

Assume the statement is not true. Therefore there must be a finite number of primes, say m of them, and we can write them as..


Now we multiply all our primes together. Let's call the result n..


But as we showed above, every integer can be written as a product of primes. So this must be true for n+1. Which means n+1 must have at least one of our primes as a divisor, let's call it pj. So pj divides n+1 and it obviously divides n. That means it must divide (n+1)-n=1 which is clearly a contradiction. In fact it's absurd!

So assuming the original statement was not true led to a contradiction, so the original statement must be true. In other words we've proved it. This method of proof is called "proof by contradiction" and is a popular technique in mathematics.

Content written and posted by Ken Abbott