Results 1 to 4 of 4

Thread: 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
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    Re: extended euclid

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

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

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

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

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

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

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

    $\displaystyle r_2 = k_4r_3 + r_4, 0 \le r_4 < r_3$. Have $\displaystyle 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 $\displaystyle x_{n+1} = x_{n-1} - k_nx_n, y_{n+1} = y_{n-1} - k_ny_n$.

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

    Now consider both those cases:

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

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

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

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

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

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

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

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

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

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

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

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

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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,546
    Thanks
    842

    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: Nov 12th 2010, 01:45 AM
  2. This has to be done by extended LP
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 10th 2008, 03:55 PM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 3rd 2008, 05:18 AM
  5. Euclid's Proposition 35
    Posted in the Geometry Forum
    Replies: 8
    Last Post: Oct 4th 2005, 04:10 AM

Search Tags


/mathhelpforum @mathhelpforum