笔记汇总
欧拉函数的定义
$1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数,记为 $\varphi(N)$。
若在算数基本定理中,$N=p^{a_1}_1 * p^{a_2}_2 * … * p^{a_m}_m$,则:
$\varphi(N) = N × \frac{p_1−1}{p_1} × \frac{p_2−1}{p_2} × … × \frac{p_m−1}{p_m}$
证明 $(proof)$
定义 $(definition)$
互质:公约数只有 $1$ 的两个整数互质
边界 $(basis)$
$\varphi(1) = 1$,小于等于 $1$ 的正整数只有 $1$,
稍微扩展一下 ∼hh
$\varphi(1) = 1$, $\varphi(2) = 1$, $\varphi(3) = 2$
$\varphi(4) = 2$, $\varphi(5) = 4$, $\varphi(6) = 2$
$\varphi(7) = 6$, $\varphi(8) = 4$, $\varphi(9) = 6$
$\varphi(10) = 5$,$\varphi(11) = 10$,$\varphi(12) = 4$
规律 1
可以发现,对于两个互质的数 $m,n$,满足 $\varphi(mn) = \varphi(m) * \varphi(n)$,例如
$\varphi(6) = \varphi(2) * \varphi(3) = 1 * 2 = 2$
$\varphi(12) = \varphi(3) * \varphi(4) = 2 * 2 = 4$
这个性质很好证明:
如果一个数 $d$ 与 $n$ 互质,则 $d$ 肯定也与 $n * m$ 互质。
若有一个数 $c$ 与 $n * m$ 互质,则可以推论出 $d * c$ 同样与 $n * m$ 互质。
根据乘法原理可证。
规律 2
$\varphi(a^b) = a^b - a^{b-1}$,例如
$\varphi(4) = 2^2 - 2^{2-1} = 2$
$\varphi(9) = 3^2 - 3^{2-1} = 6$
让我们来写一个优美的证明:
因为 $\varphi(a^b)$ 表示 从 $1$ 到 $a^b$ 中与 $a^b$ 互质的数。
我们用排除法解决,在 $\varphi(a^b)$ 中,不与 $a^b$ 互质的数有 $a、2a…a^{b-1}*a$ 共 $a^{b-1}$ 个数。
所以 $\varphi(a^b) = a^b - a^{b-1}$,得证。
规律扩展
因为 $N=p^{a_1}_1 * p^{a_2}_2 * … * p^{a_m}_m$
所以 $\varphi(N)=\varphi(p^{a_1}_1) * \varphi(p^{a_2}_2) * … * \varphi(p^{a_m}_m)$
代入 $\varphi(a^b) = a^b - a^{b-1}$ 得
$\varphi(N) = (p^{a_1}_1 - p^{a_1 - 1}_1) * (p^{a_2}_2 - p^{a_2 - 1}_2) * … * (p^{a_m}_m - p^{a_m - 1}_m)$
又因为 $a^b - a^{b-1} = a^b * (1 - \frac{1}{a})$
所以 $\varphi(N) = p^{a_1}_1 * p^{a_2}_2 * … * p^{a_m}_m * (1 - \frac{1}{p_1}) * (1 - \frac{1}{p_2}) * … * (1 - \frac{1}{p_m}) = N * \displaystyle\prod_{i = 1}^{m}(1 - \frac{1}{p_i})$
得证。
性质 1
质数的欧拉函数 等于 其值 $- 1$,例如
$\varphi(2) = 1$, $\varphi(3) = 2$
$\varphi(5) = 4$, $\varphi(7) = 6$
欧拉函数请用
\varphi
而不是\phi
已更正 https://www.zhihu.com/question/321882252
emm