Results 1 to 4 of 4

Math Help - extended euclid

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    india
    Posts
    17

    extended euclid

    can any please explain me the how this works ? how it finds the x and y in the bezout identity ? i have seacged google alot, but not getting i. please explain me
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: extended euclid

    You know this (*): For any x,y \in \mathbb{Z}, \exists k, r \in \mathbb{Z} such that x = ky + r, and 0 \le r < y.

    Note that if z divides both x and y, then z divides r, since r = x - ky.

    Let a,b \in \mathbb{Z}.

    Keep doing that (*) and track the results (keep getting values x_i and y_i in what follows):

    a = k_1b + r_1, 0 \le r_1 < b. Have r_1 = a - k_1b = x_1a + y_1b.

    b = k_2r_1 + r_2, 0 \le r_2 < r_1. Have r_2 = b - k_2(x_1a + y_1b) = x_2a + y_2b.

    r_1 = k_3r_2 + r_3, 0 \le r_3 < r_2. Have r_3 = (x_1a + y_1b) - k_3(x_2a + y_2b) = x_3a + y_3b.

    r_2 = k_4r_3 + r_4, 0 \le r_4 < r_3. Have r_4 = (x_2a + y_2b) - k_4(x_3a + y_3b) = x_4a + y_4b.

    Etc.

    At each stage after the first couple, get that x_{n+1} = x_{n-1} - k_nx_n, y_{n+1} = y_{n-1} - k_ny_n.

    But b >r_1 > r_2 > r_3 >... must terminate, either some r_n = 0 or some r_n = 1.

    Now consider both those cases:

    Case: If r_n = 0 occurs, then from r_{n-2} = k_nr_{n-1} + r_n, 0 \le r_n < r_{n-1),

    had that r_{n-1} divided r_{n-2}. But then r_{n-1} divides r_{n-3} = k_{n-1}r_{n-2} + r_{n-1}.

    And then r_{n-1} divides r_{n-2} and r_{n-3}. so it divides r_{n-4} = k_{n-2}r_{n-3} + r_{n-2}.

    This continues with r_{n-1} dividing all the r's on up until eventually dividing both a and b.

    Thus r_{n-1} divides gcd(a,b).

    But also, r_{n-1} = x_{n-1}a + y_{n-1}b, so gcd(a,b) divides r_{n-1}.

    Therefore, gcd(a,b) = r_{n-1}.

    Have shown that if r_n=0, then r_{n-1} = gcd(a,b).

    Case: Now suppose that r_n = 1 for some n.

    Then from r_{n} = x_{n}a + y_{n}b, it follows immediately that gcd(a,b) = 1 (and note that gives gcd(a,b) = r_n).

    Thus, when this prrocess terminates, whether it terminates with r_n = 0 or r_n = 1, either way, will have some m such that:

    r_{m} = gcd(a, b) and will have produced integers x_{m} and y_{m} such that gcd(a, b) = r_m = x_{m}a + y_{m}b.
    Last edited by johnsomeone; September 26th 2012 at 09:50 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: extended euclid

    See also this post and the whole thread for an optimized way to compute the Bezout's identity coefficients.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,319
    Thanks
    697

    Re: extended euclid

    let's pick two prime numbers and do it:

    gcd(5,17) = 1 (we know they are co-prime, since they are prime).

    17 = (3)(5) + 2
    5 = (2)(2) + 1
    2 = (2)(1) + 0 stop. back up one step.

    therefore:

    1 = 5 - (2)(2) = 5 - (2)(17 - (3)(5)) = 5 - (2)(17) + (2)(3)(5)

    = (1 + 6)(5) - (2)(17) = (7)(5) + (-2)(17), so:

    x = 7, and y = -2.

    indeed 35 - 34 = 1. magic!

    in otherwords, run the "extended eucildean (divison) algorithm" FORWARDS until you get the gcd, and run it BACKWARDS (collecting terms) until you get the x and y.

    this works for finding x and y such that:

    xa + yb = d, where d = gcd(a,b), for ANY gcd (not just co-prime a,b where the gcd = 1).

    this is also how you "find the inverse of a (mod n)".

    if a has an inverse (mod n), then there exists some x with:

    ax = 1 + tn, so (letting y = -t):

    ax + yn = 1. thus:

    (a (mod n))(x (mod n)) + (y (mod n))(n (mod n)) = 1 (mod n)

    (a (mod n))(x (mod n)) + (y (mod n))(0 (mod n)) = 1 (mod n)

    (a (mod n))(x (mod n)) + (0 (mod n)) = 1 (mod n)

    (a (mod n))(x (mod n)) = 1 (mod n)

    now x may not be between 0 and n-1, but writing x = qn + r, where r IS between 0 and n-1, we have:

    (a (mod n))(x (mod n)) = (a (mod n))(r (mod n)) = 1 (mod (n)), so "r" is what we're looking for.

    in our example above, we can find 5-1 (mod 17):

    we know that (7)(5) + (-2)(17) = 1 so:

    (7)(5) = 1 + (2)(17), that is:

    (7)(5) = 1 (mod 17), so the inverse of 5 (mod 17) is 7.

    *****************

    i cannot stress how important (and how simple) the division algorithm is. it is so important, structures in which it "works" are called Euclidean domains (named after...you guessed it! Mr. Euclid). it works for polynomials, too! (which comes in VERY handy).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Extended Euclid's algorithm - multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 12th 2010, 01:45 AM
  2. This has to be done by extended LP
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 10th 2008, 03:55 PM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM
  5. Euclid's Proposition 35
    Posted in the Geometry Forum
    Replies: 8
    Last Post: October 4th 2005, 04:10 AM

Search Tags


/mathhelpforum @mathhelpforum