(不会证明……以后再说)
费马小定理
对于任意\(a,p \in N_+\),有
\(a^{p-1} \equiv 1\pmod {p}\)
推论:
\(a^{-1} \equiv a^{p-2} \pmod{p}\)
即\(a^{p-2}\)为\(a\)模\(p\)意义下的乘法逆元。
欧拉定理
对于\(a,p \in N^*\)且\(a \perp p\),有\(a^{\varphi (p)} \equiv 1 \pmod {p}\),其中\(\perp\)表示互质。
其中\(\varphi (p)\)表示\(p\)对应的欧拉函数值。
推论1:\(a^{-1} \equiv a^{\varphi(p) - 1} \pmod{p}\)
由欧拉函数性质,当\(p\)是质数时:\(\varphi(p) = p-1\)
可见,费马小定理是\(p\)为质数时欧拉定理的特殊情况。
推论2:\(a^ b \equiv a^{b \bmod \varphi(p)} \pmod{p}\)
可用于答案含大指数时对给定质数取模。
扩展欧拉定理
对于任意\(a,p \in N^*\),有
\[a^b \equiv \begin{equation*}
\left\{
\begin{aligned}
a^b \qquad \qquad \ \ \ (b < \varphi(p)) \\
a^{(b \bmod \varphi(p)) + \varphi(p)}(b \ge\varphi(p)) \\
\end{aligned}
\right.
\end{equation*}\pmod{p}\]
这是在任意模数下对大指数取模的原理。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章