欧拉函数

定义：

对于正整数n，欧拉函数是小于n的正整数中与n互质的数的个数$(\varphi(1)=1)$。此函数以其首名研究者欧拉命名，它又称为$\varphi$函数、欧拉商数等。举个栗子：$\varphi(8)=4$，因为1,3,5,7均和8互质。

性质与证明：

①通式：$ \varphi (x) = x\prod _{i = 1}^{k} (1 - \frac{1}{p_i}) = x(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots (1 - \frac{1}{p_k}) $.

其中 $p_1, p_2, \cdots, p_n$ 为x的所有素因子，$x > 1$ 且 $x \in N^+$，规定 $ \varphi(1) = 1 $（唯一与1互质的数就是1本身）。 注意：每种素因子只有一个。
证明思路：讨论x的所有素因子 $p_i$ ，只要是 $p_i$ 的倍数的数都不是x的互质数。
用容斥定理证明： $A\cup B \cup C = A + B + C - A \cap B - B \cap C - C \cap A + A \cap B \cap C$.
1)、若x是素数，则 $\varphi(x) = x - 1$.
证明：因为素数x的质因子只有1和它本身，而x和x不互质，所以 $\varphi(x) = x - 1$.
2)、若x不是素数，则只需除去x的质因子$p_i$ 和 $p_i$的倍数的数即可。
设x的所有素因子为 $p_1, p_2, \cdots, p_k$，根据容斥原理得：与x不互质的数的个数为：$\frac{x}{p_1} + \frac{x}{p_2} + \cdots \frac{x}{p_k} - \frac{x}{p_1p_2} - \frac{x}{p_1p_k} - \cdots - \frac{x}{p_{k-1}p_k} + \cdots$
（注：每个分式的符号由该分式的分母中素数的个数来决定：奇加偶减）
则与x互质的数的个数为： $x - (\frac{x}{p_1} + \frac{x}{p_2} + \cdots \frac{x}{p_k} - \frac{x}{p_1p_2} - \frac{x}{p_1p_k} - \cdots - \frac{x}{p_{k-1}p_k} + \cdots)$

$= x(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots (1 - \frac{1}{p_k}) = \varphi (x) = x\prod _{i = 1}^{k} (1 - \frac{1}{p_i})$，即证。

②若n为素数p的k次幂，则有 $ \varphi (n) = \varphi (p^k) = p^k(1-\frac{1}{p}) = p^k - p^{k-1} = (p - 1)p^k $.

证明：因为除了 $ p $ 的倍数外，其他数都与n互质。根据容斥原理得 $ \varphi (n) = $ 总数 - $p$ 的倍数的个数 = $ (p^k - 1) - (\frac{p^k}{p} - 1) = p^k - p^{k -1} = (p - 1)p^k$ ，即证。

③欧拉函数是积性函数，但不是完全积性函数。

若m与n互质，则$ \varphi(mn) = \varphi(m)\varphi(n)$.
特殊地，当m=2，若n为奇数时，$ \varphi(2n)= \varphi(n)$.
证明：因为m与n互质，所以它们没有公共的质因子。
设m有$a_m$个质因子，n有$a_n$个质因子，则有

$\varphi (m) \varphi (n) = mn \prod _{i = 1}^{a_m} (1 - \frac{1}{p_i})\prod _{i = 1}^{a_n} (1 - \frac{1}{p_i}) = mn \prod _{i = 1}^{a_m + a_n}(1 - \frac{1}{p_i}) = \varphi (mn)$.
换句话说：只有那些既满足m与其互质且也满足n与其互质的数才满足条件。
根据乘法原理，这些数可以互相组合，则有 $\varphi(m)\varphi(n)$个，即证。
积性函数的性质：若将n表示成质因子分解式：$n = p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}$，则有 $\varphi(n) = \varphi(p_1^{a_1})\varphi(p_2^{a_2}) \cdots \varphi(p_k^{a_k})$.

④小于n且为n的互质数之和为 $\sum_{i=1}^n i*[gcd(n, i)==1] = \frac{n*\varphi(n)}{2}$。

证明用到一个推论：若 $ gcd(n, i) = 1 $，则 $ gcd(n, n-i) = 1 $（设$n > i$)。
下面证明这个推论：用反证法证明：假设 $ \exists k \neq 1 $，使 $gcd(n, n-i) = k $ 成立，即
$gcd(n, n-i) = k \Rightarrow (k|n) \land (k|(n-i)) \Rightarrow (k|n) \land (k|i) \Rightarrow gcd(n, i) = k \neq 1 $，
显然这与条件相矛盾，所以假设不成立，即原命题正确。
于是问题求解变得非常简单： 通过上面的推论可知 i 和 n-i 总是成对出现，且和是n，
即与n互质的所有数之和为 $\sum_{i = 1}^n i*[gcd(n, i) == 1] = \frac{n*\varphi(n)}{2}$
下面讨论在 $ gcd(n, i) = gcd(n, n - i) = 1 $ 的前提下，是否会出现 $ n - i == i$ 时而导致重复计算呢？
分两种情况来讨论：
1)、若n为奇数，因为 $n \neq 2 * i$，所以不存在$n-i=i$时导致的重复计算；
2)、若n为偶数，则 $n = 2 * i$， $[gcd(n,\frac{n}{2}) = \frac{n}{2}] | n$.
当且仅当 $ n = 2 $ 时，$ gcd(n, \frac{n}{2}) = \frac{n}{2} = 1$，
此时 $\sum_{i = 1}^2 i * [gcd(2, i) == 1] = \frac{2*1}{2} = 1$，显然不会重复计算；而对于 $ n > 2 $ 的偶数，$ gcd(n, \frac{n}{2}) = \frac{n}{2} \neq 1$，显然不满足原条件，更别说重复计算了，即证。

备注：

a、积性函数：对于任意互质的整数a和b有性质$f(ab)=f(a)f(b)$ 的数论函数。
b、完全积性函数：对于任意整数a和b有性质$f(ab)=f(a)f(b)$ 的数论函数。
c、在数论上，算术函数（数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。