初等数论（exgcd & 中国剩余定理 & 卢卡斯定理）

〇、整除

定义 $b\mid a\iff amodb=0$。

1. 求证：$c\mid a$ 且 $c\mid b\Rightarrow c\mid (a+b),c\mid ab$。

证明：设 $a=k_{1}c,b=k_{2}c,\therefore a+b=c(k_1+k_2),ab=c^2{k}_1{k}_2$。

一、辗转相除法

1. 求证：$gcd(a,b)=gcd(b,amodb)$。

证明：设 $amodb=c$，即 $a=kb+c$。

$\therefore c=a-kb$。

设 $d\mid a,d\mid b$。

$\therefore d\mid kb$，$\therefore d\mid c$。

$\therefore a,b$ 的公因数，均为 $amodb$ 的因数，即均为 $b,amodb$ 的公因数。

设 $d^{\prime }\mid b,d^{\prime }\mid c$。

$\therefore d^{\prime }\mid kb$，$\therefore d^{\prime }\mid a$。

$\therefore b,amodb$ 的公因数，均为 $a$ 的因数，即均为 $a,b$ 的公因数。

$\therefore gcd(a,b)=gcd(b,amodb)$。

二、裴蜀定理

1. 求证：$ax+by=gcd(a,b)$ 有整数解。

证明：https://oi-wiki.org/math/number-theory/bezouts/。

三、exgcd

1. 求 $ax+by=gcd(a,b)$ 的一组整数解。

解：设已知 $b{x}^{\prime }+(amodb)y^{\prime }=gcd(b,amodb)$ 的一组整数解 $x^{\prime },y^{\prime }$。

$\because gcd(a,b)=gcd(b,amodb)$，

$\therefore ax+by=b{x}^{\prime }+(amodb)\times y^{\prime }$。

$\therefore ax+by=b{x}^{\prime }+(a-\lfloor \frac{a}{b}\rfloor \times b)\times y^{\prime }$。

$\therefore ax+by=a{y}^{\prime }+b(x^{\prime }-\lfloor \frac{a}{b}\rfloor \times y^{\prime })$。

2. 若 $a,b$ 互质，求 $a$ 在模 $b$ 意义下的逆元 $x$，即求 $ax\equiv 1(\mathrm{mod}b)$ 的一个解。

解：原方程等价于 $ax+by=1$，其中 $y<0$。

而 $gcd(a,b)=1$，所以 exgcd 可求。

3. 求证：$ax+by=c$ 有整数解 $\iff gcd(a,b)\mid c$。

证明：

①充分性：设 $d=gcd(a,b)$，则 $a=k_{1}d,b=k_{2}d$。

$\therefore c=ax+by=d(k_{1}x+k_{2}y)$。

$\therefore d\mid c$。

②必要性：$\because$ 由裴蜀定理，$ax+by=d$ 有整数解。

$\therefore a\times \frac{cx}{d}+b\times \frac{cy}{d}=c$。

$\because d\mid c$，$\therefore \frac{cx}{d},\frac{cy}{d}$ 是整数。

4. 若 $ax+by=c$ 有解：

（1）求其的一组特解 $x^{\prime },y^{\prime }$。

解：由 exgcd 易求 $ax+by=gcd(a,b)$ 的一组解 $x_0,y_0$。

$\because ax+by=c$ 有解，$\therefore gcd(a,b)\mid c$。

$\therefore a\times \frac{c{x}_0}{gcd(a,b)}+b\times \frac{c{y}_0}{gcd(a,b)}=c$

$\therefore$ 解得 $\{\begin{array}{c}{x}^{\prime }=\frac{c{x}_0}{gcd(a,b)}\\ y^{\prime }=\frac{c{y}_0}{gcd(a,b)}\end{array}$。

（2）求其的通解公式。

解：设 $a(x+m)+b(y+n)=c$，化简得 $am+bn=0$。

设 $d=gcd(a,b)$。易得 $\{\begin{array}{c}m=k\times \frac{b}{d}\\ n=-k\times \frac{a}{d}\end{array}$。

（3）找出解的个数，判断是否有解满足 $x>0,y>0$。

解：即 $x^{\prime }+m>0,y^{\prime }+n>0$。

化简得 $\lceil \frac{-d{x}^{\prime }+1}{b}\rceil \le k\le \lfloor \frac{d{y}^{\prime }-1}{a}\rfloor$

解的个数即为 $k$ 的个数。

若 $k$ 存在，则有解满足上述条件。

（4）分别给出 $x$ 和 $y$ 最小的正整数值。

解：由一次函数，$x$ 随着 $k$ 增大而增大，$y$ 随着 $k$ 增大而减小。

四、中国剩余定理

求解以下方程组：

$$x\equiv a_i(\mathrm{mod}{b}_i)$$

有如下方法：

1. 令 $mod=\prod b_i$，令 $m_i=mod÷b_i$。

2. 求模 $b_i$ 意义下的 $m_i^{-1}$，记作 $m_i^{\prime }$。

3. 答案为 $(\sum a_i{m}_i{m}_i^{\prime })modmod$。

求证：以上方法的正确性。

证明：若 $i\ne j$，则由构造方式，有 $b_i\mid m_j$，即 $m_j=0(\mathrm{mod}{b}_i)$。

$\therefore a_j{m}_j{m}_j^{\prime }=0(\mathrm{mod}{b}_i)$。

若 $i=j$，则 $m_i{m}_i^{-1}=1(\mathrm{mod}{b}_i)$。

综上，$x\equiv \sum a_j{m}_j{m}_j^{\prime }\equiv a_i+\sum _{i\ne j}{a}_j{m}_j{m}_j^{\prime }\equiv a_i(\mathrm{mod}{b}_i)$。

五、卢卡斯定理

$$C_n^m\equiv C_{\lfloor n÷p\rfloor }^{\lfloor m÷p\rfloor }\times C_{nmodp}^{mmodp}(\mathrm{mod}p)$$

适用于 $n,m$ 较大，$p$ 较小的情况。

注意预处理阶乘数组只能处理到 $<p$ 的地方，不然将会导致答案全是 $0$。