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

Oct 11, 2016 · 2 min read · number theory 中国剩余定理扩展欧几里得算法裴蜀定理

前置技能点：

对任何[整数](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_的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 $x$ 、 $y$ 都称为裴蜀数，可用扩展欧几里得算法求得。

特别地，方程 $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.$

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

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