Thread: Need help understanding prime factorisation

We're talking about primes and the unique factorization theorem in my applied algebra class. Something I'm not understanding is prime factorization. For example, say we want gcd(21000, 4400).
To start off, my professor showed that 21,000=2^(3) x 3^(1) x 5^(3) x 7^(1) and that 4400=2^(4) x 5^(2) x 11^(1).
I don't understand how in the heck you figure that out. Do you just have to sit there a long time and play with numbers until you finally get something that works or is there some kind of method for figuring out what primes to use and what the exponents on those primes are? Like, how do you randomly know to use the primes 2,3,5, and 7 for 21,000 and how do you automatically know what the exponent on them should be? Is there something I'm missing?

The easiest way (in my opinion) is to draw a factor tree. Let's take 4400 as an example. 4400 factors as . So you would draw two lines extending from 4400 with 44 and 100 at the end of each. Now 44 can be factored as . So do the same thing with 2 lines extending from 44 with 4 and 11 at the ends. Circle the number 11 because it is prime. Similarly from 4 draw 2 lines and put 2 at the end of each. Circle these because they're prime. You still have to draw some more branches from 100 - can you finish on your own?

In the end, write all the circled numbers in increasing order. This is the prime factorization in canonical form (canonical is just a fancy word for "natural").

(Perhaps someone with better latex skills than me can actually draw the tree)

Originally Posted by steph3824

We're talking about primes and the unique factorization theorem in my applied algebra class. Something I'm not understanding is prime factorization. For example, say we want gcd(21000, 4400).
To start off, my professor showed that 21,000=2^(3) x 3^(1) x 5^(3) x 7^(1) and that 4400=2^(4) x 5^(2) x 11^(1).
I don't understand how in the heck you figure that out. Do you just have to sit there a long time and play with numbers until you finally get something that works or is there some kind of method for figuring out what primes to use and what the exponents on those primes are? Like, how do you randomly know to use the primes 2,3,5, and 7 for 21,000 and how do you automatically know what the exponent on them should be? Is there something I'm missing?

There is a sort of an algorithm if you like.

First make a list of prime numbers: 2, 3, 5, 7, 11, 13, etc.

Now take your number, say 21000. Divide it by the first prime on your list: 21000/2 = 10500. So you have one factor of 2.

Now take your new number, 10500 and divide it by the first prime on your list: 10500/2 = 5250. So you now have two factors of 2: 2^2.

Keep going until you get, in this case, three factors of 2.

Your number is now 2625. This is not divisible by 2, so take your next prime: 3. 2625/3 = 875 so you have one factor of 3. So far we've got 2^3 * 3 as your factor.

Continue this process until you have a prime number left over.

-Dan

(Perhaps someone with better latex skills than me can actually draw the tree)

It is perhaps worth noting that no efficient algorithm is known for factoring truly large numbers. From Wikipedia:

When the numbers are very large, no efficient integer factorization algorithm is publicly known; an effort concluded in 2009 by several researchers factored a 232-digit number utilizing hundreds of machines over a span of 2 years. The presumed difficulty of this problem is at the heart of certain algorithms in cryptography such as RSA.