Implementation of Euclid's Algorithm

I'm trying to understand this implementation of Euclid Algorithm.

First as usual the division algorithm is applied to n and a. Then repeatedly to pairs of remainders until the remainder 0 occurs.

$\displaystyle n = q_{1}a + r_{1}$

$\displaystyle a = q_{2}r_{1} + r_{2}$

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

.

.

.

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

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

Secondly( and this is where the problem starts) al the remainders up to $\displaystyle r_{m-1}$ are eliminated from all but the last of the equation from the above step to obtain an equation of the form $\displaystyle ab = kn + 1$ with $\displaystyle b$ in $\displaystyle Z_{n}$

Firstly I don't understand where the idea of eliminating the remainders comes from and what purpose it is serving here. At this point my understanding was to express the final equation in terms multiples of the values n and a using the equations obtained from the first step.

The method the implementation uses to eliminate the remainders is by multiplication by a suitable constant.

It is said the constant must satisfy $\displaystyle c_{j+2} = q_{j+1}c_{j+1} + c_{j}$ why is this? How can the remainders be eliminated through multiplication?

I'm very confused about what the implementation is doing here and how it is doing it.

Re: Implementation of Euclid's Algorithm

I should probably add that the implementation is trying to find the multiple inverse of a.

Re: Implementation of Euclid's Algorithm

A assume that by "multiple inverse of a" you mean the multiplicative inverse of a **modulo p**.

First, you do NOT want to "repeat until the remainder 0 appears". a has an inverse modulo p if and only if a and p are "relatively prime" which is always true if p is a prime number. Instead, you want to get a remainder of **1**.

If b is the multiplicative inverse of a, modulo p, then ab= np+ 1 or ab- np= 1.

For example, to find the multiplicative inverse of 6, modulo 11, we need to solve the diophantine equation 6x- 11n= 1. 6 divides into 11 once with remainder 5: 11(1)- 6(1)= 5. 5 divides into 6 once with remainder 1: 6(1)- 5(1)= 1. Replace "5" in that equation with 11(1)- 6(1) from the previous equation: 6(1)- (11(1)- 6(1))(1)= 6(2)- 11(1)= 1. The multiplicative inverse of 6, modulo 11, is 2: 6(2)= 12= 11+ 1

Similarly, to find the multiplicative inverse of 5 modulo 17, we need to solve the diophantine equation 5x- 17n= 1. 5 divides into 17 three times with remainder 2: 17(1)- 5(3)= 2. 2 divides into 5 twice with remainder 1: 5(1)- 2(2)= 1. Again, we can replace that "2" by 17(1)- 5(3): 5(1)- 2(17(1)- 5(3)= 7(5)- 2(17)= 3 so the multiplicative inverse of 5 modulo 17 is 7: 5(7)= 35= 2(17)+ 1.

Re: Implementation of Euclid's Algorithm

the euclidean algorithm is generally invoked to find the inverse of a unit a modulo n.

this only works if gcd(a,n) = 1. to see why, suppose that gcd(a,n) = d > 1 (with 0 < a < n).

then a = ds and n = dt for some positive integers 1 < s,t < n.

so at = (ds)t = (sd)t = s(dt) = sn = 0 (mod n), so a is a zero-divisor in Z_{n}.

so if a had some inverse (mod n), say x, we would have:

t = (ax)t = (xa)t = x(at) = x0 = 0, contradicting how we found t (above).

however, if gcd(a,n) = 1, then there are integers u,v such that:

au + nv = 1.

so au + nv ≡ 1 (mod n).

but au + nv ≡ au + 0v ≡ au (mod n).

so to explicitly find an inverse, we need to just compute u (mod n).

well, in general, if gcd(a,b) = d, we have r,s such that ra + sb = d. the question is: how do we find this pair of integers r and s?

let's assume that a < b (since gcd(a,b) = gcd(b,a), and gcd(a,a) is obviously a, and in that case we can choose r = 1, s = 0).

note first, that gcd(a,b) = gcd(a,b-a) = gcd(a,b-qa), as long as b-qa > 0.

if we write b = qa + r, where 0 ≤ r < a, we have:

gcd(a,b) = gcd(r,a).

we can then write:

a = q'r + r'

so that we have: gcd(a,) = gcd(r,a) = gcd(r',r). note our numbers are getting smaller each time.

eventually, we'll reach a point where:

r_{m-1} = q_{m+1}r_{m} + 0.

this tells us that gcd(a,b) = r_{m} = gcd(r_{m-1},r_{m}).

this lets us find r and s by "working backwards".

for example, gcd(16,38) = 2. to find r,s such that 16r + 38s = 2, we use the algorithm:

38 = (2)(16) + 6

16 = (2)(6) + 4

6 = (1)(4) + 2

4 = (2)(2) + 0 <--back up one step to find the gcd.

from step 3, we have: 2 = 6 - 4.

from step 2, we have 4 = 16 - (2)(6).

combining these two, we get:

2 = 6 - 4 = 6 - 16 + (2)(6) = (1+2)(6) - 16 = (3)(6) - 16.

from step 1, we have: 6 = 38 - (2)(16), and combining this with our previous "combo" we have:

2 = (3)(6) - 16 = (3)(38 - (2)(16)) - 16 = (3)(38) - ((3)(2) + 1)16 = (3)(38) - (7)(16) = (3)(38) + (-7)(16).

so r = -7, and s = 3 (and it is easy to check that (-7)(16) + (3)(38) = -112 + 114 = 2).

when gcd(a,b) = 1, using this algorithm allows us to find r,s such that ra + sb = 1.

for example, we will find gcd(7,16):

16 = (2)(7) + 2

7 = (3)(2) + 1

2 = (2)(1) + 0 <---back up one step, gcd is 1.

so 1 = 7 - (3)(2) = 7 - (3)[16 - (2)(7)] = 7 - 3(16) + (6)(7) = (1 + 6)(7) - 3(16) = (7)(7) + (-3)(16).

so r = 7, and s = -3.

this means that the inverse of 7 (mod 16) is 7. to check, note that:

(7)(7) = 49 ≡ 1 (mod 16) (since 49 = 3(16) + 1).

here is another example:

find the inverse of 15 mod 41.

we first want to find r,s such that 15r + 41s = 1.

41 = (2)(15) + 11

15 = (1)(11) + 4

11 = (2)(4) + 3

4 = (1)(3) + 1

3 = (3)(1) + 0 <---back up one step, and (ok, it's getting repetitious by now)

so 1 = 4 - 3 = (15 - 11) - (11 - 8) = 15 - 2(11) + 8 so far, so good, but we need 15's and 41's.

= 15 - 2(41 - 2(15)) + 2(4) = 15 - 2(41) + 4(15) + 2(15 - 11) = 15 - 2(41) + 4(15) + 2(15) - 2(11)

= 7(15) - 2(41) - 2(11) = 5(15) - 2(41) - 2(41 - 2(15)) = 7(15) - 4(41) + 4(15) = 11(15) + (-4)(41)

so we get r = 11, s = -4, so the inverse of 15 mod 41 is 11 (and indeed 165 ≡ 1 (mod 41)).