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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.