The fundamental theorem of Arithmatic

We begin with Chemistry. There are about 118 basic elements. All other elements are actually combinations of those basic elements. There is an analogy of this fact in number theory. We know the basic rules for combining natural numbers to create new ones are: Addition and Multiplication. For example let us take two numbers 2 and 3. By adding them we can create 5 and by multiplying we have 6. According to our analogy there should be some ‘basic’ numbers which can be combined by addition to create all other natural numbers. Similarly there should be some ‘basic’ numbers which can be combined by multiplication to create all other numbers.

For addition, that number is simply 1. By combining 1 under the rule of addition we can create any other natural number. For example: we can get 12 by adding twelve 1s.

For multiplication, things are quite interesting. Suppose we take 12. How can we make 12 by multiplication? It seems that there are more than one way to do so. Let’s try:
12 = 1 X 12
= 2 X 6
= 3 X 4
= 2 X 6
Now, we try to break 12 into more ‘elementary’ parts. And we see that all of the above ways can be written as, 12 = 2 X 2 X 3. 12 cannot be resolved into any other smaller factors. (By the way, we are excluding 1, because multiplying with 1 doesn’t change anything.)

There are two things to note in above example:
(a) As we have already broken 12 into smallest pieces, the numbers 2 and 3 can never be resolved into any smaller pieces.
(b) No matter how we try to break 12, if we want to find the smallest factors, we always end up getting two 2s and one 3.

So, clearly there are some ‘basic’ natural numbers such that, by combining them by multiplication we can create any other natural number. And these ‘basic’ numbers themselves cannot be created by multiplying other numbers. (This is similar to the fact that the basic elements in chemistry can be combined to create any other elements but the basic elements themselves cannot be created by combining other elements.) These numbers are called Prime numbers.

Thus, we conclude that:
(i) prime numbers are numbers which cannot be resolved into any smaller factors (other than themselves and 1).
(ii) every natural numbers (expect 1) can be factored into a product of primes.
(iii) prime factors of any natural number (except 1) is unique. (For example: 15 = 2 X 5, and there is not another way to multiply primes to create 15)

Every natural numbers, other than the prime numbers, are called Composite numbers; for obvious reason. All composite numbers are (exactly) divisible by at least one prime number. But there is an important exception. That is 1. 1 is neither a prime number nor a composite number. (Unfortunately, there exists ambiguity concerning whether 1 is prime or not. Here we are following the definition of prime which excludes 1.)

Finally, following above discussion, here is the statement of The fundamental theorem of Arithmetic:
Every natural number greater than 1 either is prime itself or is the product of prime numbers. Although the order of the primes in the second case is arbitrary, the primes themselves are not. For example:
1200 = 24 X 31 X 52 = 3 X 2 X 2 X 2 X 2 X 5 X 5 = 5 X 2 X 3 X 2 X 5 X 2 X 2 = etc.
The theorem is stating two things: first, that as 1200 is not a prime, it can be represented as a product of primes, and second, no matter how this is done, there will always be four 2s, one 3, two 5s, and no other primes in the product.

We started this post with an analogy to Chemistry. As we know there is a finite number of basic chemical elements, it is natural to ask whether there is only a finite number of primes or an infinite number of of primes. The answer is given brilliantly by Euclid. And we conclude this post by giving his argument.

Suppose there is a finite number of primes and the number of primes is N. Then the primes are p1 , p2 , …. , pN. Where pN is the largest prime. Now we construct a number C such that C = p1 X p2 X ….. X pN + 1. We see this number is not divisible by any of the primes p1 , p2 , …. , pN (there will always be a remainder 1). So this number C is another prime number. And certainly C > pN. This violets our assumption that pN is the largest prime. So there cannot be just N number (ie a finite number) of primes. Thus, there must be infinitely many primes.