第 1 章：同余、消去与模逆元

固定一个正整数 $n$ 作为模数。写 $a\equiv b\pmod n$ ，意思是 $n$ 整除 $a-b$ ：两个整数相差 $n$ 的整数倍，因此除以 $n$ 的余数相同。例如 $17\equiv2\pmod5$ ，因为 $17-2=3\cdot5$ 。

同余不要求两个整数本身相等。它只保留“除以 $n$ 后属于哪一种余数”的信息。以后说“模 $n$ 的一个数”，指的是一个剩余类；计算时可以用 $0,1,\ldots,n-1$ 中的代表表示它。

为什么可以先取余再计算？若 $a=b+un$ 、 $c=d+vn$ ，其中 $u,v$ 为整数，那么

$a+c=(b+d)+(u+v)n, \qquad ac=bd+n(ud+vb+uvn).$

这两个差都含有因子 $n$ ，所以加法和乘法保留同余。重复使用乘法，就得到 $a^k\equiv b^k\pmod n$ ，这里 $k$ 是非负整数。这是以后所有模幂运算的依据。

在整数等式中，非零因子可以消去；在同余中，需要额外条件。若

$ac\equiv bc\pmod n,$

我们知道的是 $n\mid c(a-b)$ 。要推出 $n\mid(a-b)$ ，必须保证 $c$ 不会替 $a-b$ 承担模数中的质因子。条件 $\gcd(c,n)=1$ 恰好保证这一点。这里 $\gcd$ 表示最大公约数，最大公约数为1就是互质。

严格地说，裴蜀等式告诉我们：若 $\gcd(c,n)=1$ ，存在整数 $u,v$ 使 $uc+vn=1$ 。两边乘 $a-b$ ，得到

$a-b=u\,c(a-b)+v\,n(a-b).$

右边两项都被 $n$ 整除，所以左边也被 $n$ 整除。于是

$\gcd(c,n)=1,\quad ac\equiv bc\pmod n \quad\Longrightarrow\quad a\equiv b\pmod n.$

不互质时结论确实会失败： $2\cdot1\equiv2\cdot4\pmod6$ ，但 $1\not\equiv4\pmod6$ 。这个例子用于提醒我们检查条件；一般证明仍是上面的裴蜀等式推导。裴蜀等式自身的证明在第14章。

若 $ab\equiv1\pmod n$ ，就称 $b$ 为 $a$ 的模 $n$ 逆元。它的作用是：乘 $a$ 之后再乘 $b$ ，会恢复原来的剩余类。因此解 $ax\equiv c\pmod n$ 时，可以两边乘 $b$ ，得到 $x\equiv bc\pmod n$ 。

逆元存在的充要条件是 $\gcd(a,n)=1$ 。充分性来自裴蜀等式： $au+nv=1$ 模 $n$ 后给出 $au\equiv1$ 。必要性也直接：若 $a$ 和 $n$ 有大于1的公因子，这个公因子会整除 $ab$ 和 $n$ ，不可能让 $ab$ 与1只相差 $n$ 的倍数。

所以后面证明中出现“消去一个因子”“取逆元”时，互质条件不是形式上的附加语，而是让这一步成立的原因。

第 1 章：同余、消去与模逆元 ​