Warning: session_start(): open(/tmp/sess_e1da44795f32b907eb91bda992ddabfa, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 欧拉函数 ====== === 定义 === $1\sim N$ 中与 $N$ 互质的数的个数叫欧拉函数, 记为 $\varphi(N)$ 对 $N$ 分解质因数 $N=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_k^{c_k}$ 特别地, $\varphi(1)=1$ === 性质 === - $\varphi(N)=N\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_k})$ - 若有 $p\ |\ N$, 且满足 $p^2\ |\ N$, 则 $\varphi(N)=\varphi(N/p)*p$ - 若有 $p\ |\ N$, 且一定不满足 $p^2\ |\ N$, 则 $\varphi(N)=\varphi(N/p)*(p-1)$ - $\forall N>1, 1\sim N$ 中与 $N$ 互质的数的和为 $N*\varphi(N)/2$ - 当 $a,b$ 互质时, 有 $\varphi(a*b)=\varphi(a)*\varphi(b)$ - 对 $N$ 分解质因数 $N=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_k^{c_k}$, 则有 $\varphi(N)=\prod_{i=1}^{k}\varphi(p_i^{c_i})$ - $\varphi(p^k)=p^k-p^{k-1}$ - $\sum_{d|n}\varphi(d)=n$ - 若正整数 $a, n$ 互质, 则有 $a^{\varphi(n)}\equiv1\pmod{n}$ - 若正整数 $a, n$ 互质, 则对于任意正整数 $b$, 有 $a^b\equiv a^{b\ mod\ \varphi(n)}\pmod{n}$ - $a, n\in N$, 则$a^b\equiv \left\{\begin{array}{rl}a^b\pmod{n}&,b<\varphi(n),\\a^{b\ mod\ \varphi(n)+\varphi(n)}\pmod{n}&,b\ge\varphi(n). \end{array} \right.$ - 若 $gcd(m,n)=d$, 则 $\varphi(mn)=d\varphi(m)\varphi(n)/\varphi(d)$ - 若 $m\ |\ n$, 则 $\varphi(mn)=m\varphi(n)$ - 若 $m\ |\ n$, 则 $\varphi(m)|\varphi(n)$ - $\varphi(n)=\sum_{d|n}d\cdot\mu(\frac n d)$ === 参考资料 === [[https://blog.csdn.net/niiick/article/details/81347041|]] [[https://www.cnblogs.com/BlueHeart0621/p/11706153.html|]]