为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数（t1，t2，t3），用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1+b×t2t3第一行：1×a+0×ba成立第二行：0×a+1×bb成立假设前k行都成立，考察第k+1行对于k1行和k行有t1(k1）t2(k1）t3(k1）t1(k)t2(k)t3(k)分别满足：t1(k1）×a+t2(k1）×bt3(k1）t1(k)×a+t2(k)×bt3(k)根据扩展欧几里德算法，假设t3(k1）jt3(k)+r则：t3(k+1）rt2(k+1）t2(k1）j×t2(k)t1(k+1）t1(k1）j×t1(k)则t1(k+1）×a+t2(k+1）×bt1(k1）×aj×t1(k)×a+t2(k1）×bj×t2(k)×bt3(k1）jt3(k)rt3(k+1）得证因此，当最终t3迭代计算到1时，有t1×a+t2×b1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
标签： 蓝天算法
还木有评论哦，快来抢沙发吧~