前知导入
唯一分解定理
对于任何一个大于 \(1\) 的正整数都能分成有限个质数的乘积
即若 \(n\) 为大于 \(1\) 的整数，则有：\(n=\prod \limits_{i=1}^{m}p_i^{c_i}\)
其中，\(p_i\) 为质数且递增，\(p_i\leq n,c_i\geq 0\)
容斥原理
在此仅做简单引入
带入情景，班里有 \(10\) 个同学喜欢数学，\(5\) 个喜欢语文，\(8\) 个喜欢英语，求至少喜欢一门的学生个数
这个问题很好解决，讲喜欢这三科的学生的集合分别记作 \(A,B,C\)，则至少喜欢一门的学生表示为 \(|A\cup B\cup C|\)
则 \(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B \cap C|+|A\cap B\cap C|\)
这就是简单的容斥原理
定义
写作 \(\varphi(n)\)，表示小于等于 \(n\) 的正整数中与 \(n\) 互质的个数
性质
- 当 \(n\) 为质数时，\(\varphi(n)=n-1\)
-
\[\varphi(n)=\begin{cases} 1&n=1\\ n\times \prod\limits_{p\in\mathbb{p},p|n}(1-\dfrac{1}{p})&i\neq 1\\ \end{cases}\]
-
证明：
当 \(n>1\) 时，根据唯一分解定理，设 \(n=\prod\limits_{i=1}^{m}p_i^{c_i}\)其中 \(p_i,p_j\) 为 \(n\) 的质因子
则 \(1\sim n\) 中，\(p_i\) 的倍数有 \(\dfrac{n}{p_i}\) 个，\(p_j\) 的倍数有 \(\dfrac{n}{p_j}\) 个
根据容斥原理，\(1\sim n\) 中不与 \(n\) 有共同因子 \(p_i\) 或 \(p_j\) 的个数为 $$n-\dfrac{n}{p_i}-\dfrac{n}{p_j}+\dfrac{n}{p_i\times p_j}=n\times (1-\dfrac{1}{p_i}-\dfrac{1}{p_j}+\dfrac{1}{p_i\times p_j})=n\times (1-\dfrac{1}{p_i})\times (1-\dfrac{1}{p_j})$$
以此类推，将 \(n\) 的全部质因子全部代入容斥原理，即可得到 \(\varphi(n)\)
-
-
欧拉函数是积性函数
当 \(\gcd(a,b)=1\) 时，\(\varphi(a\times b)=\varphi(a)\times \varphi(b)\)
由此不难推出，当 \(n\) 为奇数时，\(\varphi(2n)=\varphi(n)\)
-
证明：
根据唯一分解定理，不妨设 \(a=\prod\limits_{i=1}^{m}p_i^{c_i},b=\prod\limits_{i=1}^{m}q_i^{d_i}\)
因为 \(\gcd(a,b)=1\)，所以一定不存在一组 \(p_i=q_j\)
那么 \(ab\) 可分解为 \(\prod\limits_{i=1}^{m}p_i^{c_i}\times \prod\limits_{i=1}^{m}q_i^{d_i}\)，其中 \(p,q\) 一定不相等
故此，依据性质 \(2\)，则有 \(\varphi(ab)=ab\times \prod\limits_{i=1}^n(1-\dfrac{1}{p_i})\times \prod\limits_{i=1}^m(1-\dfrac{1}{q_i})\)
又因为 \(\varphi(a)=a\times \prod\limits_{i=1}^n(1-\dfrac{1}{p_i}),\varphi(b)=b\times \prod\limits_{i=1}^m(1-\dfrac{1}{q_i})\)
所以得到 \(\varphi(ab)=\varphi(a)\times \varphi(b)\)
-