8.3 模运算、逆元与中国剩余定理

第 8.2 节不断使用余数缩小最大公约数问题。模运算换了一个观察角度：余数不再只是临时产生的副产品，我们要把余数相同的全部整数归为一类。

这样就能把无限多个整数压缩成一个有限的运算系统。

同余表示属于相同余数类

固定一个正整数 $n$ ，称为模数。对整数 $a,b$ ，如果

n\mid(a-b),

就写作

a\equiv b\pmod n,

读作“ $a$ 与 $b$ 模 $n$ 同余”。

等价地说， $a$ 与 $b$ 除以 $n$ 后得到相同余数。

模 $5$ 的例子

因为

17-2=15=5\cdot3,

所以

17\equiv2\pmod5.

两者除以 $5$ 后的余数都是 $2$ 。

负整数也属于余数类。因为

-3-2=-5,

所以

-3\equiv2\pmod5.

符号 $=$ 仍然表示普通相等。同余是另一种关系：虽然 $17\ne2$ ，但 $17\equiv2\pmod5$ 。

剩余与剩余类

每个整数都恰好与下面集合中的一个元素模 $n$ 同余：

\{0,1,2,\ldots,n-1\}.

这些标准代表叫作模 $n$ 的剩余。

模 $5$ 时， $2$ 所在的剩余类包含

\ldots,-8,-3,2,7,12,17,\ldots

因为相邻两项相差 $5$ 。

同余是第 4 章学习过的等价关系：

$a\equiv a\pmod n$ ；

若 $a\equiv b\pmod n$ ，则 $b\equiv a\pmod n$ ；

若 $a\equiv b\pmod n$ 且 $b\equiv c\pmod n$ ，则 $a\equiv c\pmod n$ 。

因此，同余把 $\mathbb Z$ 划分成 $n$ 个互不相交的剩余类。

加法与乘法保持同余

假设

a\equiv b\pmod n \qquad\text{且}\qquad c\equiv d\pmod n.

那么

a+c\equiv b+d\pmod n

以及

ac\equiv bd\pmod n.

对加法，

(a+c)-(b+d)=(a-b)+(c-d),

右侧能够被 $n$ 整除。

对乘法，把差改写为

ac-bd=c(a-b)+b(c-d).

右侧两项都能被 $n$ 整除，所以它们的和也能被 $n$ 整除。

因此，我们既可以在运算前取余，也可以在运算后取余。

例子：缩小一个大乘积

计算 $38\cdot47\pmod7$ 。

先分别缩小因子：

38\equiv3\pmod7, \qquad 47\equiv5\pmod7.

于是

38\cdot47\equiv3\cdot5=15\equiv1\pmod7.

整个过程不需要真的计算大乘积。

幂也可以不断取余

同余乘法可以反复使用。例如，

7\equiv2\pmod5,

所以

7^4\equiv2^4=16\equiv1\pmod5.

面对很大的指数时，可以使用重复平方，并对底数和每个中间平方及时取余。第 8.4 节会把这种方法用于 RSA。

正在加载交互实验...

让整数沿剩余时钟旋转，再在两个同步圆环上组合加法与乘法移动。拖动到负数或超过模数的数值时，系统会保留完整的同余轨迹；碰撞检测器则同时用“余数相同”和“差能被模数整除”解释结果。

正在加载概念检查...

正在加载本节练习...

模逆元撤销乘法

在普通有理数中，乘以非零数 $a$ 可以通过乘以 $1/a$ 撤销。在模运算中，只有找到合适的剩余，才能进行类似的“除法”。

如果整数 $x$ 满足

ax\equiv1\pmod n,

就称 $x$ 是 $a$ 模 $n$ 的乘法逆元。

也可以写作

x\equiv a^{-1}\pmod n.

这里的 $a^{-1}$ 表示模逆元，不是实数分数 $1/a$ 。

逆元什么时候存在

逆元存在，当且仅当

\gcd(a,n)=1.

最大公约数为 $1$ 的两个整数叫作互素。

若 $\gcd(a,n)=1$ ，贝祖等式给出整数 $x,y$ ，使得

ax+ny=1.

模 $n$ 取余后， $ny$ 这一整倍数消失，得到

ax\equiv1\pmod n.

所以 $a$ 的贝祖系数就是一个逆元。

