Prime Factors as BricksDate: 10/26/2001 at 22:18:29 From: Andre Burrell Subject: Prime Factorization I have trouble with prime factorization. I need an easier way to do it than making a tree. Date: 10/27/2001 at 11:43:28 From: Doctor Sarah Subject: Re: Prime Factorization Hi Andre - thanks for writing to Dr. Math. To begin with, it's helpful to have in your head the divisibility rules for prime numbers like 2, 3, 5, and 7. You'll find them in the Dr. Math FAQ: Divisibility Rules http://mathforum.org/dr.math/faq/faq.divisibility.html 2 If the last digit is even, the number is divisible by 2. 3 If the sum of the digits is divisible by 3, the number is also. 5 If the last digit is a 5 or a 0, the number is divisible by 5. 7 Take the last digit, double it, and subtract it from the rest of the number; if the answer is divisible by 7 (including 0), then the number is also. A good basic knowledge of the multiplication table is also a big help (you knew there was a reason for learning all those multiplication facts, right?). Now let's take an example. How would you find the prime factorization of 126? Well, one way you could start would be by noticing that 126 is even. 2 is the only even prime number, and it divides evenly into every even number. So, if we divide 126 by 2 we get 63. 126 = 2 x 63 Next we know from our multiplication tables that 63 = 7 x 9. 126 = 2 x 7 x 9 We know that 7 is prime; what about 9? Nine is not prime: 9 = 3 x 3. 126 = 2 x 7 x 3 x 3 Now we can stop since we have reached only prime numbers. The prime factors of 126 are: 2 x 3 x 3 x 7 or 2 x 3^2 x 7 Does this help? - Doctor Sarah, The Math Forum http://mathforum.org/dr.math/ Date: 10/28/2001 at 10:28:17 From: Andre Burrell Subject: Re: Prime Factorization Thank you very much, but could you explain it a little easier? Date: 10/28/2001 at 23:15:37 From: Doctor Peterson Subject: Re: Prime Factorization Hi, Andre. Let's try taking the most basic approach I can think of, to see what this is all about. The prime numbers are the building blocks of which any whole number can be built by multiplying them together. Think of them as bricks. Some buildings might consist of a single brick (weird, but possible); most will be built of a number of bricks. Some of those bricks might be different sizes or colors, others might be identical. Suppose we want to break a building down into a pile of bricks, to see what it is made of. How do we do it? One brick at a time. That's what we want to do with numbers: to break them down by pulling out one brick (prime factor) at a time and putting them in piles. So let's take the number 245. There are two main ways to find the factors. One is to methodically go through all the possible prime factors and see if they are there. So we get a list of small primes to try: 2, 3, 5, 7, 11, ... Try one at a time, starting at the beginning of the list. Is there a 2 in this number? Divide by 2, and you find that it doesn't divide evenly. How about 3? Again, it doesn't go in. (This is where knowing those divisibility rules can save time, but you can just do the divisions if you prefer not to take the time to learn them.) Now we try 5: ___49_ 5 ) 245 It goes evenly, so we know that 245 = 5 * 49 We've pulled one brick out of the wall, and what's left of the wall is 49. Now we can see what prime factors there are in 49. We first check whether there is another 5 in there; taking one out doesn't mean there isn't another! (On the other hand, we knew we didn't have to try 3 again, because we know there weren't any there.) But 49 is not divisible by 5, so we continue through our list of primes. Is 49 divisible by 7? Yes, and the quotient is another 7: 49 = 7 * 7 so 245 = 5 * 7 * 7 Since we know 7 is a prime, we're finished; we have a pile of prime "bricks." The only thing left to do, if we want, is to pile up identical bricks by combining groups of the same prime as powers: 245 = 5 * 7^2 That's it! The other approach is the opportunistic method: rather than go through the primes in order, we often see an obvious prime to pick first. (That's like seeing a loose brick sticking out and pulling that one out first, rather than starting at the top.) In this case, since 245 ends with 5, we can tell immediately that it is divisible by 5, so we would divide by that first. Then when we see 49, we should recognize that as a square, and can just write it that way. All that comes with experience. If you just want to take the slow route and make sure you get the job done, that's fine. The important thing is that you are getting to know how numbers are built. If you'd like a different explanation, try going to our search page http://mathforum.org/mathgrepform.html and entering the phrase prime factorization . - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ Date: 10/29/2001 at 08:37:07 From: Andre Burrell Subject: Re: Prime Factorization Thanks, that was much simpler. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/