Skip to content

《简明数论》的简明笔记(中):13~21节

  • Euler函数φ(m),定义,积性不完全;
    • \phi(m)=m\prod_{p|m}(1-\frac{1}{p})
    • \phi(m)=m\sum_{d|m}\frac{\mu(d)}{d}
    • \sum_{d|m}\phi(d)=m
      • 用积性证很简单;证明二:按与m的最大公约数分类。
  • f(n)的Mobius变换:F(n)=\sum_{d|n}f(d)
    • Mobius逆变换:f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})
      • 以上两式等价,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可换成pk,2pk(这两者p是奇素数)。
    • 事实上,r不取1,2,4,pk,2pk时,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)。
  • 形如x \equiv a_i \pmod{m_i}的一次同余方程组。
    • 若{m_i}两两既约,则解数必为1(中国剩余定理)。
      • 解为x \equiv \sum M_i M_i^{-1}a_i \pmod{m}
      • 其中m = \prod m_i = M_i m_iM_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}的一次同余方程组。

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*