数论-欧拉函数 学习笔记

一、欧拉函数 1.欧拉函数的定义

欧拉函数（Euler’s totient function），即 φ ( n ) \varphi(n) φ(n)，表示的是小于等于 n n n 和 n n n 互质的数的个数。

比如说 φ ( 1 ) = 1 \varphi(1) = 1 φ(1)=1。

当 n 是质数的时候，显然有 φ ( n ) = n − 1 \varphi(n) = n - 1 φ(n)=n−1。

2.欧拉函数的一些性质

• 欧拉函数是积性函数。

  积性是什么意思呢？如果有 gcd ⁡ ( a , b ) = 1 \gcd(a, b) = 1 gcd(a,b)=1，那么 φ ( a × b ) = φ ( a ) × φ ( b ) \varphi(a \times b) = \varphi(a) \times \varphi(b) φ(a×b)=φ(a)×φ(b)。

  特别地，当 n n n 是奇数时 φ ( 2 n ) = φ ( n ) \varphi(2n) = \varphi(n) φ(2n)=φ(n)。

• n = ∑ d ∣ n φ ( d ) n = \sum_{d \mid n}{\varphi(d)} n=∑d∣n​φ(d)。

  利用 莫比乌斯反演 相关知识可以得出。

  也可以这样考虑：如果 gcd ⁡ ( k , n ) = d \gcd(k, n) = d gcd(k,n)=d，那么 gcd ⁡ ( k d , n d ) = 1 , （ k < n ） \gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, （ k < n ） gcd(dk​,dn​)=1,（k