Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Using the prime factorization

  1. Feb 19, 2009 #1
    1. The problem statement, all variables and given/known data

    Find the gcd of 22,471 and 3,266 and express in the form 22,471x + 3,266y

    2. Relevant equations

    3. The attempt at a solution

    I know how to get the gcd of easy numbers... using the prime factorization. But how do I do that with numbers of this scale?
  2. jcsd
  3. Feb 19, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Re: gcd

    Use the Euclidean algorithm. You don't have to factorize them.
  4. Feb 20, 2009 #3
    Re: gcd

    thank you!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook