整除与同余

标签：frac gcd 整数 ax 整除 同余 公因数

整除得到了扩展，于是便成了同余。

整除

定义及性质

若整数\(b\)除以非零整数\(a\)，商为整数，且余数为零，\(b\)为被除数，\(a\)为除数，即\(a|b\)（“|”是整除符号），读作“\(a\)整除\(b\)”或“\(b\)能被\(a\)整除”。\(a\)叫做\(b\)的约数（或因数），\(b\)叫做\(a\)的倍数。整除属于除尽的一种特殊情况。

①若\(b|a\)，\(c|a\)，且\(b\)和\(c\)互质，则\(bc|a\)。
②对任意非零整数\(a\)，\(±a|a=±1\)。
③若\(a|b\)，\(b|a\)，则\(|a|=|b|\)。
④如果\(a\)能被\(b\)整除，\(c\)是任意整数，那么积\(ac\)也能被\(b\)整除。
⑤对任意整数\(a,b>0\)，存在唯一的数对\(q,r\)，使\(a=bq+r\)，其中\(0 ≤ r < b\)。带余除法定理，是整除理论的基础。
⑥若\(c|a\)，\(c|b\)，则称\(c\)是\(a,b\)的公因数。若\(d\)是\(a,b\)的公因数，\(d≥0\)，且\(d\)可被\(a,b\)的任意公因数整除，则\(d\)是\(a,b\)的最大公因数。若\(a,b\)的最大公因数等于\(1\)，则称\(a,b\)互素，也称互质。累次利用带余除法可以求出\(a,b\)的最大公因数，这种方法常称为辗转相除法。又称欧几里得算法。
（百度百科）

欧几里德算法

用来求最大公因数（gcd），又称辗转相除法。
给定 \(a,b\in N\) ，有 \(\gcd(a,b)=\gcd(b,a\ \%\ b)\ (a\geq b)\) ，利用这个性质一直递归下去，直到 \(b'=0\) ，于是 \(a'\) 就是 \(a,b\) 的 gcd 了，因为 \(\gcd(a,0)=a\)。

裴蜀定理

\(\forall a,b \in Z\) ，一定有一组整数解使得 \(ax+by=\gcd(a,b)\)。
\(ax+by=\gcd(a,b)\) 有解 $\ \ \Leftrightarrow\ \ $ \(ax+by=m\ \ (\gcd(a,b)|m)\) 有解。
证明

扩展欧几里德算法(exgcd)

扩展欧几里得的用途

1. 判断方程\(ax+by=m\)是否有解
2. 求\(ax+by=m\)的任意一组解、通解、最小整数解
3. 求逆元

我们现在需要求解方程 \(ax+by=\gcd(a,b)\) ，
首先 \(b=0\) 时显然有解 \(x=1,y=0\) ，
再来看 \(\gcd(a,b)=\gcd(b,a\ \%\ b)\) ，把 \(a\ \%\ b\) 拆开：

\[\gcd(a,b)=\gcd(b,a-\lfloor\frac{a}{b}\rfloor b) \]

再加入一点裴蜀定理：

\[\begin{aligned} ax+by &= \gcd(a,b) \\ &= \gcd(b,a-\lfloor\frac{a}{b}\rfloor b) \\ &= bx_0+(a-\lfloor\frac{a}{b}\rfloor b)y_0 \\ &= ay_0+b(x_0-\lfloor\frac{a}{b}\rfloor y_0) \\ \end{aligned} \]

\[\Rightarrow \begin{cases} x = y_0 \\ y = x_0-\lfloor\frac{a}{b}\rfloor y_0 \\ \end{cases} \]

我们发现 \(x,y\) 能递归向下求解，由辗转相除性质可知，总能递归到 \(b=0\) 的情况。
于是我们得到了方程 \(ax+by=\gcd(a,b)\) 的一组解。

现在来讲讲如何把这一过程作用在具体用途上：

1. 判断方程\(ax+by=m\)是否有解：
   由裴蜀定理的充要性可知，若 \(\gcd(a,b)|m\) ，则方程一定有解，反之一定无解。

2. 求\(ax+by=m\)的任意一组解、通解、最小整数解：
   首先保证 \(\gcd(a,b)|m\) ，求出 \(ax+by=\gcd(a,b)\) 的解再同乘即可。

3. 求逆元：
   重中之重，吊打费马小求逆元。
   众所周知，使用费马小定理 \(a^{p-2}\equiv\frac{1}{a} \mod p\) 有两点限制： \(a \bot p\ ,\ p \in prime\)。
   扩展欧几里德求逆元只有一条限制：$a \bot p\ $。

   要求 \(a\) 在模 \(p\) 意义下的逆元 \(b\) ，有：
   \(\begin{aligned} &\ \ \ \ \ \ \frac{1}{a} \equiv b \mod p \\ &\Rightarrow ab \equiv 1 \mod p \\ &\Rightarrow ab = 1 + px \\ &\Rightarrow ab + (-p)x = 1 \\ \end{aligned}\)

   使用扩欧求解 \(b\) 即可。

同余

咕。

标签：frac,gcd,整数,ax,整除,同余,公因数
From： https://www.cnblogs.com/MoCy233/p/18676680