挑战≈ 16 分钟未开始

中国剩余定理

核心概念

中国剩余定理(CRT):设 $m_1, m_2, \dots, m_k$ 两两互质,则同余方程组

x \equiv a_1 \pmod{m_1},\quad x \equiv a_2 \pmod{m_2},\quad \dots,\quad x \equiv a_k \pmod{m_k}

有唯一的解(模 $M = m_1 m_2 \cdots m_k$ ),即在 $0$ 到 $M-1$ 中恰有一个解。

初等解法:从模数最大的一条同余出发,写出通项 $x = m_k t + a_k$ ,代入下一条同余求出 $t$ 的限制,逐步缩小,直到满足全部条件。

中国剩余定理来源于古代"韩信点兵":知道一队士兵分别按 $3$ 、 $5$ 、 $7$ 报数的余数,就能推出总人数(在一个范围内唯一)。它的深刻之处是:两两互质的几个余数,合起来恰好唯一地锁定一个数(模它们的乘积)。

为什么唯一?因为若有两个解 $x,x'$ ,它们的差 $x-x'$ 同时被每个 $m_i$ 整除;由两两互质,差就被乘积 $M$ 整除,故模 $M$ 下只有一个解。解题时不必背公式,用"逐步代入"——先满足一条,再把通解代入下一条——既稳妥又不易错。

中国剩余定理

在 0 ~ 14 中唯一同时满足两条的是 x = 8, 即 x ≡ 8 (mod 15)。

余数 a₁ (mod 3)2

余数 a₂ (mod 5)3

黄色满足其中一条,绿色同时满足两条。因为 3、5 互质,0~14 中恰有唯一解——这就是中国剩余定理。

例题 1两条同余

解 $\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \end{cases}$ 。

▸查看解答步骤

答: x ≡ 8 (mod 15)

例题 2韩信点兵

解 $x\equiv1\pmod2,\ x\equiv2\pmod3,\ x\equiv3\pmod5$ 。

▸查看解答步骤

答: x ≡ 23 (mod 30)

满足 $x\equiv2\pmod3$ 且 $x\equiv3\pmod5$ 的最小正整数是多少?

$x\equiv8\pmod{15}$ ,最小正整数为 $8$ 。

满足 $x\equiv1\pmod2$ 且 $x\equiv2\pmod3$ 的最小正整数是多少?

$x\equiv5\pmod6$ ,最小正整数为 $5$ 。

满足 $x\equiv1\pmod2,\ x\equiv2\pmod3,\ x\equiv3\pmod5$ 的最小正整数是多少?

$x\equiv23\pmod{30}$ ,最小正整数为 $23$ 。

方程组 $x\equiv2\pmod3,\ x\equiv3\pmod5$ 的解的周期(模数)是多少?

两两互质,周期为 $3\times5 = 15$ 。

前置知识点

接下来学习