模运算
基本知识
\begin{align}
&a\mod{1}=0\\
&a\mod{a}=0\\
&若\ a\mod{b}=0\\
&则\ b|a\\
&若\ a\mod{c}=b\mod{c}\ 则\ c|(a-b)\\
&同时\ a\mod{c}=b\mod{c}\ 也可以记为\ a\equiv{b}\mod{c}\\
&a\equiv{a}\mod{c}\\
&若\ a\equiv{b}\mod{c}\ 则\ b\equiv{a}\mod{c}\\
&若\ a\equiv{b}\mod{p}\ 且\ b\equiv{c}\mod{p}\ 则\ a\equiv{v}\mod{p}\\
&0,1,2\cdots p-1\ 称作\ p的剩余系
\end{align}
辗转相除法证明
具体内容看这里
\begin{align}
&设:\\
&a=bk+r(a\geq{b}\geq{r})\\
&g=\gcd(a,b)\\
&ng=a\\
&mg=b\\
&则:\\
r&=a-bk\\
&=ng-mgk\\
&=(n-mk)g\\
&\therefore g|r\\
又\ &\because g|b\\
&\therefore g|\gcd(r,b)\\
&若要证明\ g=\gcd(r,b)\\
&相当于证明\ \gcd(m,n-mk)=1(我一开始就是这里没看懂,多理解一下)\\
&若存在\ q>1\ 且\ q|m,q|(n-mk)(即q=\gcd(m,n-mk))\\
&则\ q|n\ \\
&\therefore qg|ng,qg|mg(这段看不懂的去复习上面的基本知识)\\
&\therefore qg|a,qg|b\\
而&\because g=\gcd(a,b)\\
&\therefore q=1\\
&\therefore\gcd(m,n-mk)=1\\
&\therefore\gcd(a,b)=g=\gcd(b,a\mod{b})\\
&证毕
\end{align}
逆元
其实课上并没有讲清楚逆元的定义，这边讲一下，或许能让你更好理解。
单位元：
在不同的运算中，有不同的单位元。
任何数对同一个数做相应的运算，得到原来的这个数，就称这个数是该运算域的单位元。
如加法的单位元为 0 ，因为 a+0=a 。
而乘法的单位元为 1 ，因为 a\times 1=a 。
在模域里，显然能得到单位元为 1 ，因为 $a\times 1\equiv a\mod p$ 。
逆元：
同样的：
一个数在不同的运算中，有不同的逆元，
但每个数都有相对应的运算中的逆元。
一个数对一个数做运算，最终得到了该运算域的单位元，则称这两者互为逆元
如 a 在加法域的逆元为 -a ，因为 a+(-a)=0
而 a 在乘法域的逆元为 \frac{1}{a} 或 a^{-1} ，因为 a\times\frac{1}{a}=1
在模域里，逆元就没那么好求了，且在此运算中，一个数不一定有逆元，若有，则是唯一的。
但我们可以同过定义知道，当 x 为 a 的在 \mod{p} 下的逆元时：
ax\equiv1\mod{p}
那我们求逆元有什么用呢？
我们知道在模乘中，可以很简单的进行加、减和乘法运算：
a\mod{p}\ +\ b\mod{p}=(a+b)\mod{p}\\
a\mod{p}\ -\ b\mod{p}=(a-b)\mod{p}\\
a\mod{p}\ \times\ b\mod{p}=(a\times{b})\mod{p}
但不能像上述方法一样做除法：
10\mod{3}=1\\
5\mod{3}=2\\
\therefore \frac{10\mod{3}}{5\mod{3}}=\frac{1}{2}\\
而\ \frac{10}{5}\mod{3}=2
所以当我们要求一个分数对模数取模时，就要使用逆元来求解。
以下给出几种求逆元的方法：
求单个逆元：
费马小定理
注意：本方法仅适用于模数 p 为质数且 \gcd(a,p)=1 时的情况！
定理1
在\ \gcd(c,p)=1\ 时\\
若\ ac\equiv{bc}\mod{p}\\
则\ a\equiv{b}\mod{p}
证明:
ac\equiv{bc}\mod{p}\\
ac-bc\equiv bc-bc\mod{p}\\
(a-b)c\equiv 0\mod{p}\\
\because \gcd(c,p)=1\\
\therefore a-b\equiv 0\mod{p}\\
\therefore a\equiv b \mod{p}
定理2：
若\ \gcd(a,p)=1\\
则\ (a,2a,3a,\cdots,(p-1)a)\mod p\\
余数取遍\ (1,2,3,\cdots,p-1)
证明
在\ \gcd(a,p)=1\ 的情况下\\
若存在\ aj\equiv ai\mod{p}\\
通过定理1可以知道\\
\because \gcd(a,p)=1\\
\therefore i\equiv j\mod{p}\\
矛盾\\
\therefore若\ \gcd(a,p)=1\\
则\ (a,2a,3a,\cdots,(p-1)a)\mod p\\
余数取遍\ (1,2,3,\cdots,p-1)
由定理二可知：
在\ \gcd(a,p)=1\ 的情况下\\
(1,2,3,\cdots,(p-1))\ 与\ (a,2a,3a,\cdots,(p-1)a)\mod p\\
都余数取遍\ (1,2,3,\cdots,p-1)\\
那么两个集合内所有数相乘后\ \mod p\ 的余数相等\\
即:\ (p-1)!\equiv(p-1)!\times{a^{p-1}}\mod{p}\\
显然\ \gcd((p-1)!,p)=1\\
\therefore a^{p-1}\equiv 1\mod{p}\\
\therefore a\times a^{p-2}\equiv 1\mod{p}
是不是感觉最后那个式子很眼熟？
再翻到上面逆元定义的地方看一眼，
现在知道了吧，上面的 x 就对应了这里的 a^{p-2} ！
所以在 \gcd(a,p)=1 时，加上快速幂，我们就可以 O(\log p) 求出一个数的逆元了。
猜你想搜：