2.4 中国剩余定理
定理2.9 设 m 与 n 为正整数, 则对于任意整数 a,b, 当且仅当
a≡b (mod (m,n))
时, 存在整数 x 满足:
x≡a (mod m) (2.5)
且
x≡b (mod n) (2.6)
如果 x 是同余方程 (2. 5) 与 (2. 6) 的解, 那么当且仅当
x≡y (mod [m,n])
时, 整数 y 也是一个解.
证明 如果 x 是同余方程 (2. 5) 的一个解, 那么对某整数 u, 有 x=a+mu. 如果 x 也是同余方程 (2. 6) 的一个解, 那么有
x=a+mu≡b (mod n),
即对某整数 v, 有
a+mu=b+nv.
因此有
a−b=nv−mu≡0 (mod (m,n)).
对应的, 如果有 a−b≡0 (mod (m,n)), 那么根据定理1. 15, 存在整数 u,v 满足
a−b=nv−mu.
那么
x=a+mu=b+nv
就是两个同余方程的解.
当且仅当
y≡a≡x (mod m)
且
y≡b≡x (mod n)
时, 即当且仅当 x−y 是 m,n 的公倍数时, 或者 x−y 可以被 m,n 的最小公倍数
[m,n] 整除时, 整数 y 是两个同余方程的另一个解. 证明完毕.
例如, 同余方程组
x≡5 (mod 21) ,
x≡19 (mod 56) ,
有一组解, 因为
(56,21) =7
且
19≡5 (mod 7).
如果存在整数 u 满足
x=5+21u≡19 (mod 56),
也就是
21u≡14 (mod 56),
3u≡2 (mod 8),
或者
u≡6 (mod 8),
那么整数 x 就是一个解. 于是
x=5+21u=5+21(6+8v)=131+168v
是同余方程组的一解, 其中 v 为任意整数. 因此, 方程组的所有解就是同余类 131+168Z.
定理 2. 10 (中国剩余定理) 设 k≥2. 如果 a1, …, ak 是整数, 且 m1, …, mk 是两两互质的正整数, 那么存在一个整数 x 使得
x≡ai (mod mi) , i=1, …, k.
如果 x 是这个同余方程组的任意一个解, 那么整数 y 也是它的一个解, 当且仅当
x≡y (mod m1⋯mk) .
证明 我们通过对 k 进行归纳来证明这个定理. 如果 k=2, 那么 [m1, m2]=m1m2, 这是定理 2. 9 的一个特例.
设k≥3, 并且假设命题对于 k−1 个同余方程成立. 那么就存在一个整数 z 使得 z≡aI (mod mi) , 其中 i=1, …, k−1. 既然 m1, …, mk 是两两互质的整数, 就有
(m1⋯mk−1, mk) =1,
并且根据 k=2 时的情形, 存在一个整数 x 使得
x≡z (mod m1⋯mk−1) ,
x≡ak (mod mk) .
于是有
x≡z≡ai (mod mi) ,
其中 i=1, …, k−1.
如果 y 是 k 个同余方程组的另一个解, 那么对于所有i=1, …, k, x−y 都被 mi 整除. 既然 m1, …, mk 两两互质, 于是 x−y 被 m1, …, mk 整除. 证明完毕. □
例如, 同余方程组
x≡2 (mod 3) ,
x≡3 (mod 5) ,
x≡5 (mod 7) ,
x≡7 (mod 11)
有一个解, 因为其模两两互质. 前两个同余方程的解是同余类
x≡8 (mod 15) .
前三个同余方程的解是同余类
x≡68 (mod 105) .
四个同余方程的解是同余类
x≡1118 (mod 1155) .
中国剩余定理有一个重要的应用, 来解决以下形式的丢番图方程
f(x1, …, xk) ≡0 (mod m) ,
其中 f(x1, …, xk) 是一元或多元变量的整系数多项式. 如果存在整数 a1, …, ak 使得
f(a1, …, ak) ≡0 (mod m) ,
那么这个方程模 m 可解. 中国剩余定理可以把对模 m 的同余方程组是否可解的问题, 转化为以素数幂 pr 为模的特例. 简单地, 我们考虑只有一个变量的多项式.
定理 2. 11 设
m=p1r1…pkrk
是正整数 m 的标准质因数分解形式. 设 f(x) 是整系数多项式. 同余方程
f(x) ≡0 (mod m)
是可解的, 其当且仅当同余方程
f(x) ≡0 (mod piri)
对于所有 i=1, …, k 都有解的时候.
证明 如果 f(x) ≡0 (mod m) 在整数范围内有解, 那么存在整数 a 使得 m 整除 f(a) , 于是有 p1r1 整除 f(a) , 因此同余方程 f(x) ≡0 (mod piri) 对于所有 i=1, …, k 都有解.
对应的, 假设同余方程 f(x) ≡0 (mod piri) 对于所有 i=1, …, k 都有解. 那么对于每一个 i 都存在整数 ai 使得
f(ai) ≡0 (mod piri)
由于素数幂 p1r1, …, pkrk 都是两两互质的, 中国剩余定理告诉我们存在整数 a 使得
a≡ai (mod piri)
对于所有的 i 都成立. 那么
f(a) ≡f(ai) ≡0 (mod piri)
就对于所有的 i 都成立. 由于 f(a) 是可以被每一个素数幂 piri 整除的, 它也就能够被它们的乘积 m 整除, 因此 f(a) ≡0 (mod m) . 证明结束. □
例如, 对下面的同余方程:
f(x) =x2−34≡0 (mod 495)
由于 495=32∙5∙11, x 就满足以下同余方程:
f(x) =x2−34≡x2+2≡0 (mod 9) ,
f(x) =x2−34≡x2+1≡0 (mod 5) ,
以及
f(x) =x2−34≡x2−1≡0 (mod 11) .
这些同余方程的解为:
f(5) ≡0 (mod 9) ,
f(2) ≡0 (mod 5) ,
以及
f(1) ≡0 (mod 11) .
通过中国剩余定理, 存在整数 a 使得
a ≡ 5 (mod 9) ,
a ≡ 2 (mod 5) ,
a ≡ 1 (mod 11) .
解出这些同余方程, 我们得到
a ≡ 122 (mod 495) .
我们可以检验如下:
f(122) =1222−34=14,850=30∙495,
因此
f(122) ≡0 (mod 495) .
翻译：
吴锦辉：定理 2. 9 俞守成：定理 2. 10 朱泓尧：定理 2. 11 整理：李商羽
2.4 中国剩余定理
定理2.9 设 m 与 n 为正整数, 则对于任意整数 a,b, 当且仅当
a≡b (mod (m,n))
时, 存在整数 x 满足:
x≡a (mod m) (2.5)
且
x≡b (mod n) (2.6)
如果 x 是同余方程 (2. 5) 与 (2. 6) 的解, 那么当且仅当
x≡y (mod [m,n])
时, 整数 y 也是一个解.
证明 如果 x 是同余方程 (2. 5) 的一个解, 那么对某整数 u, 有 x=a+mu. 如果 x 也是同余方程 (2. 6) 的一个解, 那么有
x=a+mu≡b (mod n),
即对某整数 v, 有
a+mu=b+nv.
因此有
a−b=nv−mu≡0 (mod (m,n)).
对应的, 如果有 a−b≡0 (mod (m,n)), 那么根据定理1. 15, 存在整数 u,v 满足
a−b=nv−mu.
那么
x=a+mu=b+nv
就是两个同余方程的解.
当且仅当
y≡a≡x (mod m)
且
y≡b≡x (mod n)
时, 即当且仅当 x−y 是 m,n 的公倍数时, 或者 x−y 可以被 m,n 的最小公倍数
[m,n] 整除时, 整数 y 是两个同余方程的另一个解. 证明完毕.
例如, 同余方程组
x≡5 (mod 21) ,
x≡19 (mod 56) ,
有一组解, 因为
(56,21) =7
且
19≡5 (mod 7).
如果存在整数 u 满足
x=5+21u≡19 (mod 56),
也就是
21u≡14 (mod 56),
3u≡2 (mod 8),
或者
u≡6 (mod 8),
那么整数 x 就是一个解. 于是
x=5+21u=5+21(6+8v)=131+168v
是同余方程组的一解, 其中 v 为任意整数. 因此, 方程组的所有解就是同余类 131+168Z.
定理 2. 10 (中国剩余定理) 设 k≥2. 如果 a1, …, ak 是整数, 且 m1, …, mk 是两两互质的正整数, 那么存在一个整数 x 使得
x≡ai (mod mi) , i=1, …, k.
如果 x 是这个同余方程组的任意一个解, 那么整数 y 也是它的一个解, 当且仅当
x≡y (mod m1⋯mk) .
证明 我们通过对 k 进行归纳来证明这个定理. 如果 k=2, 那么 [m1, m2]=m1m2, 这是定理 2. 9 的一个特例.
设k≥3, 并且假设命题对于 k−1 个同余方程成立. 那么就存在一个整数 z 使得 z≡aI (mod mi) , 其中 i=1, …, k−1. 既然 m1, …, mk 是两两互质的整数, 就有
(m1⋯mk−1, mk) =1,
并且根据 k=2 时的情形, 存在一个整数 x 使得
x≡z (mod m1⋯mk−1) ,
x≡ak (mod mk) .
于是有
x≡z≡ai (mod mi) ,
其中 i=1, …, k−1.
如果 y 是 k 个同余方程组的另一个解, 那么对于所有i=1, …, k, x−y 都被 mi 整除. 既然 m1, …, mk 两两互质, 于是 x−y 被 m1, …, mk 整除. 证明完毕. □
例如, 同余方程组
x≡2 (mod 3) ,
x≡3 (mod 5) ,
x≡5 (mod 7) ,
x≡7 (mod 11)
有一个解, 因为其模两两互质. 前两个同余方程的解是同余类
x≡8 (mod 15) .
前三个同余方程的解是同余类
x≡68 (mod 105) .
四个同余方程的解是同余类
x≡1118 (mod 1155) .
中国剩余定理有一个重要的应用, 来解决以下形式的丢番图方程
f(x1, …, xk) ≡0 (mod m) ,
其中 f(x1, …, xk) 是一元或多元变量的整系数多项式. 如果存在整数 a1, …, ak 使得
f(a1, …, ak) ≡0 (mod m) ,
那么这个方程模 m 可解. 中国剩余定理可以把对模 m 的同余方程组是否可解的问题, 转化为以素数幂 pr 为模的特例. 简单地, 我们考虑只有一个变量的多项式.
定理 2. 11 设
m=p1r1…pkrk
是正整数 m 的标准质因数分解形式. 设 f(x) 是整系数多项式. 同余方程
f(x) ≡0 (mod m)
是可解的, 其当且仅当同余方程
f(x) ≡0 (mod piri)
对于所有 i=1, …, k 都有解的时候.
证明 如果 f(x) ≡0 (mod m) 在整数范围内有解, 那么存在整数 a 使得 m 整除 f(a) , 于是有 p1r1 整除 f(a) , 因此同余方程 f(x) ≡0 (mod piri) 对于所有 i=1, …, k 都有解.
对应的, 假设同余方程 f(x) ≡0 (mod piri) 对于所有 i=1, …, k 都有解. 那么对于每一个 i 都存在整数 ai 使得
f(ai) ≡0 (mod piri)
由于素数幂 p1r1, …, pkrk 都是两两互质的, 中国剩余定理告诉我们存在整数 a 使得
a≡ai (mod piri)
对于所有的 i 都成立. 那么
f(a) ≡f(ai) ≡0 (mod piri)
就对于所有的 i 都成立. 由于 f(a) 是可以被每一个素数幂 piri 整除的, 它也就能够被它们的乘积 m 整除, 因此 f(a) ≡0 (mod m) . 证明结束. □
例如, 对下面的同余方程:
f(x) =x2−34≡0 (mod 495)
由于 495=32∙5∙11, x 就满足以下同余方程:
f(x) =x2−34≡x2+2≡0 (mod 9) ,
f(x) =x2−34≡x2+1≡0 (mod 5) ,
以及
f(x) =x2−34≡x2−1≡0 (mod 11) .
这些同余方程的解为:
f(5) ≡0 (mod 9) ,
f(2) ≡0 (mod 5) ,
以及
f(1) ≡0 (mod 11) .
通过中国剩余定理, 存在整数 a 使得
a ≡ 5 (mod 9) ,
a ≡ 2 (mod 5) ,
a ≡ 1 (mod 11) .
解出这些同余方程, 我们得到
a ≡ 122 (mod 495) .
我们可以检验如下:
f(122) =1222−34=14,850=30∙495,
因此
f(122) ≡0 (mod 495) .
翻译：
吴锦辉：定理 2. 9 俞守成：定理 2. 10 朱泓尧：定理 2. 11 整理：李商羽