## Search This Blog

### Why Prime Numbers are Important

Why Prime Numbers are Important

A prime number can be defined in several ways all of which are equivalent..

A prime number is one that has no divisors.
A prime number is one that cannot be split into equal size pieces.
A prime number is one that cannot be broken down into the product of two other integers.

Prime numbers are important. In fact, they can be thought of as fundamental numbers that are used to build all numbers. That's because of the following fact..

Any integer can be written as a product of prime numbers.

Or to put it another way, any integer can be broken down into a series of prime numbers all multiplied together. The branch of mathematics that studies integers is called "Number Theory" and this is one of the first important results in Number Theory.

How would you go about proving this? All you have to do is take any integer n and think about "breaking it down". Let's do it..

If I can find two integers (call them a and b) such that n=a*b then I've broken n down into the product of two other integers.

Now what? Well, we want our proof to be clean and elegant, so that means we want to avoid adding any unnecessary complications in our process. The simplest thing to do is repeat what we just did!

So we look at a and ask if a can be broken down into the product of two integers. Then we look at b and ask the same thing. If they can be broken down we write n as the product of all those numbers.

Then we do the same thing with each of those numbers. And we just keep going. Will this process ever stop? Yes, it will stop when we get a series of numbers that cannot be broken down into a product of two numbers. But this is just the definition of a prime number! So we are left with n written as the product of a series of prime numbers. That was easy!

Let's try a real world example. Take the number 12. First, find any two numbers that when multiplied together give 12. Any two will do, so let's go with 12=2*6.

Can 2 be broken down any more? No. What about 6? Yes, 6=2*3, so now we have 12=2*2*3. Can any of these numbers be broken down any more. No. So 2*2*3 is the prime decomposition of 12. Notice that in a prime decomposition a prime may be repeated, in this case 2 is repeated.

What would have happened if instead of starting with 12=2*6 we used 12=3*4? No problem, we would wind up with 12=3*2*2 which is the same result. This may lead you to suspect that a prime decomposition is unique. It is, an integer has exactly one prime decomposition.

Actually, to make sure an integer has only one prime decomposition it's necessary to exclude the number 1 from the list of primes, otherwise for 12 we could write 12=3*2*2*1 and 12=3*2*2*1*1 which would mean the prime decomposition is not unique. So if you ever tell a mathematician that 1 is a prime number and they get a bit upset this is the reason why. By general agreement 1 is not a prime.

Here's the prime decomposition of a few integers..

2=2
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
11=11
12=2*2*3
13=13
14=2*7
15=3*5
16=2*2*2*2
17=17
18=2*3*3
19=19
20=2*2*5

Of course, the prime decomposition of a prime consists of only one number.. itself.

So, the general expression for a prime decomposition is..

m=(p1^s1)*(p2^s2)*......*(pn^sn)

where p1,p2,...,pn are prime numbers and s1,s2,s3,...,sn are just integer powers and represent the simple fact that in the prime decomposition primes may be repeated. By collecting like primes together and raising them to a power we make sure that p1,p2,p3,...,pn are the set of distinct primes with no duplication.

An example will help..

567=3*3*3*3*7=(3^4)*7

3 and 7 are the distinct primes in the decomposition, 4 is just a power that represents the fact that 3 occurs 4 times in the decomposition.

Content written and posted by Ken Abbott abbottsystems@gmail.com