数论（11 Mai, 2019）

算法

扩展gcd

通过辗转相除求出$ax+by=$$\rm{\rm{gcd}}$$(a,\ b)$的不定方程特解。
设$c=\rm{\rm{gcd}}(a,\ b)$，则$a=k_1c$，$b=k_2c$。由于

$$\begin{aligned} a\ \%\ b&=a-k_3b \\ &=k_1c-k_3k_2c \\ &=c(k_1-k_3k_2) \end{aligned}$$ ，所以$\rm{\rm{gcd}}$$(b, a\ \%\ b)=c=\rm{\rm{gcd}}$$(a,\ b)$。
$$\left\{ \begin{aligned} &ax+by=c\\ &bx_1+(a\ \%\ b)y_1=c \end{aligned} \right.$$ ，两式联立得 $$ax+by=bx_1+(a\ \%\ b)y_1$$ 。设$k=\lfloor \frac{a}{b}\rfloor y_1$，则 $$ax+by=bx_1+(a-kb)y_1\\ax+by=ay_1+b(x_1-ky_1)$$ ，所以 $$x=y_1\\y=x_1-\lfloor \frac{a}{b}\rfloor y_1$$ 。在辗转相除的过程中，按照这样的过程一层层向上返回$x_1$和$y_1$，最终得到一组特解$x_0$和$y_0$。显然有 $$a(x+\frac{b}{c}t)+b(y-\frac{a}{c}t)=ax+by$$ ，所以通解为$x=x_0+\frac{b}{c}t$，$y=y_0-\frac{a}{b}t$。通过枚举$t$可以得到目标解。

线性同余方程

设$d=\rm{gcd}$$(a,\ b)$。
对于任意满足$c\ \%\ d=0$方程$ax+by=c$，可以转化为可以用扩展$gcd$求解的情况。
设$a'=\frac{a}{d}$，$b'=\frac{b}{d}$，$c'=\frac{c}{d}$。
可以发现

$$a'x+b'y=\frac{a}{d}x+\frac{b}{d}y=1\\ax+by=d=\frac{c}{c'}\\a(c'x)+b(c'y)=a(\frac{c}{d}x)+b(\frac{c}{d}y)=c$$ 。用扩展$gcd$求解$a'x+b'y=1$的特解$x'_0$，$y'_0$，则$x_0=\frac{c}{d}x'_0$，$y_0=\frac{c}{d}y'_0$。显然有 $$a(x+\frac{b}{d}t)+b(y-\frac{a}{d}t)=c$$ ，通解推法与扩展$gcd$中相同，可以理解为从直线$ax+by=d$变成$ax+by=c$，截距变化，但是斜率不会因常数的变化而变化。

乘法逆元

若$ax\ \%\ p=1$，则$x$是$a$关于$p$的乘法逆元。
存在乘法逆元的充要条件是$\rm{gcd}$$(a,\ p)=1$。
求证：若$bx\ \%\ p=1$且$a\ \%\ b=0$，则$\frac{a}{b}\ \%\ p = ax\ \%\ p$。
证明：由$bx\ \%\ p=1$可知$bx=py+1$，则$x=\frac{py+1}{b}$，代入得

$$\begin{aligned} ax\ \%\ p &= a\frac{py+1}{b}\ \%\ p\\ &= (a\frac{py}{b}+\frac{a}{b})\ \%\ p\\ &= (p\frac{ay}{b}+\frac{a}{b})\ \%\ p\\ &= p\frac{ay}{b}\ \%\ p+\frac{a}{b}\ \%\ p\\ &= \frac{a}{b}\ \%\ p \end{aligned}$$
求法很显然是解$bx+py=1$的同余方程。根据同余方程调根法，相邻整数根间距为$\frac{p}{gcd(b,\ p)}$。由于当$\rm{gcd}$$(b,\ p)!=1$时不存在乘法逆元，所以相邻整数根的间距为$p$。所以当$t=1$时，通过$x=(x\ \%\ p + p)\ \%\ p$，调到最小正整数。