CPC 算法笔记——中国剩余定理

1 min432 words
Legacy
Contents

中国剩余定理可用于解一元线性方程组：

{x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn)\begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \quad \vdots\\ x \equiv a_n \pmod {m_n} \end{cases}

模数两两互质的情形

令 M=∏i=1nmi, Mi=Mmi, ti=Mi−1M = \prod\limits_{i=1}^{n} m_i,\ M_i = \frac{M}{m_i},\ t_i = M_i^{-1}（模 mim_i 意义下），则可构造通解：

xS=∑i=1naitiMi+kM, k∈Zx_S = \sum_{i=1}^{n} a_it_iM_i + kM,\ k \in \mathbb{Z}

证明

由假设，∀j∈{1,2,…,n}, gcd⁡(mi,Mi)=1\forall j \in \{1, 2, \dots, n\},\ \gcd(m_i, M_i) = 1，则由 Bezout 定理可推知，∃ti s.t. tiMi≡1(modmi)\exists t_i \text{ s.t. } t_iM_i \equiv 1 \pmod {m_i}，即 MiM_i 存在模 mim_i 意义下的数论倒数 tit_i。

考虑乘积 aitiMia_it_iM_i 可知：aitiMi≡ai(modmi); a_it_iM_i \equiv a_i \pmod {m_i};\ ajtjMj≡0(modmi),a_jt_jM_j \equiv 0 \pmod {m_i}, ∀j∈{1,2,…,n},j≠i\forall j \in \{1, 2, \dots, n\}, j \neq i，所以令 x=∑i=1naitiMix = \sum\limits_{i=1}^{n} a_it_iM_i，则有 x≡ai(modmi),∀i∈{1,2,…,n}x \equiv a_i \pmod {m_i}, \forall i \in \{1, 2, \dots, n\}。

假设 x1,x2x_1, x_2 为该方程的两个解，由于模数两两互质，有 M∣(x1−x2)M \mid (x_1-x_2)，即任意两个整数解必然相差 MM 的整数倍，故解集为 {∑i=1naitiMi+kM∣k∈Z}\{\sum\limits_{i=1}^{n} a_it_iM_i + kM \mid k \in \mathbb{Z}\}。

模数不两两互质的情形

方法一：转化为模数互质

先提出以下引理1：

引理 1 方程组有解的充要条件是 ∀i,j∈{1,2,…,n},i≠j, \forall i, j \in \{1, 2, \dots, n\}, i \neq j,\ gcd⁡(mi,mj)∣(bi−bj)\gcd(m_i, m_j) \mid (b_i-b_j)。

证明

考虑将

{x≡a1(modm1)x≡a2(modm2)\begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2} \end{cases}

转化为不定方程组：

{x=pm1+a1x=qm2+a2\begin{cases} x = pm_1 + a_1\\ x = qm_2 + a_2 \end{cases}

两式相减得：

pm1−qm2=a1−a2pm_1 - qm_2 = a_1 - a_2

若方程有解，由 Bezout 定理知，gcd⁡(mi,mj)∣(ai−aj)\gcd(m_i, m_j) \mid (a_i - a_j)，以此类推可证必要性。充分性同理。

引理 2 设 mm 为正整数，对其质因数分解得 m=∏i=1αpieim = \prod\limits_{i=1}^{\alpha} p_i^{e_i}，则方程 x≡a(modm)x \equiv a \pmod m 等价于方程组

{x≡a(modp1e1)x≡a(modp2e2)⋮x≡a(modpαeα)\begin{cases} x \equiv a \pmod {p_1^{e_1}}\\ x \equiv a \pmod {p_2^{e_2}}\\ \quad \vdots\\ x \equiv a \pmod {p_\alpha^{e_\alpha}} \end{cases}

结论显然，证明略

引理 3 设 pp 为质数，α≥β\alpha \geq \beta，则方程组

{x≡a1(modpα)x≡a2(modpβ)\begin{cases} x \equiv a_1 \pmod {p^\alpha}\\ x \equiv a_2 \pmod {p^\beta} \end{cases}

的解就是方程 x≡a1(modpα)x \equiv a_1 \pmod {p^\alpha} 的解，即在有解的条件下二者等价。

证明

若方程组有解，则 ∃k,l\exists k, l 使得：

x=a1+kpα=a1+(kpα−β)pβ=a2+lpβ\begin{align*} x = a_1 + kp^\alpha &= a_1 + (kp^{\alpha-\beta})p^\beta\\ &= a_2 + lp^\beta \end{align*}

即

a1≡a2(modp)a_1 \equiv a_2 \pmod p

故原方程组可写成：

{x≡a1(modpα)x≡a1(modpβ)\begin{cases} x \equiv a_1 \pmod {p^\alpha}\\ x \equiv a_1 \pmod {p^\beta} \end{cases}

该方程组的解显然是 x≡a1(modpα)x \equiv a_1 \pmod {p^\alpha} 的解，即二者等价。

利用以上三个引理，可以将原方程组转化为模数为素数乘方的方程组，若不存在矛盾的方程，则可用中国剩余定理求解。

方法二：两两合并法

由引理 1 的证明，若方程组有解，对前两个方程，可由扩展 Euclid 算法解得 p,qp, q 使得 pm1−qm2=a1−a2pm_1 - qm_2 = a_1 - a_2，则两个方程等价于

x≡pm1+a1(modlcm(m1,m2))x \equiv pm_1+a_1 \pmod {\mathrm{lcm}(m_1, m_2)}

或

x≡qm2+a2(modlcm(m1,m2))x \equiv qm_2+a_2 \pmod {\mathrm{lcm}(m_1, m_2)}

以此类推。

参考文献

Footnotes

  1. 刘古胜,徐东星,余畅.推广的孙子定理[J].高师理科学刊,2010,30(03):26-28. ↩

Contents