欧拉函数

欧拉定理

$$ a^{\varphi(m)} \equiv 1 \pmod{m} $$

扩展欧拉定理

$$ a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},&\,\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p $$

$\varphi$ 的定义

$\varphi(x)$ 表示小于x的正整数中与x互质的数的个数。
例如:
$\varphi(5)=3,\varphi(6)=1$等等
注意:$\varphi$ 和 $\phi$ 是同一个符号

欧拉函数公式

$\varphi(x)=x*\prod_{i=1}^n\frac{p_i-1}{p_i}$

证明

根据唯一分解定理,得到 $n={p_1}^{k_1}*{p_2}^{k_2}*{p_3}^{k_3}*\dots*{p_n}^{k_n}$ 。

在与x互质的数的合集内, $p_i$ 的倍数一定不包括,而比x小的数中正好存在 $\frac{1}{p_i}$ 个 $p_i$ 的倍数。所以留下了 $\frac{p_i-1}{p_i}$ 个数。

而由于 $p$ 合集中都是质数,所以已经用过的质数不会对将要用的质数产生影响。所以之后的所有 $p_i$ 都是删掉 $\frac{1}{p_i}$ 个,留下 $\frac{p_i-1}{p_i}$ 个。

本文链接:http://kaispace.com.cn/index.php/archives/506/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者