大衍求一术算法原理讲解

对于形如ax ≡ 1 (mod n)，(a，n) = 1的同余式，秦九韶的大衍求一术给出了一种优秀的解法。

注意a，n必须互素

第一步我们令k0 = 0，k1 = 1， r0 = n， r1 = a，（k叫乘率，也是最后答案）

第二步我们让 r0 和 r1 作带余除法，即 r0 = q2r1 + r2

第三步我们用 r1 和 r2 作带余除法，即r1 = q3r2 + r3

..

直到出现rn = 1， 这时我们带回同余方程

定义kn = kn-2 - qnkn-1，依次回代求得kn即是同余方程的解