同余

定义

如果a,b除以c的余数相同，就说a和b关于模c同余记作a≡b(mod c)

还可以这样理解 $a-b=t$，若$t|c$（表示t可以被c整除），则$a\equiv b(modc)$

性质

同余关系是一种等价关系。

1.自反性：一个数永远和自己本身同余 a≡a(mod)

2.对称性：a和b同余，b也就同余a,即 a≡b(mod m)等价于b≡a(mod m)

3.传递性：a和b同余，b和c也同余，可以推出a和c也是同余的

运算

加减法

若 a≡b(mod m)，x≡y(mod m)则有，a+x≡b+y(mod m) 证明： 根据定义，若 a≡b(mod m)则可以总可找到k1,k2满足 ：a+k1*m=b+k2*m 同理，对于x≡y(mod m)，也总可找到k3,k4满足：x+k3*m+y+k4*m 等式两边分别相加有

$(a+x)+m\ast (k1+k3)=(b+y)+m\ast (k2+k4)$ 两边同时取模m即得到 a+x≡b+y(mod m)

乘法

若 a≡b(mod m)，x≡y(mod m)则有，ax≡by(mod m) 证明与加法相似(略)

一个特殊的？除法？

如果ac≡bc(mod m),且c和m互质，则有a≡b(mod m)(就是说同余式两边可 以同时除以一个和模数互质的数)。 证明： 对于ac≡bc(mod m)，我们总可以找到k1,k2使得 $ac+k1\ast m=bc+k2\ast m$ 移项有$c\ast (a-b)=m\ast (k2-k1)$ $c\ast (a-b)/m=(k2-k1)$ 所以，可知，$c\ast (a-b)|m$ 又因为c与m是互质(互素)的，因此，$(a-b)|m$ 所以得到 $a\equiv b(modm)$

线性同余方程

给出a,b,m，求一整数x满足 a*x≡b（mod m） ，或给出无解 因为未知数的次数为1，所以我们称之为线性同余方程。 根据同余的定义，该式子等价于$a\ast x\%m=b$ 也就是说，$a\ast x-b$是m的倍数 那么不妨设 $ax-b=-my$ 即 ax+my=b 根据裴蜀定理及扩欧定理(exgcd)求解可得到任一特解 设特解为$x_0$，则其通解可以表示为 $\{x_0+k\frac{m}{d}\mid k\in Z\}$其中$d=gcd(a,m)$

推论：其最小正整数可表示为$(x_0\%(\frac{m}{d})+\frac{m}{d})\%(\frac{m}{d})$

裴蜀（贝祖Bezout）定理

定理： 对于给定的正整数a，b方程ax+by=c有解的充要条件为： c=k*gcd（a，b），k∈Z（c | gcd(a,b)）

证明：

https://blog.csdn.net/a_forever_dream/article/details/83859354

推论：

a,b 互质的冲要条件是，ax+by=1 整数解对于n元不定方程: $a_1{x}_1+a_2{x}_2+a_3{x}_3+\dots \dots +a_n{x}_n=m$当且仅当 $gcd(a_1,a_2,a_3,a_4,\dots \dots ，a_n)|m$时有整数解$a_1,a_2,a_3,a_4,\dots \dots ，a_n$互质的充要条件是 方程$a_1{x}_1+a_2{x}_2+a_3{x}_3+\dots \dots +a_n{x}_n=m$有整数解

扩欧定理

扩欧定理可以求解形如 $ax+by=c$,($c|gcd(a,b)$)，其求解过程就是不断递归的求解gcd(a,b)同时操作两个未知量x和y的值，当求解出gcd(a,b)时，即可回溯推出x,y，这里求出的x，y是一组特解。

typedef long long LL; LL exgcd(LL a, LL b, LL& x, LL& y) { if (b == 0) { x = 1; y = 0; return a; } LL r = exgcd(b, a % b, x, y); LL t = x; x = y; y = t - a / b * y; return r; } 注意到： 实际求解的x，y实际上是方程$ax+by=gcd(a,b)$的解，因此在必要时要乘$c/gcd(a,b)$获得符合条件的解 在函数参数部分，x和y使用传址是为了直接对传入的变量进行操作。 根据前面的同余部分知识，我们可以最小正整数化x和y 即

$[x\%\frac{c}{gcd(a,b)}+\frac{c}{gcd(a,b)}]\%\frac{c}{gcd(a,b)}$ $[y\%\frac{c}{gcd(a,b)}+\frac{c}{gcd(a,b)}]\%\frac{c}{gcd(a,b)}$ 这种最小正整数化的思想也可以用在其他取模操作上可以避免在取模的过程中出现负数等情况。

线性同余方程组

顾名思义我们这次要求解一组线性同余方程

$x\equiv b_1(mod{m}_1)$ $x\equiv b_2(mod{m}_2)$ $x\equiv b_3(mod{m}_3)$ $x\equiv b_4(mod{m}_4)$ …… $x\equiv b_n(mod{m}_n)$

这种方程有两种常见的样式 ① $m_1,m_2,m_3\dots \dots m_n$是两两互质 ② $m_1,m_2,m_3\dots \dots m_n$不一定满足互质

中国剩余定理求解（CRT）

对于①可以用中国剩余定理求解

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：

找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数

用数学语言来说，这个问题解法的本质是从5和7的公倍数中找一个除以3余2的数$n_1$，从3和7的公倍数中找一个除以5余3的数$n_2$，从3和5的公倍数中找一个除以7余2的数$n_3$，再将三个数相加得到解。在求$n_1$，$n_2$，$n_3$时又用了一个小技巧，以$n_1$为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。 最后，我们还要清楚一点，n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉掉3，5，7的公倍数105即可。 于是中国剩余定理的公式就出来了 设有正整数$m_1,m_2,m_3\dots \dots m_n$两两互质，则方程组 $x\equiv b_1(mod{m}_1)$ $x\equiv b_2(mod{m}_2)$ $x\equiv b_3(mod{m}_3)$ $x\equiv b_4(mod{m}_4)$ 有整数解，并且在模$M=m_1\ast m_2\ast m_3\ast \dots \dots \ast m_n$下解是唯一的。 其解为 $x\equiv (b_1\ast M_1\ast M_1^{-1}+b_2\ast M_2\ast M_2^{-1}+b_3\ast M_3\ast M_3^{-1}+\dots \dots +b_n\ast M_n\ast M_n^{-1})modM$ 其中$M_i=M/m_i$,$M_i^{-1}是M_i取模m_i的逆元$ 补充两个求逆元的常用方法

费马小定理求逆元

费马小定理描述如下 $a^{p-1}\equiv 1(modp)$当且仅当p为质数（素数）的时候成立 所以有推论： $a\ast a^{p-2}\equiv 1(modp)$ 所以$a^{-1}=a^{p-2}$,用快速幂可解

扩欧定理求逆元

设$a^{-1}=x$，则有$a\ast x\equiv 1(modp)$ 根据同余的定义，可转化为下式： $a\ast x+p\ast y=1$ 直接带入exgcd算法即可求解 注意：这里实际求解的是二元方程①$a\ast x+p\ast y=gcd(a,p)$①所对应的解X。因此$a\ast x+p\ast y=1$中的x应该为$X/gcd(a,p)$

LL CRT(LL b[], LL m[], int n)//b是余数，m是模 { LL M = 0, tx, ty, x = 0; for (int i = 1; i <= n; ++i) { M *= m[i]; } for (int i = 1; i <= n; ++i) { LL Mi = M / m[i]; LL t = exgcd(Mi, m[i], tx, ty); x = (x + Mi*b[i] / t * x) % M; } return x; }

扩展中国剩余定理（EX_CRT）

