Euclids Algorithm and Multiple Inverses

$\displaystyle r_{m-2} = q_{m} r_{m-1} + r_{m} \hspace{50} 0 < r_{m} < r_{m-1} \\* r_{m-1} = q_{m+1} r_{m} + 0$

(ignore the indentation on the first line)

"The final equation shows that $\displaystyle r_{m}$ is a factor of $\displaystyle r_{m-1}$, and then the penultimate equation shows that $\displaystyle r_{m}$ is also a factor of $\displaystyle r_{m-2}$. Continuing in this way, we find that $\displaystyle r_{m}$ is a factor of all the remainders,"

But isn't this obviously not true?

$\displaystyle r_{m-3} = q_{m-1}r_{m-2} + r_{m-1}$

So in the very next line $\displaystyle r_{m}$ is no longer a factor.

What am I not seeing?

Re: Euclids Algorithm and Multiple Inverses

r_{m-3} = q_{m-1}r_{m-2} + r_{m-1}.

but r_{m-2} = q_{m}r_{m-1} + r_{m}.

so r_{m-3} = q_{m-1}(q_{m}r_{m-1} + r_{m}) + r_{m-1} = (q_{m-1}q_{m} + 1)r_{m-1} + q_{m-1}r_{m}

finally, since r_{m-1} = q_{m+1}r_{m}, we have:

r_{m-3} = (q_{m-1}q_{m} + 1)(q_{m+1}r_{m}) + q_{m-1}r_{m}

= (q_{m-1}q_{m}q_{m+1} + q_{m} + q_{m-1})r_{m},

so it certainly appears that r_{m} does indeed divide r_{m-3}.

let's look at a specific example:

suppose we wish to find gcd(33,138).

first we divide 138 by 33 and compute the remainder:

138 = 4*33 + 6

next, we repeat the process by dividing 33 by 6:

33 = 5*6 + 3

and again, we divide 6 by 3:

6 = 2*3 + 0 <--we got to 0, so our "final remainder" is the one in the second step: 3. without doing the "long division" we can show that 3 divides 138:

138 = 4*33 + 6 = 4*(5*6 + 3) + 6 = (4*5 + 1)(6) + 4*3 = (4*5 + 1)(2)(3) + 4*3 = [(4*5 + 1)(2) + 4](3) = [(21)(2) + 4](3) = (42 + 4)(3) = (46)(3).

note that we showed in the 2nd step that 3 divides 33 as well, since the 3rd step shows that 3 divides 6.

perhaps a longer, less trivial example will show this more clearly:

compute gcd(527,2261).

2261 = (4)(527) + 153

527 = (3)(153) + 68

153 = (2)(68) + 17

68 = (4)(17)

working backwards, we have:

153 = (2)(68) + 17 = (2)(4)(17) + 17 = ((2)(4) + 1)(17)

527 = (3)(153) + 68 = (3)[(2)(68) + 17] + (4)(17) = (3)(2)(4)(17) + (3)17 + (4)(17) = [(2)(3)(4) + 4 + 3](17) <--17 divides 527

2261 = (4)(527) + 153 = (4)[(2)(3)(4) + 4 + 3](17) + ((2)(4) + 1)(17) = [(4)(2)(3)(4) + (4)4 + (4)3 + (2)(4) + 1](17) <--17 divides 2261

= (96 + 16 + 12 + 8 + 1)(17) = (133)(17)

the remainders in this case were:

68 (= (4)(17))

153 ( = (2)(68) + 17 = (2)(4)(17) + 17 = ((2)(4) + 1)(17) = (9)(17))

527 ( = [(2)(3)(4) + 4 + 3](17) = (31)(17))

so in point of fact, 17 indeed divides every single one.

Re: Euclids Algorithm and Multiple Inverses

Excellent, thanks. Great explanation, makes total sense now.