extended euclid

**nitin1** · September 26th 2012, 07:42 AM

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

**johnsomeone** · September 26th 2012, 09:44 AM

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$ .

**emakarov** · September 26th 2012, 10:26 AM

See also this post and the whole thread for an optimized way to compute the Bezout's identity coefficients.

**Deveno** · September 26th 2012, 01:52 PM

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).

Thread: extended euclid

LinkBack

Thread Tools

Display

extended euclid

Re: extended euclid

Re: extended euclid

Re: extended euclid

Similar Math Help Forum Discussions

Extended Euclid's algorithm - multiplicative inverse

This has to be done by extended LP

Another GCD using Euclid's Algorithm

Euclid's algorithm

Euclid's Proposition 35

Search Tags