物理 欧拉专题之欧拉函数
前言：欧拉的东西太多了，来个总体吧
更新进度：$\huge{\frac{1}{15}}$
欧拉函数是个什么玩意？虽然说欧拉函数名为函数，但其更多涉及数论知识了。
1.1形式表示
欧拉函数严格定义为 设 $ n $ 是一个正整数，**欧拉函数** $ \phi(n) $ 表示 **小于等于 $ n $ 且与 $ n $ 互素的正整数的个数**。
即：$ \phi(n) = \#\{k \in \mathbb{Z}^+ \mid 1 \leq k \leq n,\ \gcd(k, n) = 1\} $
举个例子看一看
$ n $ 与 $ n $ 互素的数 $ \phi(n) $
| 1 | {1} | 1 |
| 2 | {1} | 1 |
| 3 | {1,2} | 2 |
| 4 | {1,3} | 2 |
| 5 | {1,2,3,4} | 4 |
| 6 | {1,5} | 2 |
| 7 | {1,2,3,4,5,6} | 6 |
| 8 | {1,3,5,7} | 4 |
| 9 | {1,2,4,5,7,8} | 6 |
| 10 | {1,3,7,9} | 4 |
注意：$ \phi(1) = 1 $，因为 $ \gcd(1,1) = 1 $
注意到他们都满足欧拉函数，那么欧拉函数到底有什么卵用呢？
睡觉去了明天更🙃(ToT)(ToT)
更帖子欧拉函数的性质
性质 1：若 $ p $ 是质数，则$\phi(p) = p - 1$， 因为除了 $ p $ 本身外，所有小于 $ p $ 的正整数都与 $ p $ 互素。
性质 2：若 $ p $ 是质数，$ k \geq 1 $，则$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$
证明思路： 在 $ 1 $ 到 $ p^k $ 中，与 $ p^k $ 不互素的数是那些能被 $ p $ 整除的数。这些数有：$ p, 2p, 3p, \ldots, p^{k-1} \cdot p = p^k $
共 $ p^{k-1} $ 个。 所以互素的数有：$ p^k - p^{k-1} $
例如：$ \phi(8) = \phi(2^3) = 8 - 4 = 4 $，对应 {1,3,5,7}
性质 3：积性函数
若 $ m $ 和 $ n $ 互素（即 $ \gcd(m,n) = 1 $），则：$\phi(mn) = \phi(m)\phi(n)$
例子：
$ \phi(6) = \phi(2 \cdot 3) = \phi(2)\phi(3) = 1 \times 2 = 2 $
$ \phi(15) = \phi(3 \cdot 5) = \phi(3)\phi(5) = 2 \times 4 = 8 $
$ \phi(12) = \phi(3 \cdot 4) $ 不成立！因为 $ \gcd(3,4)=1 $？是的，所以可以拆：
$\phi(12) = \phi(3)\phi(4) = 2 \times 2 = 4$
实际上，$ \phi(12) = \{1,5,7,11\} \Rightarrow 4 $，正确。注意：只有当 $ m,n $ 互素时才成立！