algorithm for multiplicative inverse
                  

   input:  a, n positive integers  a in [1,2,...,n-1]
                                   and gcd(a,n) = 1

   output:  the multiplicative inverse of a in Z/n.


   n0 = n;
   a0 = a;
   t0 = 0;
   t  = 1;
   q  = n0 div a0;  // largest integer less than or equal to n0/b0
   r  = n0 - q*a0   // r = n0 mod b0
   while (r > 0) do
     begin
        temp = t0 - q*t;
        if (temp >= 0) then temp = temp mod n;
        if (temp < 0) then temp = n - ((-temp) mod n);
        t0 = t;
        t = temp;
        n0 = a0;
        a0 = r;
        q = n0 div a0; 
        r = n0 mod a0;
     end

        if (a0 <> 1) then
             a has no inverse mod n
        else
            ainverse = t mod n