How to work out the prime factors of a number

Did you know that any number is either a prime number; or can be made by multiplying its unique prime factors together?

So:

Number	What type of number is it?
2	Prime
3	Prime
4	Composite (meaning something made by combining things) i.e 2 x 2
5	Prime
6	Composite 2 x 3
7	Prime
8	Composite 2 x 4
9	Composite 3 x 3
10	Composite 2 x 5
11	Prime
12	Composite 2 x 6 or 3 x 4
13	Prime
14	Composite 2 x 7
15	Composite 3 x 5
16	Composite 2 x 8 or 4 x 4 or 2 x 2 2 x 2
17	Prime
18	Composite 2 x 9, 3 x 6, 2 x 3 x 3,
19	Prime
and so on .....	they get a lot more complicated!

This is called ‘the fundamental theory of arithmetic’ and prime factors are very important in lots of different applications. The most well known is called RSA encryption, named after the 3 creators, Rivest, Shamir, and Adelman. They realised that  it’s much harder to factor large numbers into primes, than it is to create prime numbers in the first place.

RSA encryption is mainly used when you order items on the internet. If you bought a Maths Wrap (hint!), your credit card details will be securely encrypted.

It works something like this:

It is very simple to multiply numbers together, especially with computers. Suppose I ask you to multiply 12345 x 67891. The answer is  838114395.

So 12345 and 67891 are two of the factors of 838114395.

OK. Now suppose that I had given you 838114395 and asked you to work out what two numbers I had multiplied together? That would be very difficult, although a computer could do it quite easily. However the computer does it by trial and error and would need to perform around 29,000 calculations. For any size number the calculations required are roughly the square root of the number to be factored. In this case the square root of 838114395 is around 29,000.

These numbers are really small for a computer. However if the number to be factored is around 400 digits – which some are – it would take an awful long time.  Roughly 10 to the power of 200 possibilities, or a number with 201 digits. Unbelievably large. At one million calculations it would take much longer than the lifetime of the universe.

I’ll post a more detailed explanation in the future.

How to work out the prime factors of a number using a factor tree. This is usually GCSE level C around 2/3 marks.

[youtube_sc url=”http://youtu.be/IS05lBC6RpU” rel=”0″]