Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Prime > Prime Factorization

Any whole number bigger than 1 can be represented in exactly one way as a product of primes.  This theorem is called the Fundamental Theorem of Arithmetic, and it is also called the Unique Factorization Theorem.

Prime Factorization

The recognition of the fact that whole numbers bigger than 1 can be represented just one way as the product of primes is attributed to Euclid, who lived from 325 BC until he died in Alexandria, Egypt in 265 BC.

By expressing numbers as products of prime factors, it is easy to find their Greatest Common Divisor, or their Least Common Multiple.

First, you should know what a prime number is.  It's a number that can't be expressed as the product (that means by multiplying together) smaller numbers.  An example is 5.  5 can't be expressed as the product of any smaller numbers.  Its only factors are 1 and 5.

The Sieve of Eratosthanes can be used to find prime numbers.  Using this method, we see that the first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.

A good way to find the prime factorization of a number is to see if it can be divided by these small primes.  If it can, then "take out" those factors, and try dividing the quotient by small primes.  Each of these successful divisions yields one prime factor.  When you're left with a prime number at the end, then you're done.

I'll illustrate the method with an example.  Find the prime factorization of 24:

24 ÷ 2 = 12
12 ÷ 2 = 6
6 ÷ 2 = 3

and 3 is a prime number.  As you can see, I started by dividing by the smallest prime number, and dividing the result as many times as I could, and then at the end I was left with a prime number.  So 24 is 2 × 2 × 2 × 3.

You might also notice in this example, that the first quotient, 12, was written twice, as was each quotient that follows it.  If you're finding the prime factorization of a few different numbers, you might find it easier to just write each answer once, on the line below.  That looks like this:

Find the prime factorization of 24:

24 ÷ 2
12 ÷ 2
6 ÷ 2
3

Now the last number written on each line is a prime number, so the method is not only easier to write, but it is clearer to see, as well.  Again, the prime factorization of 24 is 2 × 2 × 2 × 3.  This can be written as 23 × 3.  The little "3" is called an exponent, and means that the 2 appears three times as a factor of 24.  You say this "two to the power three times three".

Now let's use the method with a different number.

Find the prime factorization of 180:

180 ÷ 2
90 ÷ 2
45 ÷ 3
15 ÷ 3
5

So 180 = 22 × 32 × 5.

One more example -- Find the prime factorization of 77:

77 ÷ 7
11

So 77 is 7 × 11

What's Next?

Do you understand prime factorization?  If not, send me an email (click the link, below) and I will be glad to help you.  If so, then the next topic is finding the Greatest Common Divisor of two or more numbers, using their prime factorizations.

Internet references

The Fundamental Theorem of Arithmetic, from Mathworld.

www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Euclid.html gives a biography of Euclid.

Related pages in this website

The Sieve of Eratosthanes is an easy method to find prime numbers.

Factoring polynomials -- a second year algebra topic, which requires that you be able to factor whole numbers.

Highly Composite Numbers have many factors for their size.

Other so-called "fundamental" theorems

The Fundamental Theorem of Algebra says Every polynomial equation of degree n with complex coefficients has n roots in the complex numbers.

The Fundamental Theorem of Calculus says if f is the derivative of F, then the integral from a to b of f(x) dx is F(b)-F(a).

 

 


The webmaster and author of this Math Help site is Graeme McRae.