algorithms for modular inverses

i have read section about The Extended Euclidean Algorithm & Modular Inverses,which states that it not only computes GCD(n,m) bu开发者_如何学运维t also a and b such that a*n+b*b=1; algorithm is described by by this way:

1. Write down n, m, and the two-vectors (1,0) and (0,1)
2. Divide the larger of the two numbers by the smaller - call this quotient q
3. Subtract q times the smaller from the larger (ie reduce the larger modulo the smaller)

(i have question here if we denote by q n/m,then n-q*m is not equal to 0?because q=n/m;(assume that n>m),so why it is necessary such kind of operation? then 4 step

4.Subtract q times the vector corresponding to the smaller from the vector corresponding to the larger 5.Repeat steps 2 through 4 until the result is zero 6.Publish the preceding result as gcd(n,m)

so my question for this problem also is how can i implement this steps in code?please help me,i dont know how start and from which point could i start to solve such problem,for clarify result ,it should look like this An example of this algorithm is the following computation of 30^(-1)(mod 53);

53           30           (1,0)                        (0,1)
53-1*30=23   30           (1,0)-1*(0,1)=(1,-1)         (0,1)
23           30-1*23=7    (1,-1)                       (0,1)-1*(1,-1)=(-1,2)
23-3*7=2      7           (1,-1)-3*(-1,2)=(4,-7)       (-1,2)
2             7-3*2=1     (4,-7)                      (-1,2)-3*(4,7)=(-13,23)
2-2*1=0       1           (4,-7)-2*(-13,23)=(30,-53)   (-13,23)

From this we see that gcd(30,53)=1 and, rearranging terms, we see that 1=-13*53+23*30, so we conclude that 30^(-1)=23(mod 53).

The division is supposed to be integer division with truncation. The standard EA for gcd(a, b) with a <= b goes like this:

 b =  a * q0 + r0
 a = r0 * q1 + r1
r0 = r1 * q2 + r2
  ...
r[N+1] = 0

Now rN is the desired GCD. Then you back-substitute:

r[N-1] = r[N] * q[N+1]

r[N-2] = r[N-1] * q[N] + r[N]
       = (r[N] * q[N+1]) * q[N] + r[N]
       = r[N] * (q[N+1] * q[N] + 1)

r[N-3] = r[N-2] * q[N-1] + r[N-1]
       = ... <substitute> ...

Until you finally reach rN = m * a + n * b. The algorithm you describe keeps track of the backtracking data right away, so it's a bit more efficient.

If rN == gcd(a, b) == 1, then you have indeed found the multiplicative inverse of a modulo b, namely m: (a * m) % b == 1.