《简明数论》的简明笔记（中）：13~21节

Euler函数φ(m)，定义，积性不完全；
- $\phi(m)=m\prod_{p|m}(1-\frac{1}{p})$ ；
- $\phi(m)=m\sum_{d|m}\frac{\mu(d)}{d}$ ；
- 。
  - 用积性证很简单；证明二：按与m的最大公约数分类。
f(n)的Mobius变换：；
- Mobius逆变换：；
  - 以上两式等价，f(n)与F(n)的积性也等价。
- f与g的Dirichlet卷积： $h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$ ，h保持f与g的积性。
同余：
- a对模m的最小非负剩余、绝对最小剩余；
- 同余式是等价关系；同余式可加减乘；ca≡cb (mod m)等价于a≡b (mod m/(c,m) )；
- 对模m的逆的定义。
同余类、完全剩余系定义；
- 既约剩余系包含的同余类个数即φ(m)。
- (a,m)=1时，x遍历m的完全/既约剩余系当且仅当ax遍历m的完全/既约剩余系。
  - 用这个可轻松证明Fermat-Euler定理。
Wilson定理，即(p-1)! ≡ -1 (mod p)。
- 证：除了-1外，其它因子可与（不相等的）逆元配对抵消。
- 即，p的既约剩余系的积模p得-1。
  - 扩展：p可换成p^k，2p^k（这两者p是奇素数）。
- 事实上，r不取1,2,4,p^k,2p^k时，r的既约剩余系的积模r得1。
ax≡b (mod m) 型的同余方程。
- (a,m)|b 是有解的充要条件，解有(a,m)个。
  - 可求a对m的所有逆元。
- 注意到一个解是 $x_0 = a^{\phi(m)-1}b$ ，也可用扩展欧几里德求特解。
- 所有解是 $x_0 + \frac{m}{(a,m)}t$ ，其中0<=t<(a,m)。
形如的一次同余方程组。
- 若{m_i}两两既约，则解数必为1（中国剩余定理）。
  - 解为 $x \equiv \sum M_i M_i^{-1}a_i \pmod{m}$ 。
  - 其中 $m = \prod m_i = M_i m_i$ ， $M_i M_i^{-1} \equiv 1 \pmod{m_i}$ 。
  - 当a_i分别遍历m_i的完全/既约剩余系时，x遍历m的完全/既约剩余系。
- 若{m_i}并非两两既约，例如(m_i,m_j)=a时，可将模m_i与m_j的两个方程化成模a、m_i/a、m_j/a的三个方程。
  - 编程时，直接化为若干个模p^k的方程似更简便，其中p^k || [m_1,m_2,...,m_i,...]。
- f(x)≡0 (mod n) 的解数设为 T(f;n)，则T(f;n)是关于n的积性函数。
  - 于是只需研究f(x)≡0 (mod p^k)型方程的解法。
  - 即求解多个方程后再解个模{p^k}的一次同余方程组。