反过来，若 $ax\equiv1\pmod n$ ，则 $ax-1$ 能被 $n$ 整除。因此存在整数 $y$ ，满足

ax+ny=1.

$a,n$ 的任意公因数都必须整除 $1$ ，所以最大公约数只能是 $1$ 。

用扩展欧几里得算法寻找逆元

求 $7$ 模 $26$ 的逆元。

欧几里得算法给出

\begin{aligned} 26&=3\cdot7+5,\\ 7&=1\cdot5+2,\\ 5&=2\cdot2+1. \end{aligned}

反向代入：

\begin{aligned} 1 &=5-2\cdot2\\ &=5-2(7-5)\\ &=3\cdot5-2\cdot7\\ &=3(26-3\cdot7)-2\cdot7\\ &=3\cdot26-11\cdot7. \end{aligned}

因此

-11\cdot7\equiv1\pmod{26}.

$-11$ 的标准非负代表是 $15$ ，所以

7^{-1}\equiv15\pmod{26}.

检查：

7\cdot15=105=4\cdot26+1.

求解一次同余方程

要解

7x\equiv5\pmod{26},

在两边乘以逆元 $15$ ：

x\equiv15\cdot5=75\equiv23\pmod{26}.

这个过程很像普通除法，但它之所以可行，是因为 $7$ 与 $26$ 互素。

更一般地，同余方程 $ax\equiv b\pmod n$ 有解，当且仅当

\gcd(a,n)\mid b.

这正是第 8.2 节线性组合判据的模运算形式。

合并多条余数条件

假设一个整数要同时满足三个时钟：

x\equiv2\pmod3,

x\equiv3\pmod5,

以及

x\equiv2\pmod7.

模数 $3,5,7$ 两两互素：任意两个不同模数的最大公约数都是 $1$ 。

中国剩余定理说明：若系统

x\equiv a_i\pmod{n_i} \qquad(1\le i\le k)

的正模数两两互素，那么它在模

N=\prod_{i=1}^{k}n_i

意义下恰有一个解。

“模 $N$ 意义下恰有一个”表示所有整数解都属于同一个剩余类 $x_0+Nt$ 。

构造中国剩余定理解

对每条同余式定义

N_i=\frac{N}{n_i}.

由于各模数两两互素，

\gcd(N_i,n_i)=1,

所以 $N_i$ 模 $n_i$ 存在逆元 $y_i$ ：

N_i y_i\equiv1\pmod{n_i}.

最终

x\equiv\sum_{i=1}^{k}a_iN_i y_i\pmod N.

每个乘积 $N_i y_i$ 都像一个选择器：在时钟 $n_i$ 上等于 $1$ ，在其他时钟上则因为包含相应模数因子而等于 $0$ 。

完整计算示例

这里

N=3\cdot5\cdot7=105.

对模 $3$ ， $N_1=35$ 且 $35\equiv2\pmod3$ 。 $2$ 的逆元为 $2$ ，因为 $2\cdot2\equiv1\pmod3$ 。

对模 $5$ ， $N_2=21\equiv1\pmod5$ ，所以逆元为 $1$ 。

对模 $7$ ， $N_3=15\equiv1\pmod7$ ，所以逆元也为 $1$ 。

因此

\begin{aligned} x &\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1\\ &=233\\ &\equiv23\pmod{105}. \end{aligned}

检查三个时钟：

23\bmod3=2, \qquad 23\bmod5=3, \qquad 23\bmod7=2.

正在加载交互实验...

在两到三个独立循环信标上设置目标余数，再沿同一条整数时间线扫描，直到全部信号对齐。你可以在枚举模式与构造选择器模式之间切换，既观察解为什么以互素模数的乘积为周期重复，也看到中国剩余定理怎样直接构造答案。

正在加载概念检查...

正在加载本节练习...

注意

同余按照余数给整数分类；模除法需要互素条件下的逆元；中国剩余定理则把两两互素的多条余数条件合并成模乘积意义下唯一的一类。

本节衔接

现在我们已经能够在有限剩余系统中进行乘法与幂运算，通过贝祖系数寻找逆元，并通过中国剩余定理合并同余条件。第 8.4 节将把这些工具组装成一个小型 RSA 公钥系统。

8.3 模运算、逆元与中国剩余定理

