Results 1 to 3 of 3

Math Help - Gcd

  1. #1
    Newbie
    Joined
    Sep 2006
    Posts
    16

    Gcd

    I was able to find the Greatest Common Divisor of two numbers by using the Euclidean Algorithm. But what is the easiest way to express this GCD as a linear combination in the form c=au+bv where c is the GCD of a,b?

    For example, the gcd(56,72)=8. And the linear combination can be expressed as 8 = (56)4-(72)(3). What's the easiest way to actually find this combination without simply guessing?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1
    Easy is in the eyes of the doer. It really depends on what one prefers.
    Personally I prefer to factor numbers into their prime factor form.
    For example 144000=(2^7)(3^2)(5^3) and 68600=(2^3)(5^2)(7^3).
    So gcd(144000, 68600 )=(2^3)(5^2).
    Use the common primes with their least powers.
    This method works with more than two numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by JimmyT View Post
    I was able to find the Greatest Common Divisor of two numbers by using the Euclidean Algorithm.
    Are you familiar with continued fractions?
    (That is the most direct method).
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum