Note: This article is available in Chinese only. 本文暂无英文版本。
View original
前置技能点：
对任何整数
， 和它们的最大公约数 ，关于未知数 和 的线性丢番图方程（称为裴蜀等式）： 有整数解时当且仅当_m_是_d_的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解
、 都称为裴蜀数，可用扩展欧几里得算法求得。 特别地，方程
有整数解当且仅当整数_a_和_b_互素。（kk:因为1(m=1)只可能是1(d=1)的倍数，也就是说gcd(a,b)=1，即a,b互质）
已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式
通常谈到[最大公约数](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)的整数解。
例子：
求二元一次不定方程
的整数解。
- 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。
1int exgcd(int a,int b,int &x,int &y)
2{
3 if(b==0)
4 {
5 x=1;
6 y=0;
7 return a;
8 }
9 int ret=exgcd(b,a%b,x,y);
10 int tmp=x;
11 x=y;
12 y=tmp-a/b*y;
13 return ret;
14}用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
有解的判定条件，并用**构造法**给出了在有解情况下解的具体形式。
重点是：中国剩余定理是一种构造法。