线性同余方程

1. 概述

于 初等数论 中, 线性同余方程 是形如 的一元同余方程. 它可转化为二元 线性 Diophantine 方程, 因而其可解性由 是否整除 决定.

2. 定义

定义 1 (线性同余方程)

设 , 且 . 称关于未知整数 的 同余式：

为模 的 线性同余方程.

3. 例子

例子 2 (有多个解类的线性同余方程)

线性同余方程：

可约化为 , 因而 . 所以它在模 意义下有两个不同的 解类：

4. 相关性质

定理 3 (线性同余方程的可解判据)

设 , 且 , 并令 . 则 线性同余方程

有整数解, 当且仅当 .

证明 4 (线性同余方程的可解判据)

充分性 ( )

若 同余式 有整数解 , 则存在 使：

由 二元线性 Diophantine 方程的可解判据, 有 .

必要性 ( )

若 , 则由 二元线性 Diophantine 方程的可解判据, 存在 使 . 因而 .

定理 5 (线性同余方程的解类个数)

设 , 且 , , 并设 . 则 线性同余方程 在模 意义下恰有 个不同的 解类.

证明 6 (线性同余方程的解类个数)

写 、、, 则 , 原方程等价于

若 , 则所有整数构成唯一的模 解类, 此时取 . 若 , 由 模逆元的存在判据 与 模逆元的唯一性, 该方程模 有唯一解 . 因此在两种情形下, 模 的全部解类的代表元均可取为：

它们两两不同余且共有 个.

推论 7 (互素系数情形)

设 , 且 . 若 , 则 线性同余方程 有唯一的模 解类：

证明 8 (互素系数情形)

由 模逆元的存在判据, 存在. 该 线性同余方程 两侧乘以 即得结论, 唯一性则由 线性同余方程的解类个数 在 时的情形得到.

5. 相关概念

• 模逆元
• 线性 Diophantine 方程
• 同余方程组

6. 术语翻译

中文	英文
线性同余方程	linear congruence

初等数论