Prime Factors as Bricks

Date: 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.