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

Printable View

- September 26th 2012, 08:42 AMnitin1extended 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

- September 26th 2012, 10:44 AMjohnsomeoneRe: extended euclid
You know this (*): For any such that , and .

Note that if divides both and , then divides , since .

Let .

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

. Have .

. Have .

. Have .

. Have .

Etc.

At each stage after the first couple, get that .

But must terminate, either some or some .

Now consider both those cases:

**Case:**If occurs, then from ,

had that divided . But then divides .

And then divides and . so it divides .

This continues with dividing all the 's on up until eventually dividing both and .

Thus divides .

But also, , so divides .

Therefore, .

Have shown that if , then .

**Case:**Now suppose that for some n.

Then from , it follows immediately that (and note that gives ).

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

and will have produced integers and such that . - September 26th 2012, 11:26 AMemakarovRe: extended euclid
See also this post and the whole thread for an optimized way to compute the Bezout's identity coefficients.

- September 26th 2012, 02:52 PMDevenoRe: 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).