Results 1 to 2 of 2

Math Help - gcd

  1. #1
    Member
    Joined
    Aug 2007
    Posts
    239

    gcd

    Why is it as a consequence of the Euclidean Algorithm that  (a,b) = ax + by ?

    I know we start off with  r_n = r_{n-2} - q_{n}r_{n-1} . From here do we solve for  r_{n-2} and  r_{n-1} in terms of the previous remainders eventually solving for  r_n in terms of  a,b ?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by shilz222 View Post
    Why is it as a consequence of the Euclidean Algorithm that  (a,b) = ax + by ?

    I know we start off with  r_n = r_{n-2} - q_{n}r_{n-1} . From here do we solve for  r_{n-2} and  r_{n-1} in terms of the previous remainders eventually solving for  r_n in terms of  a,b ?

    Thanks
    Are you asking for why or just an example of how to use it?

    If you are asking for the why of it, basically it's because of the division algorithm, and the fact that products and sums of integers are integers.

    For an example, consider 45 and 63:
    63 = 1 * 45 + 18
    45 = 2 * 18 + 9
    18 = 2 * 9 + 0

    Thus (45, 63) = 9

    -Dan
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum