中国剩余定理(crt)学习笔记

前置技能点:

维基百科_裴蜀定理(贝祖等式)

对任何[整数](https://zh.wikipedia.org/wiki/)![a](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc) , ![b](https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3) 和它们的[最大公约数](https://zh.wikipedia.org/wiki/)![d](https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab) ,关于未知数![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4) 和![y](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d) 的[线性](https://zh.wikipedia.org/wiki/)[丢番图方程](https://zh.wikipedia.org/wiki/)(称为**裴蜀等式**):![ax+by=m](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3386cf2b30d74a8dc65ec168ef326cf2ece3de0)

有整数解时当且仅当_m_是_d_的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解 xy 都称为裴蜀数,可用扩展欧几里得算法求得。

特别地,方程 ax+by=1 有整数解当且仅当整数_a_和_b_互素。(kk:因为1(m=1)只可能是1(d=1)的倍数,也就是说gcd(a,b)=1,即a,b互质)

维基百科_扩展欧几里得算法

已知整数a、b,扩展欧几里得算法**可以在求得a、b的[最大公约数](https://zh.wikipedia.org/wiki/)的同时,能找到整数x、y**(其中一个很可能是负数),使它们满足[贝祖等式](https://zh.wikipedia.org/wiki/)
![ax + by = \gcd(a, b).](https://wikimedia.org/api/rest_v1/media/math/render/svg/72fe07a990a7ce59a499626f59b1ce588c8f6cda)
通常谈到[最大公约数](https://zh.wikipedia.org/wiki/)时,我们都会提到一个非常基本的事实:**给予二整数a、b,必存在有整数x、y使得ax + by = gcd(a,b)**[[1]](https://zh.wikipedia.org/wiki/#cite_note-1)。

有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

例子:

求二元一次不定方程 {\textstyle 47x+30y=1} 的整数解。

  * 47 = 30 * 1 + 17
  * 30 = 17 * 1 + 13
  * 17 = 13 * 1 + 4
  * 13 = 4 * 3 + 1

然后把它们改写成“余数等于”的形式

  * 17 = 47 * 1 + 30 * (-1) //式1
  * 13 = 30 * 1 + 17 * (-1) //式2
  * 4 = 17 * 1 + 13 * (-1) //式3
  * 1 = 13 * 1 + 4 * (-3)

然后把它们**“倒回去”**

  * 1 = 13 * 1 + 4 * (-3) //应用式3
  * 1 = 13 * 1 + [17 * 1 + 13 * (-1)] * (-3)
  * 1 = 13 * 4 + 17 * (-3) //应用式2
  * 1 = [30 * 1 + 17 * (-1)] * 4 + 17 * (-3)
  * 1 = 30 * 4 + 17 * (-7) //应用式1
  * 1 = 30 * 4 + [47 * 1 + 30 * (-1)] * (-7)
  * 1 = 30 * 11 + 47 * (-7)

得解x=-7, y=11。

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int ret=exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ret;
}

Acdreamer的博客_中国剩余定理

维基百科_中国剩余定理

用现代数学的语言来说明的话,中国剩余定理给出了以下的**一元线性同余方程组**:

(S) : \quad \left{ \begin{matrix} x \equiv a_1 \pmod {m_1} \ x \equiv a_2 \pmod {m_2} \ \vdots \qquad\qquad\qquad \ x \equiv a_n \pmod {m_n} \end{matrix} \right.

有解的判定条件,并用**构造法**给出了在有解情况下解的具体形式。

重点是:中国剩余定理是一种构造法。