同余式的欧几里得算法

同余式的欧几里德算法

理论依据

定理1 a,b Z，Qka Pkb ( 1)足下述递推关系：

a q1b r1，b q2r1 r2，r1 q3r2 r3，…，rk 1 qk 1rk rk 1，…，rn 1 qn 1rn 0；

k 1

rk对 k {1,2,...,n}成立，其中Qk、Pk、rk满

P0 1，P1 q1，P2 q2P1 P0，…，Pk qkPk 1 Pk 2，…，Pn qnPn 1 Pn 2；

Q0 0，Q1 1，Q2 q2Q1 Q0，…，Qk qkQk 1 Qk 2，…，Qn qnQn 1 Qn 2；

k {2,3,...,n}。（课本《初等数论》第三版P10）

显然其中rn (a,b)且( 1)

n 1

Qna ( 1)nPnb rn，故得s,t Z满

sa tb (a,b)。故由定理可得到求解二元一次不定方程ax by c的欧几里德算法

（详见课本《初等数论》第三版P27）。下面导出求解一次同余式的欧几里德算法。

设同余式为ax b(%m)，它等价于方程二元一次不定方程ax my b。由上面所述算法可以得到s,t Z满sa tm (a,m)，而它等价于sa (a,m)(%m)。当

(a,m)|b时，同余式有解，一个特解为x

b

s(%m)，通解为 (a,m)

x

bm

s k(%m)， k {0,1,...,(a,m) 1}。 (a,m)(a,m)

计算过程

与求解二元一次不定方程不同的是，求解同余式不需要m的系数Pk。 计算时可以借助表格：

具体计算步骤如下：

1. 由递推式rk 2 qkrk 1 rk作带余除法计算rk、qk； 2. 由递推式Qk qkQk 1 Qk 2计算Qk；

3. 直到得到rn 1 0，停止计算并得到n、rn、Qn； 4. 然后令(a,m) rn、s ( 1)

n 1

Qn，由公式sa (a,m)(%m)易得到通解。

当然，也可先化简同余式后再求解，只是当(a,b,m)含较大素因数时无法直接化简。

一个例子

例如：解同余式1215x 560(%2755)。 通过上述方法可得计算表

8 1

由于(a,m) 5|560，因此同余式有解。s ( 1)195 195，故通解为

x

5602755

( 195) k 200 551k(%2755)， k {0,1,...,5 1}。 55

东华理工大学理学院

——邓能财