第 8.2 节不断使用余数缩小最大公约数问题。模运算换了一个观察角度：余数不再只是临时产生的副产品，我们要把余数相同的全部整数归为一类。

这样就能把无限多个整数压缩成一个有限的运算系统。

同余表示属于相同余数类

固定一个正整数 $n$ ，称为模数。对整数 $a,b$ ，如果

n\mid(a-b),

就写作

a\equiv b\pmod n,

读作“ $a$ 与 $b$ 模 $n$ 同余”。

等价地说， $a$ 与 $b$ 除以 $n$ 后得到相同余数。

模 $5$ 的例子

因为

17-2=15=5\cdot3,

所以

17\equiv2\pmod5.

两者除以 $5$ 后的余数都是 $2$ 。

负整数也属于余数类。因为

-3-2=-5,

所以

-3\equiv2\pmod5.

符号 $=$ 仍然表示普通相等。同余是另一种关系：虽然 $17\ne2$ ，但 $17\equiv2\pmod5$ 。

剩余与剩余类

每个整数都恰好与下面集合中的一个元素模 $n$ 同余：

\{0,1,2,\ldots,n-1\}.

这些标准代表叫作模 $n$ 的剩余。

模 $5$ 时， $2$ 所在的剩余类包含

\ldots,-8,-3,2,7,12,17,\ldots

因为相邻两项相差 $5$ 。

同余是第 4 章学习过的等价关系：

$a\equiv a\pmod n$ ；

若 $a\equiv b\pmod n$ ，则 $b\equiv a\pmod n$ ；

若 $a\equiv b\pmod n$ 且 $b\equiv c\pmod n$ ，则 $a\equiv c\pmod n$ 。

因此，同余把 $\mathbb Z$ 划分成 $n$ 个互不相交的剩余类。

加法与乘法保持同余

假设

a\equiv b\pmod n \qquad\text{且}\qquad c\equiv d\pmod n.

那么

a+c\equiv b+d\pmod n

以及

ac\equiv bd\pmod n.

对加法，

(a+c)-(b+d)=(a-b)+(c-d),

右侧能够被 $n$ 整除。

对乘法，把差改写为

ac-bd=c(a-b)+b(c-d).

右侧两项都能被 $n$ 整除，所以它们的和也能被 $n$ 整除。

因此，我们既可以在运算前取余，也可以在运算后取余。

例子：缩小一个大乘积

计算 $38\cdot47\pmod7$ 。

先分别缩小因子：

38\equiv3\pmod7, \qquad 47\equiv5\pmod7.

于是

38\cdot47\equiv3\cdot5=15\equiv1\pmod7.

整个过程不需要真的计算大乘积。

幂也可以不断取余

同余乘法可以反复使用。例如，

7\equiv2\pmod5,

所以

7^4\equiv2^4=16\equiv1\pmod5.

面对很大的指数时，可以使用重复平方，并对底数和每个中间平方及时取余。第 8.4 节会把这种方法用于 RSA。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

模逆元撤销乘法

在普通有理数中，乘以非零数 $a$ 可以通过乘以 $1/a$ 撤销。在模运算中，只有找到合适的剩余，才能进行类似的“除法”。

如果整数 $x$ 满足

ax\equiv1\pmod n,

就称 $x$ 是 $a$ 模 $n$ 的乘法逆元。

也可以写作

x\equiv a^{-1}\pmod n.

这里的 $a^{-1}$ 表示模逆元，不是实数分数 $1/a$ 。

逆元什么时候存在

逆元存在，当且仅当

\gcd(a,n)=1.

最大公约数为 $1$ 的两个整数叫作互素。

若 $\gcd(a,n)=1$ ，贝祖等式给出整数 $x,y$ ，使得

ax+ny=1.

模 $n$ 取余后， $ny$ 这一整倍数消失，得到

ax\equiv1\pmod n.

所以 $a$ 的贝祖系数就是一个逆元。

反过来，若 $ax\equiv1\pmod n$ ，则 $ax-1$ 能被 $n$ 整除。因此存在整数 $y$ ，满足

ax+ny=1.

$a,n$ 的任意公因数都必须整除 $1$ ，所以最大公约数只能是 $1$ 。

用扩展欧几里得算法寻找逆元