对于②需要合并方程然后用扩欧定理求解 因为不满足互素的条件，所以中国剩余定理在这里并不适用。因此我们需要合并方程来减少方程数量并适用扩欧定理求解。 我们先拿出前两个方程 $x\equiv b_1(mod{m}_1)$ $x\equiv b_2(mod{m}_2)$ 根据定义，我们可以将两式分别转化为如下形式 $x=b_1+k_1\ast m_1$ $x=b_2+k_2\ast m_2$ 联立两式移项 $k_1\ast m_1-(b_2-b_1)=k_2\ast m_2$ 令$d=gcd(m1,m2)$两边同时除d 得到$\frac{k_1\ast m_1}{d}-\frac{b_2-b_1}{d}=\frac{k_2\ast m_2}{d}$ 两边同时取模$k_2\ast m_2$ 得到$k_1\equiv \frac{b_2-b_1}{m1}(mod\frac{m_2}{d})$ 则必然存在一最小$T$满足$T\equiv \frac{b_2-b_1}{m1}(mod\frac{m_2}{d})$使得$k_1\equiv T(mod\frac{m_2}{d})$ 带入$x=b_1+k_1\ast m_1$得到 $x=b_1+m_1\ast (T+\frac{m_2}{d}\ast C)$(C是任意整数) $x=b_1+m_1\ast T+\frac{m_2\ast m_1}{d}\ast C$

$x\equiv (b_1+m_1\ast T)(mod\frac{m_2\ast m_1}{d})$ ① 由$k_1\ast m_1-k_2\ast m_2=(b_2-b_1)$可由扩欧定理解出k1 注:这里实际计算的是$k_1\ast m_1-k_2\ast m_2=gcd(k1,k2)$，因此在使用$k_1$时需要乘上$(b_2-b_1)/gcd(b_1,b_2)$ 根据刚刚算出的$k_1\equiv T(mod\frac{m_2}{d})$由于同余的等价性，有$T\equiv k_1(mod\frac{m_2}{d})$ 则可最小化$T=(k_1\%\frac{m_2}{d}+\frac{m_2}{d})\%\frac{m_2}{d}$

对比①式有 $b_1=b_1+m_1\ast T$ $m_1=\frac{m_1\ast m_2}{d}$(实际运算的时候先乘后除较优) 这样操作一遍，我们合并了$x\equiv b_1(mod{m}_1)$与$x\equiv b_2(mod{m}_2)$两个式子 这样依次迭代下去，最后得到的b1就是方程组的最小非负数解

代码 若输入的数据有无解的情况，返回-1，否则返回最小正整数解

//x=b1(mod m1) LL ex_CRT(LL b[], LL m[], int n)//从1~n { LL m1, m2, b1, b2, x0, y0, aa, bb, c, d; b1 = b[1], m1 = m[1]; bool fl = 1; for (int i = 2; i <= n; ++i) { m2 = m[i], b2 = b[i]; aa = m1; bb = m2; c = b2 - b1; d = exgcd(aa, bb, x0, y0); if (c % d) { fl = 0; break; } LL t = bb / d; x0 = (x0 * (c / d) % t + t) % t; b1 = b1 + m1 * x0; m1 = m1 / d * m2; } if (fl) { return b1; } else { return -1; } }

求线性同余方程组小于N的解的个数

这个问题与同余方程组的通解有关。

我们通过CRT及EX_CRT两个算法求出来的一般都是最小非负整数解（不是的话也得化成最非负整数解），设该解为$x_0$，不论是那种算法，$x_0$一定是由模$LCM(m_1,m_2,\dots \dots m_n)$得到的。（加LCM是为了包含EX_CRT中模数不满足两两互素的情况，其实与CRT算法中的M是同一意义。）

根据同余的定义，所有的正整数解可以表示为 $x=x_0+k\ast lcm$，(设$lcm=LCM(m_1,m_2,\dots \dots m_n)$) 那么小于n的解的个数一定是$ans=1+(n-x_0)/lcm$，其实就是在求有多少个k满足$x<n$，最后把本身加上。在这里要特别注意题目要求，有的题目要求非负数，有的题目要求正整数。这就要特判一下$x_0=0$的情况。