问模逆算法

EN

我读过关于扩展的欧几里德算法&模逆的一节，其中指出，它不仅计算GCD(n,m)，而且计算a和b，这样就可以这样描述a*n+b*b=1;算法：

1. 写了n，m，并且两个向量(1,0)和(0，1)
2. 除以两个数字中较大的一个，称为小商q
3. 减去q倍于较大的(即减小较大的模越小)

。

(这里我有一个问题，如果我们用q/m表示，那么n-q*m is不等于0?因为q= n/m；(假设n>m)，那么为什么需要这样的运算呢？然后第四步

4.从较大的向量中减去对应较小向量的Q倍。重复步骤2到4，直到结果为0。

因此，我对这个问题的问题也是如何在代码中实现这个步骤?请帮助我，我不知道如何开始和从哪一点开始解决这样的问题，为了澄清结果，这个算法的一个例子应该是下面的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)

由此我们看到gcd(30, 53) =1，重新排列项，我们看到1=-13*53+23*30，因此我们得出30^(-1)=23(mod 53)。