Associated Topics || Dr. Math Home || Search Dr. Math

### Prime Factorization

```
Date: 01/07/97 at 17:11:16
From: Megaman7
Subject: Prime factorization

How do you find the prime factorization of a number?
```

```
Date: 01/07/97 at 19:49:10
From: Doctor Mike
Subject: Re: Prime factorization

Hi Megaman,

The short answer is that you keep looking for factors until you find
them all.  My longer answer gives suggestions for doing this.

Realistically, you start out with what is easy.  For example, if the
number is 48100 your first step should be to partially factor it
as 100*481 and then start working on factoring 100 and 481.  You might
be able to factor 100 completely in your head, but if not, you can at
least partially factor it as 10*10.  At this point you have that
48100 = 10*10*481.  From here it is an easy step to 2*5*2*5*481.

The way to start on 481 is to just start.  Try dividing 481 by 2, or
realize that that won't work because 481 is not even.  Try dividing
by 3.  That gives the quotient 160 along with a remainder, so that
won't work.  Next you COULD try dividing by 4, but that is not going
to have a chance since 2 didn't even work.

Then you could keep on trying more numbers: 5, 6, 7, 8, 9, and so on
until you find some number that divides into 481 without leaving a
remainder.  You are not going to have any luck until you try 13.
Bingo, 481/13 = 37 or equivalently 13*37 = 481.  Now we have a better
factorization: 2*5*2*5*13*37.  You probably know 13 is prime, so let's
look at 37.  You will find that nothing except 1 and 37 itself will
divide into 37 without remainder, so we are almost done.

It is customary to write the primes in order like 2*2*5*5*13*37 and
also to write them with exponents (2 squared and 5 squared) if
possible.

Here are a few hints to make the process easier and shorter.  When you
are dividing by smaller numbers to see if you get no remainder, you
only have to try dividing by prime numbers, like 2,3,5,7,11,13 etc.
product of two other numbers) is going to go into the number you are
working on without remainder, so is any prime in the factorization of
that composite.  This rule cuts down on what numbers you have to try.
You never have to try dividing by 6, for instance.

Another rule deals with when you can stop.  When you are trying out
dividing your number by primes less than it, you can stop when you get
past the square root of the number you are working on.  For instance,
if you are working on 37, whose square root is between 6 and 7, then
the only primes you have to try are 2, 3, and 5.  Again, think about
this rule and how you might prove it.  You do not need try 7 since
that is strictly greater than the square root of 37.

Finally, you cannot argue with success.  If you are pretty sure that
6 will go into the number you are working on, go ahead and try it.  If
you have a "hunch" that 37 is a divisor of 48100, go ahead and try it.
If you get lucky and stumble onto the fact that 37*1300 = 48100, then
you have a good head start.  Just don't depend on it too much.  The
organized way will always work.

There is a theorem which states that "there is only one answer" to a
factorization problem.  The only restriction on this result is that
answers like 168 = 2*2*2*3*7 and 168 = (2^3)*3*7 and 168 = 2*3*2*7*2
are all the "same" solution.

I hope these ideas help.   Good luck.

-Doctor Mike,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
Middle School Factoring Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search