雪碧的博客

Preface 复习数论的时候发现原来好像原来学过的全忘了，于是重新学习了一下，并记录如下。 欧拉函数 欧拉函数 φ(n)\varphi(n)φ(n) 表示小于等于 nnn 的正整数中与 nnn 互质的数的个数。 性质 欧拉函数是一个积性函数，即对于互质的两个数 mmm 和 nnn ，有 φ(m×n)=φ(m)×φ(n)\varphi(m \times n) = \varphi(m) \times \varphi(n)φ(m×n)=φ(m)×φ(n) ，容易通过唯一分解定理证明。 这给我们提供了很多很好的性质。 φ(1)=1\varphi(1) = 1φ(1)=1 φ(p)=p−1\varphi(p) = p - 1φ(p)=p−1 （ppp 为质数） φ(pk)=pk−pk−1\varphi(p^k) = p^k - p^{k - 1}φ(pk)=pk−pk−1 （ppp 为质数） φ(m×n)=φ(m)×φ(n)\varphi(m \times n) = \varphi(m) \times \varphi(n)φ(m×n)=φ(m)×φ(n) （mmm 和 nnn 互质） φ(n ...