Results 1 to 4 of 4

Math Help - Need help understanding prime factorisation

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    79

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    The easiest way (in my opinion) is to draw a factor tree. Let's take 4400 as an example. 4400 factors as 44\cdot 100. So you would draw two lines extending from 4400 with 44 and 100 at the end of each. Now 44 can be factored as 4\cdot 11. 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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by steph3824 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    (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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. gaussian prime factorisation
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 6th 2011, 10:38 PM
  3. Worst case for prime factorisation
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 16th 2009, 02:04 AM
  4. prime factorisation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 6th 2009, 07:06 AM
  5. Unique Prime factorisation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 12th 2008, 04:08 PM

Search Tags


/mathhelpforum @mathhelpforum