title: algorithms for modular inverses
body: <p>i have read  section about The Extended Euclidean Algorithm &amp; Modular Inverses,which states that it not only computes <code>GCD(n,m)</code> but also  a and b such that <code>a*n+b*b=1;</code> 
  algorithm is described by by this way:</p>
  
  <blockquote>
    <ol>
    <li>Write down n, m, and the two-vectors (1,0) and (0,1)</li>
    <li>Divide the larger of the two numbers by the smaller - call this
    quotient q</li>
    <li>Subtract q times the smaller from the larger (ie reduce the larger
    modulo the smaller)</li>
    </ol>
  </blockquote>
  
  <p>(i have question here   if we  denote  by q   n/m,then <code>n-q*m is</code> not equal to 0?because  q=n/m;(assume that n>m),so why it is  necessary  such kind of  operation?
  then  4  step</p>
  
  <blockquote>
    <p>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)</p>
  </blockquote>
  
  <p>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);</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>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).</p>