同余式的欧几里德算法
理论依据
定理1,a b Z +
∀∈，1
(1)k k k k Q a P b r --=-对{1,2,...,}k n ∀∈成立，其中k Q 、k P 、k r 满
足下述递推关系：
11a q b r =+，212b q r r =+，1323r q r r =+，…，111k k k k r q r r -++=+，…，110n n n r q r -+=+；
01P =，11P q =，2210P q P P =+，…，12k k k k P q P P --=+，…，12n n n n P q P P --=+；
00Q =，11Q =，2210Q q Q Q =+，…，12k k k k Q q Q Q --=+，…，12n n n n Q q Q Q --=+；
{2,3,...,}k n ∀∈。

（课本《初等数论》第三版10P ）
显然其中(,)n r a b =且1
(1)
(1)n n n n n Q a P b r --+-=，故得,s t Z ∈满
(,)sa tb a b +=。

故由定理可得到求解二元一次不定方程ax by c +=的欧几里德算法
（详见课本《初等数论》第三版27P ）。

下面导出求解一次同余式的欧几里德算法。

设同余式为(%)ax b m ≡，它等价于方程二元一次不定方程ax my b +=。

由上面所述算法可以得到,s t Z ∈满(,)sa tm a m +=，而它等价于(,)(%)sa a m m ≡。

当
(,)|a m b 时，同余式有解，一个特解为(%)(,)
b
x s m a m ≡
，通解为 (%)(,)(,)
b m
x s k m a m a m ≡
+，{0,1,...,(,)1}k a m ∀∈-。

计算过程
与求解二元一次不定方程不同的是，求解同余式不需要m 的系数k P 。

计算时可以借助表格：
具体计算步骤如下：
1. 由递推式21k k k k r q r r --=+作带余除法计算k r 、k q ；
2. 由递推式12k k k k Q q Q Q --=+计算k Q ；
3. 直到得到10n r +=，停止计算并得到n 、n r 、n Q ；
4. 然后令(,)n a m r =、1
(1)
n n s Q -=-，由公式(,)(%)sa a m m ≡易得到通解。

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

一个例子
例如：解同余式1215560(%2755)x ≡。

通过上述方法可得计算表
由于(,)5|560a m =，因此同余式有解。

81
(1)195195s -=-=-，故通解为
5602755
(195)200551(%2755)55
x k k ≡
-+≡+，{0,1,...,51}k ∀∈-。

东华理工大学理学院
——邓能财。