# extended euclid

• Sep 26th 2012, 07:42 AM
nitin1
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
• Sep 26th 2012, 09:44 AM
johnsomeone
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$.
• Sep 26th 2012, 10:26 AM
emakarov
Re: extended euclid
See also this post and the whole thread for an optimized way to compute the Bezout's identity coefficients.
• Sep 26th 2012, 01:52 PM
Deveno
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).