【初等数论】费马小定理&欧拉定理&扩展欧拉定理(暂不含证明)
阅读原文时间:2023年07月08日阅读:2

(不会证明……以后再说)


费马小定理

对于任意\(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}\]

这是在任意模数下对大指数取模的原理。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章