同余方程组

1. 概述

于 初等数论 中, 同余方程组 要求一个整数同时满足若干个模数条件. 当模数两两互素时, 中国剩余定理 保证解存在且在模数乘积意义下唯一.

2. 定义

定义 1 (同余方程组)

设 , , 且 . 称由下列 同余式 组成的方程组：

为关于未知整数 的 同余方程组.

3. 例子

例子 2 (两个互素模数)

同余方程组：

的全部整数解为 .

4. 相关性质

定理 3 (中国剩余定理)

设 , , 且 . 若 两两互素, 则 同余方程组：

有整数解, 且解在模 意义下唯一.

证明 4 (中国剩余定理)

存在性

对每个 , 令 . 由 一个元素与其余元素之积互素, 可知 , 故由 模逆元的存在判据, 存在 使

取

对任意 , 第 项满足 , 而当 时有 . 因而 , 所以 是该 同余方程组 的一组解.

唯一性

若 都是该 同余方程组 的解, 则对每个 都有 . 由 两两互素因数的乘积仍整除, , 即 .

定理 5 (两个模数的一般相容条件)

设 , 且 . 同余方程组：

有整数解, 当且仅当

有解时, 解在模 意义下具有 唯一性.

证明 6 (两个模数的一般相容条件)

令 .

充分性 ( )

若 是该 同余方程组 的解, 由 与 , 可得 且 , 因而 .

必要性 ( )

若 , 由第一个 同余式 写 . 将其代入第二个同余式后得到：

由 线性同余方程的可解判据, 该方程存在整数解 , 从而原方程组存在整数解.

解的唯一性

将关于 的同余式约去 后得到

因 , 当 时所有整数构成唯一的模 剩余类; 当 时, 由 模逆元的存在判据 与 模逆元的唯一性, 在模 意义下唯一. 因 , 相应的 的模数为：

因而 在该模数意义下唯一, 其中等式来自 最大公因数与最小公倍数的乘积公式.

5. 相关概念

• 线性同余方程
• 互素
• 两两互素
• 完全剩余系
• 剩余类

6. 术语翻译

中文	英文
同余方程组	system of congruences
中国剩余定理	Chinese remainder theorem

初等数论