Results 1 to 14 of 14
Like Tree10Thanks
  • 2 Post By Plato
  • 2 Post By MarkFL
  • 1 Post By topsquark
  • 2 Post By HallsofIvy
  • 1 Post By romsek
  • 2 Post By Debsta

Thread: Prime Factorization

  1. #1
    Senior Member harpazo's Avatar
    Joined
    Sep 2014
    From
    NYC
    Posts
    463
    Thanks
    23

    Prime Factorization

    What is the prime factorization of 770?

    770 = 70 * 11

    70 = 35 * 2

    35 = 7 * 5

    So, the answer is 2 * 5 * 7 * 11.

    2 * 5 * 7 * 11 = 770

    What about for huge numbers?

    What about the prime factorization of 10,000? What about 100,000?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,155
    Thanks
    3048
    Awards
    1

    Re: Prime Factorization

    Quote Originally Posted by harpazo View Post
    What is the prime factorization of 770?

    770 = 70 * 11

    70 = 35 * 2

    35 = 7 * 5

    So, the answer is 2 * 5 * 7 * 11.

    2 * 5 * 7 * 11 = 770
    What about for huge numbers?
    What about the prime factorization of 10,000? What about 100,000?
    Suppose we want to factor any number. Say 26700456. That is random, but here it is
    The point being that today the web provides students with resources that could only be imagined even twenty years ago.

    But if you want to understand look at this.
    $1000000000000000$ that is a one with fifteen zeros. That is $10^{15}$
    Now $10=2\cdot 5$ So that $10^{15}=[2\cdot 5]^{15}=2^{15}\cdot 5^{15}$
    Thus now you have a prime factorization of a very large number. Done without any help of technology.
    Done because you understand the process.
    What is the prime factorization of $17,621,968,000,000,000~?$
    Thanks from harpazo and topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    2,239
    Thanks
    944

    Re: Prime Factorization

    Quote Originally Posted by harpazo View Post
    What is the prime factorization of 770?

    770 = 70 * 11

    70 = 35 * 2

    35 = 7 * 5

    So, the answer is 2 * 5 * 7 * 11.

    2 * 5 * 7 * 11 = 770

    What about for huge numbers?

    What about the prime factorization of 10,000? What about 100,000?
    There are simple tests for divisibility by small numbers, such as if the rightmost digit is divisible by 2, then then entire number is also. If the sum of the digits is divisible by 3, then the number is also. If the rightmost two digits is divisible by 4, then the number is also. If the rightmost digit is divisible by 5, then so is the number. If the number passes the tests of divisibility for 2 and 3, then it is divisible by 6. I would look up tests for divisibility and become at least familiar with them.
    Thanks from harpazo and topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member harpazo's Avatar
    Joined
    Sep 2014
    From
    NYC
    Posts
    463
    Thanks
    23

    Re: Prime Factorization

    Thank you everyone.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member harpazo's Avatar
    Joined
    Sep 2014
    From
    NYC
    Posts
    463
    Thanks
    23

    Re: Prime Factorization

    Quote Originally Posted by Plato View Post
    Suppose we want to factor any number. Say 26700456. That is random, but here it is
    The point being that today the web provides students with resources that could only be imagined even twenty years ago.

    But if you want to understand look at this.
    $1000000000000000$ that is a one with fifteen zeros. That is $10^{15}$
    Now $10=2\cdot 5$ So that $10^{15}=[2\cdot 5]^{15}=2^{15}\cdot 5^{15}$
    Thus now you have a prime factorization of a very large number. Done without any help of technology.
    Done because you understand the process.
    What is the prime factorization of $17,621,968,000,000,000~?$
    How do we start this one?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,304
    Thanks
    798
    Awards
    1

    Re: Prime Factorization

    Quote Originally Posted by harpazo View Post
    How do we start this one?
    The same approach as I think we all use (unless you are using some kind of more advanced algorithms.)

    How many times can you divide 17621968000000000 by 2? How many times can you divide what's left by 3? Etc.

    -Dan
    Thanks from harpazo
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    20,051
    Thanks
    3177

    Re: Prime Factorization

    To factor the number Plato gave, 17,621,968,000,000,000, I would first note that it is (17,621,968)(1,000,000,000). 1,000,000,000= 10^9= (2^9)(5^9).

    Now the hard part! 17,621,968 is even: 17,621,968= 2(8,810,984)= 2(2)(2)(4,405,492)= 2(2)(2)(2)(2,202,746)= 2(2)(2)(2)(2)(1101373). That last number is not even. Further, since its digit sum, 1+ 1+ 0+ 1+ 3+ 7+ 3= 16, is not divisible by 3, 3 is not a factor or 1101373. The last digit is not a "0" or a "5" so it is not divisible by 5. There is a test for divisibility by 7: subtract twice the last digit from the number. The original number is divisible by 7 if and only if the new one is. Here 1101373- 6= 1101367. If it is not obvious that that is divisible by 7, do it again- or just go ahead and try dividing by 7! 1101373/7= 157339 so 17,621,968= (2^5)(7)(157339). But 157339= 7(22477)= 7(7)(3211) while 3211 is not divisible by 7. The next larger prime number is 11 but 3211 is not divisible by 11. 3211= 13(247)= 13(13)(19). 19 itself is prime so we have 17,621,968= (2^5)(7^2)(13^2)(19).

    So we have 17,621,968,000,000,000= [(2^9)(5^9)][(2^5)(7^2)(13^2)(19)]= (2^14)(5^9)(7^2)(13^2)(19)
    Last edited by HallsofIvy; Dec 5th 2018 at 02:07 PM.
    Thanks from topsquark and harpazo
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,363
    Thanks
    2734

    Re: Prime Factorization

    try factoring $19249 \times 2^{13018586} + 1$

    (hint: it's easier than it looks!)
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member harpazo's Avatar
    Joined
    Sep 2014
    From
    NYC
    Posts
    463
    Thanks
    23

    Re: Prime Factorization

    Quote Originally Posted by HallsofIvy View Post
    To factor the number Plato gave, 17,621,968,000,000,000, I would first note that it is (17,621,968)(1,000,000,000). 1,000,000,000= 10^9= (2^9)(5^9).

    Now the hard part! 17,621,968 is even: 17,621,968= 2(8,810,984)= 2(2)(2)(4,405,492)= 2(2)(2)(2)(2,202,746)= 2(2)(2)(2)(2)(1101373). That last number is not even. Further, since its digit sum, 1+ 1+ 0+ 1+ 3+ 7+ 3= 16, is not divisible by 3, 3 is not a factor or 1101373. The last digit is not a "0" or a "5" so it is not divisible by 5. There is a test for divisibility by 7: subtract twice the last digit from the number. The original number is divisible by 7 if and only if the new one is. Here 1101373- 6= 1101367. If it is not obvious that that is divisible by 7, do it again- or just go ahead and try dividing by 7! 1101373/7= 157339 so 17,621,968= (2^5)(7)(157339). But 157339= 7(22477)= 7(7)(3211) while 3211 is not divisible by 7. The next larger prime number is 11 but 3211 is not divisible by 11. 3211= 13(247)= 13(13)(19). 19 itself is prime so we have 17,621,968= (2^5)(7^2)(13^2)(19).

    So we have 17,621,968,000,000,000= [(2^9)(5^9)][(2^5)(7^2)(13^2)(19)]= (2^14)(5^9)(7^2)(13^2)(19)
    Thank you for this reply.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,304
    Thanks
    798
    Awards
    1

    Re: Prime Factorization

    Quote Originally Posted by romsek View Post
    try factoring $19249 \times 2^{13018586} + 1$

    (hint: it's easier than it looks!)
    Uh huh. Whatever you say.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    6,363
    Thanks
    2734

    Re: Prime Factorization

    Quote Originally Posted by romsek View Post
    try factoring $19249 \times 2^{13018586} + 1$

    (hint: it's easier than it looks!)
    Quote Originally Posted by topsquark View Post
    Uh huh. Whatever you say.

    -Dan
    The factors are $19249 \times 2^{13018586} + 1$ and $1$
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,304
    Thanks
    798
    Awards
    1

    Re: Prime Factorization

    Quote Originally Posted by romsek View Post
    The factors are $19249 \times 2^{13018586} + 1$ and $1$
    Okay, I'll bite. How did you know that $\displaystyle 19249  \times 2^{13018586} + 1$ is prime? I don't have that many fingers!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    1,078
    Thanks
    324

    Re: Prime Factorization

    Quote Originally Posted by topsquark View Post
    Okay, I'll bite. How did you know that $\displaystyle 19249  \times 2^{13018586} + 1$ is prime? I don't have that many fingers!

    -Dan
    see https://en.wikipedia.org/wiki/Larges...n_prime_number

    Currently it ranks as the 20th largest known prime.
    Thanks from harpazo and topsquark
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member harpazo's Avatar
    Joined
    Sep 2014
    From
    NYC
    Posts
    463
    Thanks
    23

    Re: Prime Factorization

    Interesting good notes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime Factorization Help
    Posted in the Algebra Forum
    Replies: 11
    Last Post: Mar 23rd 2014, 12:02 PM
  2. Prime Factorization
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: May 12th 2013, 03:23 AM
  3. Prime Factorization
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Sep 21st 2010, 03:56 PM
  4. prime factorization 2
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Sep 16th 2008, 01:37 PM
  5. prime factorization
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 18th 2008, 07:51 PM

/mathhelpforum @mathhelpforum