内容 第二章 · 一次同余方程 · 20
术语线索
divisor communis maximus / solvability condition
最大公因数 / 可解条件。
命题
The congruence ax ≡ h modulo m is solvable exactly when gcd(a,m) divides h.
同余 ax ≡ h (mod m) 可解，当且仅当 gcd(a,m) 整除 h。
读法 现代白话辅助
这条给出一次同余的完整分界。若公共因子没有同时整除右边，左边永远带着这个公共因子，右边却没有，方程不可能成立。
分步证明Step-by-step proof
1 / 2设 d=gcd(a,m)。左边 ax 在模 d 下总是 0。
若 h 也被 d 整除，可把 a、h、m 同除以 d，回到互素系数情形。
小例 worked example
题
6x ≡ 9 (mod 15) 是否可解？
解
gcd(6,15)=3，3 整除 9，所以可解。同除以 3 得 2x ≡ 3 (mod 5)，解为 x ≡ 4 (mod 5)。
我的笔记 自动保存