『算法-ACM 竞赛-数学-数论』（逆元）扩展欧几里求解+证明

欧几里得与扩展欧几里得

先解释一下符号：

$$A≡B （mod C）符号代表A模C与B模C相等，即A/C与B/C同余。$$

$inv（a）代表a的逆元$

定义：
$b ∗b^{-1}≡1 (mod c) ，那么称b^-1^为b模c的乘法逆元。$
$则Inv（b）=b^{-1}$

定理：

$\frac{a}{b}\pmod{c}=a*inv(b)\pmod{c}成立的条件是inv(b)存，在即b与c互质。$

用途：

乘法逆元可以用来求解部分除法的取模问题（分母是一个整数，并且与被取模数互质）
$$b ∗b^{-1}≡1 (mod c) $$$$可以转化为使用拓展欧几里得求解bx+cy=1的解，
求解x即为b的逆元$$
证明:
学数论不证明，是不能锻炼逻辑思维能力的。

$因为 ainv(a)≡1(modc)\
所以设 ainv(a)=kc+1\
移项得 ainv(a)-kc=1\
取K=-k得 ainv(a)+K*c=1$
原结论得证

小技巧：
但是这里的 inv(a)可能解除负值，我们可以再加上 c 来保证他是正整数