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.  
Think about this.  If some composite number (a composite number is the 
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/