求 $7$ 模 $26$ 的逆元。

欧几里得算法给出

\begin{aligned} 26&=3\cdot7+5,\\ 7&=1\cdot5+2,\\ 5&=2\cdot2+1. \end{aligned}

反向代入：

\begin{aligned} 1 &=5-2\cdot2\\ &=5-2(7-5)\\ &=3\cdot5-2\cdot7\\ &=3(26-3\cdot7)-2\cdot7\\ &=3\cdot26-11\cdot7. \end{aligned}

因此

-11\cdot7\equiv1\pmod{26}.

$-11$ 的标准非负代表是 $15$ ，所以

7^{-1}\equiv15\pmod{26}.

检查：

7\cdot15=105=4\cdot26+1.

求解一次同余方程

要解

7x\equiv5\pmod{26},

在两边乘以逆元 $15$ ：

x\equiv15\cdot5=75\equiv23\pmod{26}.

这个过程很像普通除法，但它之所以可行，是因为 $7$ 与 $26$ 互素。

更一般地，同余方程 $ax\equiv b\pmod n$ 有解，当且仅当

\gcd(a,n)\mid b.

这正是第 8.2 节线性组合判据的模运算形式。

合并多条余数条件

假设一个整数要同时满足三个时钟：

x\equiv2\pmod3,

x\equiv3\pmod5,

以及

x\equiv2\pmod7.

模数 $3,5,7$ 两两互素：任意两个不同模数的最大公约数都是 $1$ 。

中国剩余定理说明：若系统

x\equiv a_i\pmod{n_i} \qquad(1\le i\le k)

的正模数两两互素，那么它在模

N=\prod_{i=1}^{k}n_i

意义下恰有一个解。

“模 $N$ 意义下恰有一个”表示所有整数解都属于同一个剩余类 $x_0+Nt$ 。

构造中国剩余定理解

对每条同余式定义

N_i=\frac{N}{n_i}.

由于各模数两两互素，

\gcd(N_i,n_i)=1,

所以 $N_i$ 模 $n_i$ 存在逆元 $y_i$ ：

N_i y_i\equiv1\pmod{n_i}.

最终

x\equiv\sum_{i=1}^{k}a_iN_i y_i\pmod N.

每个乘积 $N_i y_i$ 都像一个选择器：在时钟 $n_i$ 上等于 $1$ ，在其他时钟上则因为包含相应模数因子而等于 $0$ 。

完整计算示例

这里

N=3\cdot5\cdot7=105.

对模 $3$ ， $N_1=35$ 且 $35\equiv2\pmod3$ 。 $2$ 的逆元为 $2$ ，因为 $2\cdot2\equiv1\pmod3$ 。

对模 $5$ ， $N_2=21\equiv1\pmod5$ ，所以逆元为 $1$ 。

对模 $7$ ， $N_3=15\equiv1\pmod7$ ，所以逆元也为 $1$ 。

因此

\begin{aligned} x &\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1\\ &=233\\ &\equiv23\pmod{105}. \end{aligned}

检查三个时钟：

23\bmod3=2, \qquad 23\bmod5=3, \qquad 23\bmod7=2.

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

同余按照余数给整数分类；模除法需要互素条件下的逆元；中国剩余定理则把两两互素的多条余数条件合并成模乘积意义下唯一的一类。

8.3 模运算、逆元与中国剩余定理

8.3 模运算、逆元与中国剩余定理

同余表示属于相同余数类

模 555 的例子

剩余与剩余类

加法与乘法保持同余

例子：缩小一个大乘积

幂也可以不断取余

模逆元撤销乘法

逆元什么时候存在

用扩展欧几里得算法寻找逆元

求解一次同余方程

合并多条余数条件

构造中国剩余定理解

完整计算示例

本节衔接

8.3 模运算、逆元与中国剩余定理

8.3 模运算、逆元与中国剩余定理

同余表示属于相同余数类

模 555 的例子

剩余与剩余类

加法与乘法保持同余

例子：缩小一个大乘积

幂也可以不断取余

模逆元撤销乘法

逆元什么时候存在

用扩展欧几里得算法寻找逆元

求解一次同余方程

合并多条余数条件

构造中国剩余定理解

完整计算示例

本节衔接

模 $5$ 的例子

模 $5$ 的例子