《简明数论》的简明笔记（中）：13~21节
Tuesday, November 18th, 2008
Euler函数φ(m)，定义，积性不完全；
；
；
。
用积性证很简单；证明二：按与m的最大公约数分类。
f(n)的Mobius变换：；
Mobius逆变换：；
以上两式等价，f(n)与F(n)的积性也等价。
f与g的Dirichlet卷积：，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的所有逆元。
注意到一个解是 ，也可用扩展欧几里德求特解。
所有解是，其中0<=t<(a,m)。
形如的一次同余方程组。
若{m_i}两两既约，则解数必为1（中国剩余定理）。
解为。
其中，。
当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}的一次同余方程组。
Tags: 书籍, 数学, 数论
Related posts
行装
听合唱音乐会有感及其它
在郑州
08年5月11日至12日
推荐一些书