大衍求一術算法原理講解

對於形如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即是同餘方程的解