扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
一道数论问题,高手请若a>b>0,a,b均为正整数,n是一个正整数且满足n|(a的n次方-b的n次方）,求证：n|(a的n次方-b的n次方）/(a-b),在线等,速度
扫二维码下载作业帮
2亿+学生的选择
将n标准分解对n的任意素因子p取r使p的r次幂整除n且p的r+1次幂不整除n若p与a-b互质,结论成立否则p整除a-b用归纳法p的x-1次幂整除【a的（p的x-1次幂）次幂-b的（p的x-1次幂）次幂】记a的（p的x-1次幂）次幂=A,b的（p的x-1次幂）次幂=B【A的p次幂-B的p次幂】=【A-B】*【A的p-1次幂+A的p-2次幂*B+...+B的p-1次幂】已知p的x-1次幂整除【A-B】只需证p整除【A的p-1次幂+A的p-2次幂*B+...+B的p-1次幂】由amodp同余b,知Amodp同余B【A的p-1次幂+A的p-2次幂*B+...+B的p-1次幂】modp同余【p*B的p-1次幂】同余0即证
其他类似问题
扫描下载二维码您的访问出错了(404错误)
很抱歉，您要访问的页面不存在。
1、请检查您输入的地址是否正确。
进行查找。
3、感谢您使用本站，3秒后自动跳转至网站首页您还可以使用以下方式登录
当前位置：&>&&>& > 初等数论讲义
初等数论ppt 初等数论讲义
初等数论讲义张起帆 1 唯一分解定理 7第一讲 唯一分解定理的证明及简单应用 ...................................................................................... 71.1 带余除法 .................................................................................................................................. 71.2 同余语言的引进.......................................................................................................................81.3 唯一分解定理及证明 ...............................................................................................................81.4 应用举例 .................................................................................................................................. 91.5 进一步的思考......................................................................................................................... 10第二讲 一些数论问题 .................................................................................................................... 101.6 Eratosthenes筛法 ................................................................................................................ 101.7 一次不定方程......................................................................................................................... 111.8 Fermat数与Mersenne数 ................................................................................................... 12 2 同余式 13第三讲 周期问题 ............................................................................................................................ 132.1 同余的概念及基本性质 ......................................................................................................... 132.2 周期 ........................................................................................................................................ 14第四讲 孙子定理及应用 ................................................................................................................ 152.3 Wilson定理 ........................................................................................................................... 152.4 孙子定理 ................................................................................................................................ 152.5 Euler函数的计算 .................................................................................................................. 17第五讲 高次同余方程 .................................................................................................................... 182.6 解同余方程的一般原则 ......................................................................................................... 182.7 模素数幂的同余方程 ............................................................................................................. 192.8 模素数的同余方程 ................................................................................................................ 20 3 原根与二次剩余 23第六讲 模p的原根 ...................................................................................................................... 233.1 原根的存在性........................................................................................................................ 233.2 原根的判别准则.................................................................................................................... 243.3 二次剩余和勒让德符号 ......................................................................................................... 2534 CONTENTS第七讲 二次互反律 ........................................................................................................................ 263.4 Gauss引理 ................................................................................................................................... 263.5 二次互反律的证明 ....................................................................................................................... 273.6 推广的二次互反律 ....................................................................................................................... 283.7 特殊的二次同余方程的解 ........................................................................................................... 29第八讲 素数表平方和问题 ............................................................................................................ 303.8 素数表平方和主要定理 ............................................................................................................... 313.9 Gauss整数的算术 ....................................................................................................................... 323.10 Gauss整数的应用 ................................................................................................................. 333.11
小结 ......................................................................................................................................... 34第九讲 模m的原根 ....................................................................................................................... 343.12 模m的原根存在的条件 ....................................................................................................... 353.13 指数 ......................................................................................................................................... 373.14 公钥密码应用 ......................................................................................................................... 38第十讲 群，环，域理论简介（上） .......................................................................................................................... 383.15 群的概念及例子 ..................................................................................................................... 383.16 似曾相识的群理论 ................................................................................................................. 403.17 基本的群论定理 ..................................................................................................................... 41第十一讲 必备的抽象代数（下） ................................................................................................................ 423.18 环和域的概念及例子 ............................................................................................................. 423.19 环的算术性质 ......................................................................................................................... 443.20 理想的运算 ............................................................................................................................. 453.21 域的“熟知”定理 ................................................................................................................................................... 46 4 数论函数 47第十二讲 基本的数论函数及运算 ................................................................................................ 474.1 数论函数pot ................................................................................................................................ 474.2 麦比乌斯函数和Euler函数 ........................................................................................................ 504.3 Dirichlet乘积 ............................................................................................................................... 51第十三讲 分析方法初步 ................................................................................................................ 514.4 麦比乌斯反演公式 ....................................................................................................................... 514.5 积性函数和完全积性函数 ........................................................................................................... 524.6 素数分布 ....................................................................................................................................... 53第十四讲 不定方程 ........................................................................................................................ 564.7 同余方法 ....................................................................................................................................... 564.8 Fermat无穷递降法 ............................................................................................................................ 574.9 柯召方法 ....................................................................................................................................... 584.10 局部整体原则 ......................................................................................................................... 61Chapter 1 唯一分解定理 第一讲 唯一分解定理及简单应用 1.1 带余除法对任意整数a, b，b
> 0，存在唯一整数q, r满足 a = bq + r, 0 ≤ r < b这是小学生都知道的事实，但却是至关重要的。它可以给出求最大公约数的Euclid算法：设a, b为 正整数且a > b, 则可不断做带余除法a = bq1 + b1b = b1q2 + b2 则bn+1 = (a, b) 因为· · ·
bn = bn+1qn+2 + bn+2, bn+2 = 0(a, b) = (a-b, b) = (a-2b, b) = · · · = (b1, b) = (b-b1, b1) = · · · = (b2, b1) = · · · = (bn+1, bn) = bn+1 从上述算法得出如下结论，由于很重要，作为定理 定理1.1.1. 对任意整数a, b，存在整数u, v，满足 (a, b) = au + bv 有了这个定理我们容易得到如下结论： 引理1.1.2. 对整数a, b, c，若(a, b) = 1，则 a|bc ==> a|c78 CHAPTER 1.
唯一分解定理证明：因为(a, b) = 1，故存在整数u, v，满足 1 = au + bv 即 由于两项都是a的倍数，故a|c。推论：对素数p有c = acu + bcvp|ab ==> p|a或p|b 1.2 同余语言的引进对整数a, b, m，称a模m同余于b，记为a ≡ b (mod m)是指a和b用m除的余数相同，换句话 说m|a - b。例如17 ≡ 10 ≡ 3 (mod 7)同余思想简单来说就是在带余除法中忽略商，只关心余数，在某些场合，这就突出了重点，看问 题更清晰，现重新叙述前面的推理:Eulcid算法：对整数a > b > 0，一定有a ≡ b1
(mod b)，（对某一整数b1，0 ≤ b1
< b）b ≡ b2
(mod b1)，（对某一整数b2，0 ≤ b2
< b1）· · ·bn-1 ≡ bn+1 = 0 (mod bn)(a, b) = bn定理1.1.1对任意整数a, b，存在整数v使bv ≡ (a, b) (mod a)，特别地，若(a, b) = 1，则有bv ≡ 1 (mod a)引理的证明：因(a, b) = 1，故存在v满足bv ≡ 1 (mod a)，在bc ≡ 0 (mod a)中两边同 乘v有c ≡ bvc ≡ 0 (mod a) 1.3 唯一分解定理及证明定理1.3.1. 任意大于1的整数都可以唯一地分解为素数之积 证明：先证存在性，这只需素数的定义和归纳公理即可完成。对整数n > 1，问n是否素数？若是，则完成；若非，则存在整数a, b，使得n = ab。继续问：是否a和b是否都是素数，继续下去 得证。再证唯一性。设有两种分解 n = p1 · · · ps = q1 · · · qt,1.4.
应用举例 9则p1|q1 · · · qt，用推论知由此推出p1整除某一qi，不妨设p1|q1，再由p1, q1是素数知p1 = q1。因此 p2 · · · ps = q2 · · · qt,归纳即可完成证明。 1.4 应用举例例1 正的有理数有唯一的既约分数表示。证明：设α =
(a, b) = (c, d) = 1，则ad = bc，那么a|bc，结合(a, b) =
1知a|cb 同 d 理c|a,故a = c,进而b = d，即有理数α有唯一的既约分数表示。 例2 若(a, b) = 1，则(a + b, a - b) = 1或2。证明：设(a + b, a - b) = d，则d|a + b +(a - b) = 2a, d|a + b - (a - b) = 2b，因此d|(2a, 2b) = 2。例3 对任意正整数n，1000n - 1不整除1978n - 1证明：假设1000n - 1|1978n - 1，则1000n - 1|1978n - 1 - (1000n - 1) = 1978n - 1000n = 2n(989n - 500n)，但(1000n - 1, 2n) = 1，故1000n - 1|989n - 500n。而 这 是 不 可 能 的，因 为0 < 989n - 500n < 1000n - 1。..例4：对素数p和整数1 < r < p，p整除组合数p r .p.证明：因为r 是整数，故r!|p(p - 1) · · · (p - r + 1)，但因r!是一些小于p的数（因此非p的倍.p.的数）相乘，所以r!非p的倍数，那么(r!, p) = 1。结合前面两式知r!|(p - 1) · · · (p - r +1)，所以p|
r 例5：设a, b, c为正整数，(a, b) = 1，ab = cn，则a = cn, b = cn。1 2 数证明：设a = pα1
· · · pαr 1 rb = qβ1 · · · qβs1 s c = pl1
· · · plr qm1
· · · qms1 r
1 s 带入ab = cn并比较得n整除所有αi和βj ，即a, b都是n次幂。 例6：求方程x2 + y2 = z2的整数解解：先简化为这种特殊情形：x > 0, y > 0, z > 0，x, y, z两两互素。这样x, y, z必须两奇一偶， 通过考察用4除的余数知必须z奇，不失一般性可设x偶，y奇。将方程变形为 x2 = z2 - y2)2 = ( )10CHAPTER 1.
唯一分解定理2 2 但由(z, y) = 1利用例2知z+y 再由例5知 z + yz - y = a2, = b2, x = 2ab 解为x = 2ab, y = a2 - b2, z = a2 + b2，(a, b) = 1 要得全部解，可乘任意整数。 1.5 进一步的思考1。唯一分解定理及证明方法在高等代数中多项式的唯一分解中出现过，这里的代余除法是 利用整数的绝对值去量整数的大小；那里是用多项式的次数去量多项式的大小。 2。将视野扩展到所谓Gauss整数集合Z[i] = {a + bi|a, b ∈ Z}，在Z[i]上容易定义整除的概念，请 问(1) Z[i]中哪些元可以求倒数（还在Z[i]中）(2) 可否在Z[i]上定义“素数”的概念。(3)
Z[i]中的“素数”长的什么样，特别地通常的素数中哪些在Z[i]中依然是“素数”(4) 还有没有唯一分解定理，该如何叙述？3。例6的解很容易转化为求圆周x2 + y2 = 1上的有理点。请用通过点(-1,0)引直线与圆相交的方 法去找出全部有理点，并想想这样的方法可否推广？4. 证明方程x4 + y4 = z2无正整数解。第二讲 一些数论问题 1.6 Eratosthenes筛法如何构造和检查素数是一基本问题。注意一个简单事实：一个正整数N ，若不是素数，则必 √有不超过的素因子。由此可得一个判别素数和构造（N 以内）素数表的方法：取最小的素数2， 计算（并淘汰）所有2的倍数，留下的数最小的是3，必是素数，在淘汰所有3的倍数，留下的最小 N 。这样剩下的全是素数。例1:
造100以内的素数，只需划掉2，3，5，7的所有倍数。例2: 判断137是否素数。只需用2，3，5，7，11去试除知它是素数。 例3：找出1000以内的最大的平方数a，还需满足a +2, a - 2都是素数。设a = n2，要使a +2, a - 2都 是素数，首先必须n是奇数，其次n必须是3的倍数（否则a + 2是3的）倍数，这样的n从大到小依 次是27, 21...。经检验17|272 + 2，但212 + 2, 212 - 2都是素数。故要找的数事212
= 441定理1.6.1. 素数有无限个证明：只需证明任意大的表都不能包括全部素数。设p1, p2, ..., pk 是前k个素数，则p1p2 · · · pk + 1不含这k个中任意一个作为素因子，故它的素因子必为新的素数。定理1.6.2. 4n - 1形素数有无限个证明：设p1, p2, ..., pk 是前k个4n - 1形素数，考察4p1p2 · · · pk - 1，它必有一个4n - 1形素因 子，这个素因子必为新的。1.7.
一次不定方程 11定理1.6.3.
若(a, b) = 1,则a + bn形素数有无限个 （这个定理的证明较深，现在没法证）定理1.6.4. 存在任意长度的等差数列，全是素数 这个定理是获Fields奖的工作。素数分布是数论中两类最基本的问题之一:还有大量的超难的未解决问题，比如Goldbach猜想和孪生素数猜想 1.7 一次不定方程数论中最重要的问题除了素数分布，还有不定方程：即解那些未知数较多（比方程个数）的 方程的整数解或有理数解。最简单的当然是线性方程 a1x1 + · · · + arxr = n (1) 其中a1, ..., ar不全为0 我们将从三个方面研究：判别何时有整数解，解的形状及何时有非副整数 解。 定理1.7.1.
方程(1)有整数解当且仅当(a1, ..., ar)|n证明：判别方程何时有解实际上是对集合A = a1Z + · · · + arZ进行分析，只要能说明 有d使A = dZ即可。注意A的简单性质：对加法运算封闭，也对整数倍（包括负的倍数）运算封 闭。取d是A中的最小正元，显然A ? dZ，如反包含不成立，则可取a ∈ A满足a ?∈ dZ，做带余出 发有a = dq + b, 0 < b < d，由A的性质知b = a - dq ∈ A，与d的最小性矛盾，说明A = dZ。易 知d必为最大公约数(a1,
..., ar)。定理证必。请在r = 2时与定理1.1.1进行比较。现在集中关心二元方程 ax + by = n (2) 不失一般性可设(a, b) = 1，有下列定理 定理1.7.2. 若(x0, y0)为方程(1)的一组整数解，则全部解为x = x0 + bt, y = y0 - at, t ∈ Z证明：由方程ax + by = ax0 + by0得a(x - x0) = b(y0 - y),这样，b|a(x - x0)，而(a, b) = 1， 故b|x - x0，因此可设x - x0
= bt，即x = x0 + bt，y = y0 - bt下面讨论对a, b, n都为正时，方程何时有非负整数解。显然，当n充分大时是有的，于是可以 问对确定的互素的正整数a,
b，最大的使方程(2)无非负整数解的n是多少？定理1.7.3. 当n = ab - a - b时，方程(2)无非副整数解，而当n > ab - a - b时，方程(2)一定有非 负整数解。 证明之前先看具体例子，若a = 8, b = 15，那么ab - a - b = 97，将n分别取97和100。12 CHAPTER 1.
唯一分解定理先解方程8x + 15y = 97。取适当的x，使97 - 8x是15的倍数，即8x ≡ 97 ≡ 7 (mod 15)，8x ≡-8 (mod 15)。由于(8, 15) = 1，故得x ≡ -1 ≡ 14 (mod 15). 即非负的x至少是14，x和y当然是97-8×14
一个变大，一个变小，因此要保持x非负，y至多是= -1。因此没有让x, y都非负的解。 15 再解8x + 15y = 100，还是模15知8x ≡ 100 (mod 15), 2x ≡ 25 ≡ 10
x ≡ 5(mod 15)，故可取x = 5，代入得y = 4。于是得到了x, y都非负的解。通过例子已经有了定理证明的思想。定理证明：先考察方程 ax + by = ab - a - b ≡ (3) 对x的要求是ax ≡ ab - a - b ≡ a (mod b),即x ≡ -1 (mod b)，因此最小的非负的x是b - 1，此 时y = -1。说明方程(3)无x, y均非负的解。现考察方程(2)在n > ab - a - b时的解，取r为使y为整数的最小x，那么0 ≤ r ≤ b - 1，此= -1，但因y为整数，故y ≥ 0。证毕。 时y = >b 问题上一个定理能否推广到三个以上未知数的情形。1.8 Fermat数与Mersenne数 n + 1的数称为Fermat数。看起来象素 形如Mp = 2p - 1的数称为Mersenne数；形如Fn =22数，其实未必。 命题1.8.1.
不同的Fermat数必互素 证明：由关系Fn(Fn - 2)(Fn+1 - 2) · · · (Fn+m-1 - 2) = Fn+m - 2立得。 Fermat曾猜测所有Fn都是素数。事实是：F0, ..., F4是素数，但F5已不是，甚至后面没有发现素数。 命题1.8.2. Mp的素因子必为2pk + 1形。这需要一个引理。引理1.8.3. 对正整数a, b, s，有(sa - 1, sb - 1) = (s(a,b) - 1)证明：显然左是右的倍数，只需证左整除右。记左边为d，则sa ≡ sb ≡ 1 (mod d). 设r是 满足sr ≡ 1 (mod d)的最小正整数。由带余除法可知r|a, r|b，故r|(a, b)。因此s(a,b) ≡ 1 (mod d)， 即d|s(a,b) - 1)。引理得证。用这个引理和Fermat小定理容易证明上述命题，留给同学们去证。关于完全数的有关结论， 也请自学。 Chapter 2 同余式 第三讲 周期问题 2.1 同余的概念及基本性质对整数a, b, m，称a模m同余于b，记为a ≡ b (mod m)是指a和b用m除的余数相同，换句话 说m|a - b。同余的最基本的性质是 a ≡ b (mod m), c ≡ d (mod m) ==> a + c ≡ b + d (mod m), ac ≡ bd (mod m) 或总结为对任意整系数多项式f (X) a ≡ b (mod m) ==> f (a) ≡ f (b) (mod m) 这一简单性质的简单应用如下： 例1 求2100被7除的余数 2100
× 2 ≡ 133
× 2 ≡ 2 (mod 7) 将集合{a + mZ} = {x ∈ Z|x ≡ a称为一个剩余类，显然对任意b ∈ a + mZ, a + mZ = b + Z， 同余的基本思想就是忽略一个剩余类中的不同的元的差别。 例2 证明奇数的平方被8除必余1 这是因为在模8的世界就只有8个数（模8有8个剩余类），其中有4个奇数1，3，5，7，依次验证可证。模m有m个剩余类，如果一组整数a1, a2, ..., am分别属于这m个不同的剩余类，称它们构成 模m的剩余系，最常见的剩余系是0, 1, ..., m - 1或1, 2, ..., m。由于(a, m) = 1 ==> 对任意b ∈ a + mZ, 有(b, m) = 1,1314 CHAPTER 2.
同余式因 此 我 们 可 以 说 某 个 剩 余 类 与m互 素，与m互 素 的 剩 余 类 的 个 数 记 为φ(m);如 果 一 组 整 数a1, a2, ..., aφ(m)分 别 属 于 这φ(m)个 不 同 的 剩 余 类，称 它 们 构 成 模m的 剩 余 缩 系。φ(m)成 为Euler函数（注意φ(1) = 1）。请牢记并熟练运用一个常用的结论：若(a, m) = 1，则同余方程ax ≡ b (mod m)有唯一解。这是因为在模m的世界与m互素的数 都可以求“倒数”。 2.2
周期命题2.2.1. 若(a, m) = 1，则存在正整数r，满足ar ≡ 1 (mod m);进一步，若r是有此性质的最小 正整数，则对任何满足ad ≡ 1 (mod m)的d，有r|d证明：考察序列a, a2, a3, ...。由于模m只有有限个类，故存在整数i > j > 0有aj ≡ ai = ajai-j (mod m)。因此ai-j ≡ 1。命题的第一部分得证，现证第二部分。若r不整除d，做带余除 法d = qr + s, 0 < s < r，于是as ≡ ad ≡ 1 (mod m)，与r的最小性矛盾。定义2.2.2. 满足ar ≡ 1 (mod m)的最小正整数r称为a模m的周期或次数或阶 例3：2模7的周期是3，2d ≡ 1 (mod 7)
3|d。例4 ：既约真分数何时是纯循环小数，混循环小数。
m n rm 是纯循环小数当且仅当存在r满足10
(mod m)当且仅当(10, m) = 1。10模7的次数 是6，故 1 6位循环小数；10模49的次数是42，故
是42位循环小数。下列重要定理对计算次数 7 49有用。 定理2.2.3. Fermat小定理。对素数p，和任意整数a有ap ≡ a (mod p)，若(a, p) = 1，则ap-1 ≡ 1 (mod p). .p. 证明：对任意整数a, b，有(a +b)p = ap +bp + ≡ ap +bp，但a可分为a个1相加，故ap i ≡ a(mod p)。p-1 i=1定理2.2.4. Euler定理。对整数a, m，若(a, m) = 1，则有aφ(m) ≡ 1 (mod m)取a1, a2, ..., aφ(m)为模m的一组剩余缩系，则aa1, aa2, ..., aaφ(m)为另一组剩余缩系，因此 a1a2 · · · aφ(m) ≡ aa1aa2 · · · aaφ(m) ≡ aφ(m)a1a2 · · · aφ(m)所以aφ(m) ≡ 1 (mod m)。 显然Euler定理是Fermat小定理的推广。现在我们可以用这两个定理证明10模49的次数是42。首先通过简单计算知10模7的次数是6（由Fermat 小定理知只需计算102, 103 mod 7）。 设10模49的次数是r，由Euler定理知d|φ(49) = 42，另一方面，因10d ≡ 1 (mod 7)，故6|d。从两 个整除关系知d = 6或42，简单计算知10d ?≡ 1 (mod 49)。故d = 42。2.3.
WILSON定理 151思考题：注意现象 = 0.. = 0.428571, ...，任何真分数7都是由同一组 7 7 7
1数字组成的循环小数，且只相差一个旋转。证明对素数p，若p - 1位循环小数，则同样的现象 p会发生。进一步，若将p 换成一般的正整数m，该如何推广。 第四讲 孙子定理及应用 2.3 Wilson定理定理2.3.1.
Wilson定理。对任意素数p，有(p - 1)! ≡ -1
(mod p)证明：当p = 2时，显然成立，现在设p为奇素数。对任意i ∈ A = {1, 2, ..., p - 1}，存在唯 一it ∈ A满足iit ≡ 1 (mod p)。将每个i与it配成一对，但当i = it，即i2 ≡ 1时，无其他元与i配对。 故Y Y(p - 1)! = i ≡ i ≡ 1 × (-1) ≡ -1 (mod p)i∈Ai2应用：对素数p ≡ 1 (mod 4)，存在整数a使得p|a2 + 1
证明：由于(p-i) ≡ -i (mod p), i = 1, ..., ，故(p-1)! ≡ )!(-1) ≡ )!)2 (mod p)，结合Wilson定理知2 2 22 2 )!)≡ -1 (mod p)，即p|+ 1 222 思考题：如何将Wilson定理推广到模奇素数幂的情形。 2.4 孙子定理现实或理论中都常遇到解不同模的同余式组 x ≡ a1 (mod m1)
· · ·x ≡ an (mod mn)这个问题的简单回答是：只要m1, m2, ..., mn两两互素，则（不论a1, ..., an如何取）同余式组一定有解，且解是一个模m = m1 · · · mn的剩余类。假如找到一个解a，显然剩余类a + mZ中的元都 是解，另外由x ≡ ai ≡ a (mod mi)得到mi|x - a，由mi两两互素知m|x - a，即x ≡ a (mod m)。 中国古人的贡献是找到一种有效的解法，即所谓的孙子定理，外国称为中国剩余定理（Chinese remainder theorem）。 m定理2.4.1. 设m1, m2, ..., mn两两互素，m = m1 · · · mn，Mi = m，则上述同余式组的解是ix ≡ a, a = a1M t + · · · + anM t ,1nMiM it
1 (mod mi)
≡16 CHAPTER 2.
同余式证明：首先将原始的同余式组归结到n个特殊情形，即 x ≡ 0 (mod m1)
· · ·x ≡ ai (mod mi)
· · ·x ≡ 0 (mod mn) i = 1, ..., n，只要将n个解相加即可。然后继续简化为： x ≡ 0 (mod m1)
· · ·x ≡ 1 (mod mi)
· · ·x ≡ 0 (mod mn) 只要将每个解乘上ai。而最后一个组简化为： x ≡ 1 (mod mi)x ≡ 0 (mod Mi)t，倒回去 而这又化为解Miy ≡ 1 (mod mi)。有解性由(mi, Mi) = 1保证。当得到最后一个的解M i即得定理的证明。t，即解相应的同余方程。 说明：这种方法需要计算n个M i例：解方程 x ≡ 2 (mod 4) x ≡ 3 (mod 25)解：先解4x ≡ 1 (mod 25) 得x ≡ 19 (mod 25)；再解25x ≡ 1 (mod 4)得x ≡ 1 (mod 4)。于 是得到 76 ≡ 0 (mod 4)76 ≡ 1(mod 25) 25 ≡ 1 (mod 4)25 ≡ 0 (mod 25)原同余式组的解是 x ≡ 2 × 25 + 3 × 76 ≡ 78 (mod 100)例: 求762009 + 252009的最后两位数字。解：由 76 ≡ 0 (mod 4)76 ≡ 1 (mod 25)2.5.
EULER函数的计算 17 知762 ≡ 76 (mod 100)，同理252 ≡ 25 (mod 100)。故762009 + 252009 ≡ 76 + 25 ≡ 1 (mod 100),因此，最后两位数字是0和1。实际上76和25就是通过x2 - x ≡ 0 (mod 100)解出的。 练习：找出两个三位数满足，任意方幂的后三位都不变。2.5 Euler函数的计算容易看出φ(pr) = pr - pr-1，因此一般的φ(n)的计算可有下列定理得出： 定理2.5.1. 如整数m1, m2互素，则φ(m1m2) = φ(m1)φ(m2)证明:取集合A, A1, A2分别为模m =
m1m2，模m1，模m2的各一组完全剩余系，做A到A1
×A2的映射σ : a -→ (a1, a2),其中ai由a ≡ ai (mod mi)确定。这个映射显然是单的，因为 a ≡ b ≡ b(mod m)(mod
mi), i = 1, 2 ==> a另外，因A与B × C均是有限集，且元素个数相等，故σ是双射。取集合B ? A，B1
?A2分别是模m，模m1，模m2的一组剩余缩系，则由(a, m) = 1
(a, m1) = (a, m2) = 1
(a1, m1) = (a2, m2) = 1知σ在B上的限制给出B到B1
× B2的一一对应。因此元素个数相等，故φ(m1m2)
= φ(m1)φ(m2)由此定理，对n = pl1
· · · plr ，有1rφ(n) = (p- p1 l1
l1-11Y1) · · · (p- p) = n (1 - )lr
rlr rp|n上述公式也可通过容斥原则得出：记Ci为1,
n中是pi的倍数的数构成之集合，则 ..φ(n) = n - |C1 ∪ · · · ∪ Cr| = n -
|Ci ∩ Cj | - · · · + (-1)r|C1 ∩ · · · ∩ Cr|1≤i≤r1≤i<j≤r 但|Ci ∩ Cj | =
p n ，故 pijY φ(n) = n -
+ · · · + (-1)r
(1 - 1 )pi i p1 · · · pr1≤i≤r 1≤i≤r. 即 1 Yφ(n) = n (1 - ) p|n容斥原则: 对有限集合C1, ..., Cr， |C1 ∪ · · · ∪ Cr| =..· · + (-1)r-1|C1 ∩ · · · ∩ Cr|
|Ci ∩ Cj | + ·1≤i<j≤r1≤i≤r18 CHAPTER 2.
同余式.φ(d) = nd|nEuler函数有一重要性质：证明：将n以内的正整数按(x, n)分类。记A = [1, n] ∩ Z，Ad = {x ∈ A|(x, n) = d}. 由于n n (x, n) = d
x = dy, n = d · , (y, ) = 1 d d故|Ad| = φ)。因为A = ∪d nA ，两边数数可得d|d 练习 1.求22100. n . n = φ) = φ(d)dd|nd|n的最后两位数字。n9
≡ n3 (mod 504)2. 证明对任意n，有 3.
对哪些n，2n - n2是7的倍数。4.
10000以内有多少n满足2n
+ n2是100的倍数。 5. 设n = pq，p, q为不同的奇素数，问模n的一组剩余缩系之积≡? (mod n)第五讲 高次同余方程 2.6 解同余方程的一般原则设有整系数多项式f (x)和整数m，如何解同余方程 f (x) ≡ 0 (mod m) (1)显然，方程的解是一些模m的剩余类。当我们谈论有多少个解时，只的是多少个剩余类，或在一 个指定的完全剩余系里有多少个解。看如下两个方程 4x ≡ 10 (mod 14)和2x ≡ 5 (mod 7) (2)(3)本来两个方程是等价的，但却应回答(3)有一个解x ≡ 6 (mod 7)，(2)有两个解x ≡ 6 (mod 14)， 和x ≡ 13
(mod 14)现回到方程(1)。一种万能的解法是穷举法，即将0, 1, 2, ..., m - 1依次代入检查，显然当m较 大时，这不是好办法。我们应当将它简化为更简单的方程。首先，将m分解为m = pl1
· · · plr ，从 而将(1)化为r个方程 if (x) ≡ 0 (mod pli ), i = 1, ..., r1 r如果得出上述方程的各一个解x ≡ ai
(mod pil i )，再用孙子定理可解出(1)的一个模m的解。2.7.
模素数幂的同余方程 定理2.6.1. 如果方程1r19if (x) ≡ 0 (mod pli )有ni个解，i = 1, ..., r，m = pl1
· · · plr ，则方程(1)有n1 · · · nr个解证明:由孙子定理立得。 例1：解方程x2 - x ≡ 0 (mod 100) 解：先解x2 - x ≡ 0 (mod 4)和x2 - x ≡ 0 (mod 25)，分别得到x ≡ 0, 1 (mod 4)和x ≡ 0,1 (mod 25)。再通过孙子定理得到四个解x ≡ 0, 1, 76, 25 (mod 100)总之我们将一般的方程(1)简化为解模素数幂的方程。 2.7 模素数幂的同余方程 由于f (x) ≡ 0 (mod pl) ==> f (x) ≡ 0 (mod pl-1) 因此我们在解方程f (x) ≡ 0 (mod pl)时，应该逐次解f (x) ≡ 0 (mod p), f (x) ≡ 0 (mod p2), ...著名的Hensel引理是说从f (x) ≡ 0 (mod p)的一个好的解可以提升得到f (x) ≡ 0 (mod pl)的一 个解。 引理2.7.1. Hensel引理。如果整数a0满足f (a0) ≡ 0 (mod p)，而f t(a0) ?≡ 0 (mod p)，则存在唯 一的整数序列a1, a2, ..., 0 ≤ ai ≤ p - 1使对任意l > 1,方程(2)f (x) ≡ 0 (mod pl)x ≡ a0 (mod p) 有唯一解x ≡ a0 + a1p + · · · +al-1p l-1(mod pl)这个引理的证明就是逐次解方程f (x) ≡ 0 (mod pl), l = 2, 3, ...。记x = a0 + px1，代入方 程f (x) ≡ 0 (mod p2)得f (a0 + px1) ≡ f (a0) + f t(a0)px1 ≡ 0 (mod p2), 因此f t(a0)x1 ≡ -(mod p)。有唯一解，记为x1
a1p。第归f (a0)(mod p2)。得到方程(2)在l = 2时的唯一解px ≡ a0 +l-2 地解方程，若解出x ≡ αl-2 = a0 + a1p + · · · + (mod pl -1)为al-2p f (x) ≡ 0 (mod pl-1)x ≡ a0 (mod p) ltf (αl-2)的 解，设x = αl-2 + p xxl ，代 入(2)并 化 简 得f (αl-2)xl-1
≡ - p (mod p)，也 有 唯 一解（因f t(αl-2) ≡ f t(a0) ?≡ 0 (mod p)）xl-1 ≡ al-1
(mod p)，由此得到(2)的唯一解 x ≡ αl-2 + p al-1 = a0 + a1p + · · · + al-1pl-1 l-1(mod p ) (mod p )l l20 CHAPTER 2.
同余式 例2。解同余方程 7x4
+ 19x + 25 ≡ 0 (mod 27)解：先解 7x4
+ 19x + 25 ≡ 0 (mod 3) 易知有唯一解x ≡ 1 (mod 3)。令x = 1 + 3y，代入 7x4
+ 19x + 25 ≡ 0 (mod 9) (3)并化简得6 + 6y ≡ 0 (mod 9)，即y ≡ 2 (mod 3)。那么(3)的解为x ≡ 7 (mod 9)。再设x = 7 + 9z， 代入原方程并化简得18 + 9z ≡ 0 (mod 27)，解得x ≡ 1 (mod 3)。因此原方程有唯一解 x ≡ 16 (mod 27) 例3：方程xp-1 - 1 ≡ 0
(mod pl) 解：由Fermat小定理知f (x) = xp-1 - 1 ≡ 0
(mod p)有p - 1个解1, 2, ..., p - 1，但f t(x) ≡-xp-1，故每个解都满足Hensel引理的条件，故都可得到原方程的唯一一个解，于是原方程
有p - 1个解。 练习1. 证明若f t(a) ≡ 0 (mod p)，则 f (x) ≡ 0 (mod p2) x ≡ a (mod p) 的解数是0或p。2. 若a1, ..., an是模p两两不同余的整数，问(x - a1) · · · (x - an) ≡ 0 (mod p3)有多少解。3. 方程有多少解。4. 证明方程xp-1 - 1 ≡ 0 (mod
pl)的全部解是 x(x - 1)(x - 2)(x - 5) ≡ 0 (mod 53) x ≡ apl-1(mod pl), a = 1, 2, ..., p - 12.8 模素数的同余方程模素数的同余方程并没有一个万能解法（除了穷举），但有如下定性结论 定理2.8.1.
拉格朗日定理。如果方程f (x) ≡ 0
p)解数不超过f (x)的次数degf2.8.
模素数的同余方程 21 这个定理的证明与通常证明一个数域上的代数方程相应结论是一样的。因为 ab ≡ 0 (mod d) ==> a ≡ 0 (mod p)或 ≡ 0 (mod p)因此对任意整系数多项式f (x), g(x)，有 {x ∈ Z|f (x)g(x) ≡ 0 (mod p)} = {x ∈ Z|f (x) ≡ 0 (mod p)} ∪ {x ∈ Z|g(x) ≡ 0 (mod p)},另一方面，由于f (x) = (x - a)g(x) + f (a)，故可得f (a) ≡ 0 (mod p)
存在a, 满足f (x) ≡ (x - a)g(x) (mod p)用以上两点通过归纳法可得定理证明。 这个定理有很多有趣的重要应用。首先可以重证Wilson定理：由Fermat小定理知xp-1-1 ≡ 0(mod p)有p - 1个根1, 2, ..., p - 1，再用拉格朗日定理知xp-1 - 1 ≡ (x - 1)(x - 2) · · · (x - (p - 1)) (mod p) 比较常数项知 -1 ≡ (-1)p-1(p - 1)! ≡ (p - 1)! (mod p)还可以证明下列结论： 定理2.8.2. 对正整数d|p - 1，有 (1)方程xd - 1 ≡ 0 (mod p)恰有d个根(2)对给定整数a，若存在b满足a
≡ bd，则称a是模p的d次剩余。 a是d次剩余 d
≡ 1 (mod p) a p-1证明：(1)因为xp-1 - 1 ≡ 0 (mod p)有p - 1个根，而xd - 1是xp-1 - 1的因子，由拉格朗日定 理立得xd - 1 ≡ 0 (mod p)的根数亦为次数，即d。(2)先证==>.
若a ≡ bd，则d ≡ bp-1
(mod p)。然后证明满足两边条件的数（在一个d, 2d, ..., (p - 1)d， 剩余系内）一样多。由(1)已知右边的有d次剩余1d这p - 1个列出的对象并不表示p - 1个剩余类。因为对任意b，满足xd ≡ bd (mod p)的x恰有d个 类x ≡ bαi, i = 1, ..., d，这里alphai表xd - 1 ≡ 0 (mod p)的那d个根。说明1d, 2d, ..., (p - 1)d中 每d个同余，那么d次剩余一共是 p-1d作为练习，证明下列结论（注意利用“法宝”：a与(a,
m)在模m的世界互为“倍数”）p-1 1. 对任意n，记d = (n, p - 1)，(1)方程xn ≡ 1 (mod p)等价于xd ≡ 1 (mod p), (2)
a是n次剩余当且仅当a是d次剩余。d2. 若a模p的次数是d，则ai模p的次数是d的类是ai，i过一个模d的剩余(i,d) 缩系。.3.
利用关系 φ(d) = n证明存在模p次数为p - 1的元。d|n22 CHAPTER 2.
同余式 Chapter 3 原根与二次剩余 第六讲 模p的原根 3.1 原根的存在性现在p固定表示奇素数，若g模p的次数是p -1，称g是模p的原根。换句话说，g, g2, ..., gp-1 ≡ 1 (mod p)表示了模p的剩余缩系。例如3是模7的原根，3的方幂依次为3,2,6,4,5,1。上一讲的练习3实 际是证明了模p的原根的存在性。现在我们用不同的方法证明之。方法一：记A表一个模p的剩余缩系，Ad表A中次数为d的元的集会，那么A = ∪d|p-1Ad .|A| = |Ad|d|p-1(1)我们将会看到|Ad| = φ(d)，但现在只知道 |Ad| > 0 ==> |Ad| = φ(d),即|Ad| = 0或φ(d)，总之|Ad| ≤ φ(d)，于是由(1)有. .p - 1 = |Ad| ≤ φ(d) = p - 1d|p-1 d|p-1说明以上都是等式，次数为任意d|p
1的都有φ(d)个，原根也一定有φ(p
- 1)个。 其他方法依赖如下引理（引理的证明留作练习）引理3.1.1. 若a的次数是m，b的次数是n，且(m, n) = 1，则ab的次数是mn。 方法二：设法证明“所有元素中次数最大者d是所有元的次数的倍数，”因为这就意味着所 有p - 1个模p非0的元都满足xd
≡ 1 (mod p)(2), 2324 CHAPTER 3.
原根与二次剩余 但满足(2)的只能是至多d ≤ p - 1个，说明d = p - 1。引号部分的证明需要下列引理（引理的证 明留作练习）现在证明引号部分：假如a的次数是d，是次数最大者，但b的次数是n
t，那么an的次数是ps，bp的次数是dt，由引理知anbp的次数是psdt > d，从而 与d的最大性矛盾。方法三：设p - 1的标准分解式为p - 1 = pl1
· · · plr ，先用拉格朗日定理证明存在次数为pli 的1ritttt元，再用引理。3.2 原根的判别准则 定理3.2.1. a是模p的原根当且仅当对p - 1的任意素因子q?≡ 1 (mod p)。 有a证明：记a的次数为d，则 p-1 qa非原根 1
存在素数| 存在素数q满足q q d dd|
存在素数q满足a p-1 q≡ 1 (mod p) n ?≡ 有a 1 (mod p)。则d与n的p部分相同（若qr||n，称qr为n的q部分） 例2：判别2是否是模13的原根。注：同样的思想可证（作为练习）记a的次数是d。若an ≡ 1 (mod p)，但对n的某个素因子q，计算3
≡ -1 (mod 13)12 12 例3：证明对奇素数p1
> p2，不存在m使p1p2|mp1-p2
+ 1证明：假设有这样的m，那么 mp1-p2
≡ -1 (mod p1)mp1-p2
≡ -1 (mod p2) 结合Fermat小定理知 mp2-1 ≡ -1 (mod p1) mp1-1 ≡ -1 (mod p2) 前一个式子等价于 m2(p2-1)
≡ 1 (mod p1) m(p2-1)
?≡ 1 (mod p1) 说明m模p1的次数d与2(p2 - 1)有相同的2部分，但d|p1 - 1，因此p1 - 1的2部分 > p2 - 1的2部分 对称地可说明 p2 - 1的2部分 > p1 - 1的2部分3.3.
二次剩余和勒让德符号 得出矛盾。25小结：给定奇素数p和ddt
· · · plr ，g是某一个模p的原根。对a ?≡
(mod p)，以1r下说法等价： (1) a是d次剩余(2) 满足gi ≡ a (mod p)的i是d的倍数 (3) ad≡ 1 (mod p)下列说法等价(1) a是d次剩余，但对任何满足d|s|p - 1, s > d的s，a不是s次剩余 (2) 满足gi ≡ a (mod p)的i满足(i, p - 1) = d(3) 存在一个原根α满足αd ≡ a (mod p) (4) a的次数是dt 特别地（取d = 1），下列说法等价 (1) 对p - 1的任何> 1的因子s，a不是s次剩余 (2) 对p - 1的任何素因子q，a不是q次剩余(3) 对p - 1的任何素因子q?≡ 1
(mod p) (4) 满足gi ≡ a (mod p)的i满足(i, p - 1) = 1 a(5) a是原根p-1 qt 判别原根时，计算ap最辛苦，但这等价于判别a是否是二次剩余，我们会有很好的 方法去做。 3.3 二次剩余和勒让德符号定义3.3.1. 设有奇素数p，与p互素的a称为模p的二次剩余，如果方程x2 ≡ a (mod p)有解，这就 是前面讲的d次剩余取d = 2易知在一个缩系中，二次剩余和非二次剩余各占一半，而且 a是二次剩余
a 2≡ 1 (mod p)由于a≡ ±1
(mod p)，故a是非二次剩余
a 2 ≡ -1 (mod p) 定义3.3.2. )称为勒让德符号， p 1, a是二次剩余 -1, 是非二次剩余 由定义立得 (a) )≡ a pp-12 (mod p)26 CHAPTER 3.
原根与二次剩余≡ ) (mod p) p p pp-( 1 (mod p) 因此有≡
-p由于上两式的两端取值都是±1，而p > 2，因此同余式变成等式。总结基本性质如下: (1) ( ≡ a2 (mod p) p p p p-1
-1(3) ( ) = (-2p-1经过一点计算可得另一基本性质： 22 (4) ( -p-1通过以上(2),(3),(4)条性质还不足以计算任意勒让德符号，还需要如下重要的二次互反律: (5)
对不同的奇素数p和q，有1 q-1) = (-1)(p-)() p qp( q ), p ≡ 1 (mod 4)或q ≡ 1 (mod 4) p-, p ≡ q ≡ 3 (mod 4) q或等价地说成 先不急于证明二次互反律，举个例子说明它的威力。因为( 353 3 ) = -1，故5是模353的非二次剩余。再算一个例子353 5 5 17 41 7 17 3 7 1) = () = () = () = ) = 117 17 7 7 ) = -3 ) = -3现在对具体p = 13，计算(
，从中可以看出计算一般的( 2 )的方法，也包含证明二次互反律13p所需高斯引理的思想。 因此S记A = {1, 2, 3, 4, 5, 6}，当然A (-A)是一剩余缩系。2A = 2, 4, 6, 8, 10, 12 ≡ {2, 4, 6, -5, -3, -1}，Y2(6!) = i ≡ (-1)3(6!) (mod 13)6i∈2A 2故26 ≡ -1 (mod 13)。这样( -1 13第七讲 二次互反律 3.4 Gauss引理我们来证明二次互反律，采用Gauss的初等证明，这需要一个关键的Gauss引理（不仅是结 论，包括2思想），而原始的思想正是来自计算( 2 )的方法，让我们从上次计算( 的方法开始： p 13记A = {1, 2, }，模p有两个最简单的缩系。一是 2[{1, 2, ..., p - 1} = A (p - A);3.5.
二次互反律的证明 一是S考察2A = {x1, ..., xn} {y1, ..., ym}，其中\ \{x1, ..., xn} = 2A A, {y1, ..., ym} = 2A (p - A)S同时因2A (-2A)也是一组模p的缩系，说明x1, ..., xn, -y1, ..., -ym模p互不相同，故[A (-A).27 A = {x1, ..., xn, p - y1, ..., p - ym} 于是 另一方面Yi ≡ (-1)mx1 · · · xny1 · · · ymi∈A p-1 2Y Y i = i = x1 · · · xny1 · · · ymi∈Ai∈2A 综上两式知 2
≡ (-1)m即2 ) = (-1)m。由m的定义:m是2A中p 的元的个数，即A中p 的元的个数，故m p ] - p ≡p2-1 8 p2424p2-1 28 (mod p)) = (-1) p S注:称集合A = {a1, ..., p-1 }为模p的一个半系，若A (-A)是一剩余缩系。显然，对任2 (mod 2)，这样， 意a ?≡ 0 (mod p)，aA仍是半系，因此aai = εibi, εi
= ±1, b1, ..., p-1 为a1, ..., p-1 的一个置2 2 p-1
mQ2 里m为ε1, ..., εp-1 中个 数，即≡ (-1) ，这 ≡ ε· · · ε -
1的 1 换，考 察i∈aA i可 得（在a 2 2模p下）aA与-A交的数目。前面的计算就是用这一简单想法，总结起来就是如下Gauss引 理 引理3.4.1. 设A为模p的一个半系，a ?≡ 0 (mod p)，aA = {x1, ..., xn, y1, ..., ym}，其中{x1, ..., xn}同 余于A的一个子集，{y1, ..., ym}同余于-A的一个子集。则) = (-1)mp-1取A = {1, 2, ..., p2，得到如下特殊形式的Gauss引理引理3.4.2. 设a, 2a, ..., 这些数对p的最小非负剩余中> m，则22 m) = (
p3.5 二次互反律的证明 现有不同的奇素数p, q。依次对q, 2q, ..., 2做带余除法kq = pqk + rk, 0 < rk < p28 CHAPTER 3.
原根与二次剩余，y> p 。另 外j 记{r1, ..., p-1 } = {x1, ..., xn, y1, ..., ym}，这 里xi2< {x1, ..., xn, p - y1, ..., p - ym}。求和有p-12A =
{1, 2 =2n m. . .rk = xi + yj k=1i=1 2(1)j=1和n m. .k = xi + (p - yj )k=1i=1 p-12p-1 2(2) 在(1)中用kq - pqk 换rk 得j=1 n m. . q k - p qk = xi + yj k=1k=1i=1j=1(3)现通过(2),(3)两式得出m的信息，由于我们只关心m的奇偶性即m mod
2，故对两式取模2（注意到p ≡ q ≡ 1 (mod 2)）可得 kq m ≡ qk
≡ [] (mod 2)k=1 k=1即 2p-1 ，同理] k=1(
p - p p-1 kqk=1 q
] -q于是. kq ]+. [ kp ]q ( )(
k=1 - k=1 p qp-1 q-1剩下只需证 ..[] + [] =
k=1 k=12222p2q-1 2(4)这需要利用长方形{(x, y)|0 < x < 0 < y < }。内部的整点数目是，沿对角线y = x分 成两个三角形内部的整点数目分别是 和 ]，而对角线上无整点，这就证明了(4)，从而 证明了二次互反律。k=1pk=1qp-1 2q-123.6 推广的二次互反律定义3.6.1.
· · · plr 为奇数，则可对与n互素的m定义Jacobi符号1rl1 · · · lr n p1 pr3.7.
特殊的二次同余方程的解 29注) = -1推出方程x2 ≡ m (mod n)无解，但) = 1不能推出方程x2 ≡ m (mod n)有nn解。Jacobi符号具有勒让德符号的相应的性质，特别是二次互反律： (1) 若a ≡ b (mod n)，则( ) = ( ) nnn n nn -1 (3) ( -2n2-12(4) ( n -1)(5) 推广的二次互反律。对互素的奇数m和n，有)() ) = (-1)(22n m这些性质的证明都留作练习，只简单说说(3)。设n = pl1
· · · plr ，则(3)归结为证明pl11rlr· · pr
·≡ l122归结为证明对任意奇数a, b有这是很容易证明的。p- 1+ + l (mod 2) · · · r 2+ (mod 2) ≡2 2
2用Jacobi符号，计算勒让德符号会更方便。因为算(
)时不必分解a，例如 p 353
9 143) = ( 143 ) = -129( 67 ) = 34 -( 67 ) = -1 353 ) = ( 143 353
2 17 17 95 10
5 17 2 129353 129 129 95 ) = ( 95 ) = ( 95 95 95 17 17 17 ) = ( 5 5 -1练习1. （利用Jacobi符号）证明2n - 1 + 3n - 1。你能否出一个类似的题。2. 设D为无平方因子的整数，用D*表示 D*
= D, 若D ≡ 1 (mod 4) 4D, 其它证明对奇素数p, q，有D Dp ≡ q (mod D*) ==> )p q3.7 特殊的二次同余方程的解用二次互反律很容易判别二次同余方程 x2
≡ n (mod p)是否有解，但如何解却不容易，在某些特殊情形下，解有某种表达式。 (5)定理3.7.1. 设p为奇素数，) = 1，p则 1) 当p ≡ 3 (mod 4)时，方程(5)的解为x ≡ ±np+1 4(mod p)30 CHAPTER 3.
原根与二次剩余 2)当p ≡ 5 (mod 8)时，方程(5)的解为 p+3 ±n8 (mod p), 若≡ 1 (mod p) x ≡ ±n n p-1p+3
≡ -1 (mod p) 2
)! (mod p), 若n 证明：1) 因n p-1 2≡ 1
(mod p)，（加1后变成偶数），故n ≡ n2p-1+1 得出(5)的解。p-1= (np+1 42 ) (mod p)2) 仍然n 2≡ 1 (mod p)，但2因子，此时 2 p-1p-14≡ ±1 (mod p) 分两种情形：若n 1 (mod p)，因1)的方法可得解为 4x ≡ ±np+38(mod p)若≡ -1
(mod p)，则p+3 p+3 8 2n ≡ -(n8
≡ (p - 1)!(np+32)2 ≡ (!)(n8
)2 (mod p) 2 从而得出方程(5)的解。 注：情形1)指p - 1恰有一个2因子；情形2)指p - 1恰有两个2因子。如果p - 1有三个以上2因 子，即p ≡ 1 (mod 8)，问题会复杂一些，如果借助一个给定的非二次剩余c，也可得到一个解的 表达式，只是复杂些，留作练习。 n定理3.7.2. 设p为奇素数，1，则对任意正整数l p 方程x2
≡ n (mod pl) (6)有两个解 t(±x) = ±2x?≡ 0 (mod p)，因此由Hensel引 证明：记f (x) = x2 - n，设(5)的解为±x0，则f 00理得到所要结论。 注：当p = 2时，方程(6)何时有解会更困难，作为练习讨论在什么条件下方程(6)有解。 第八讲 素数表平方和问题3.8.
素数表平方和主要定理313.8 素数表平方和主要定理定理3.8.1.
设p为素数，则p可表为平方和当且仅当p = 2或p ≡ 1
(mod 4) 必要性是显然的。由于p ≡ 1 (mod 4) ==> 存在整数m, 有p|m2 + 1。因此上述定理可由下列 定理推出 定理3.8.2. m2 + 1形的数的素因子都是平方和。这个定理的证明需要一个引理引理3.8.3. 若(x, y) = 1，称x2 + y2为本原平方和。如果一个原平方和x2 + y2的素因子p可表为x2+y2平 方也可表为本原平方和。 证明：设p = a2 + b2，则 a2 ≡ -b2 (mod p) x2
≡ -y2 (mod p)于是a2x2 ≡ b2y2 (mod p) ax ≡ ±by (mod p)若ax ≡ by
(mod p)（另一种情形同样证明，省略），则 x2 + y2 (a2 + b2)(x2 + y2) (ax - by)2 + (ay + bx)2)2 + (2 = == ( )p2 p2但由p|ax - by和和p|(a2 + b2)(x2 + y2) = (ax - by)2 + (ay + bx)2知p|ay + bx，因此表为平方p22 2 2) 现证明这种表示是本原的，若有d|)，则pp ay + bx d|ab= xp 同理d|y。由于(x, y) = 1，故d = 1。表示是本原的。 现在证明定理3.8.2：对m作归纳。m =
1时显然成立。假设对< m的整数成立。任取素数p
m，则p +12 +1 p p < m，于是p 是平方和，再由引理可得p = m 是（本原）平方和。
· · r m，当然每个p < 1 ·i ip|m2 + 1，若p|(m - p)2 + 12p1···pr定理3.8.1也随之得证。32 CHAPTER 3.
原根与二次剩余3.9 Gauss整数的算术注意到a2 + b2 = (a + bi)(a - bi)，前面的证明都可以在Gauss整数Z[i] = {a + bi|a, b ∈ Z}中进 行。我们说Z[i]按照加法和乘法构成环，称为Gauss整数环。我们先把Z上的算术理论搬到Gauss整 数环上。 命题3.9.1.
Z[i]上的单位（即可以求倒数的元）只有±1, ±i1
证明:设a+bi是Z[i]上的单位，则=∈ Z[i]，即, ∈ Z。从而a+bi = ±1, ±ia+bia2+b2a2+b2 a2+b2定义3.9.2.
称α为Z[i]上的“素元”，如果α的每一个因子β，都有ββ 或是单位。定理3.9.3. 对复数α = a + bi，用N (α)表a2 + b2。对任意α, β ∈ Z[i]，β ?= 0，存在γ, λ ∈ Z[i]，满 足α = λβ + γ和N (γ) < N (β); 也可以换种说法存在γ ∈ Z[i]满足α ≡ γ (mod β)和N (γ) < N (β)证法一（几何法）：不妨设N (α)
≥ N (β)，而且α与β（作为向量）不共线，断言:存在u=±1, ±i，使|α - uβ| < |α|（这样重复进行即可完成证明）。首先可取u1 = ±1，使α与u1β夹角为锐 角；然后可取u2 = ±i，使α与u2u1β夹角不超过45度。简单从三角形可看出|α - u2u1β| < |α| 法二：α = λ + δ，这里 1 1λ ∈ Z[i], δ = a + bi, a, b ∈ Q, |a| ≤ |b| ≤ 2 2于是N (δ) = a2 + b2 ≤21 < 1。并且α = λβ + δβ 一方面 另一方 δβ = α - λβ ∈ Z[i]面 N (δβ) = N (δ)N (β) < N (β)因此取γ = δβ即完成证明 推论3.9.4. 对α, β ∈ Z[i]，集合αZ[i] + βZ[i]一定形如γZ[i]证明略，这样的γ称为α和β的最大公因子，它是集合αZ[i] + βZ[i]中N (γ)最小的（即复绝对 值最小）。 推论3.9.5. （Z[i]上的唯一分解定理）Z[i]上的任何非零元可唯一分解为“素元”之积 注：证明就是平推旧的证明（因为有带余除法），但请仔细体会唯一的含义。 定义3.9.6. a + bi ∈ Z[i]称为本原的，若a与b互素3.10.
GAUSS整数的应用 33 任何一个Gauss整数可写为一个普通整数乘一个本原的Gauss整数，因此需问什么普通素数 还是“素的”，一个本原的Gauss整数何时是“素的”。 命题3.9.7.
普通素数p是“素的”当且仅当p不是平方和 证明：必要性是显然的，因为若p = a2 + b2，则p = (a + bi)(a - bi)。现证从分性：若p不 是“素的”，则p = (a + bi)(c + di)，因而p2 = (a2 + b2)(c2 + d2), a2 + b2 > 1, c2 + d2 > 1，说 明a2 + b2 = p = c2 + d2，矛盾。命题3.9.8. 本原的Gauss整数a + bi是“素的”当且仅当a2 + b2是素数 证明:先证从分性。若a+bi不是“素的”，那么a+bi = (c+di)(A+Bi)，且a+bi,
c+di都非单位，于是a2 +b2
= (c2 +d2)(A2 +B2) 非素数。再证必要性。若a2 +b2不是素数，则a2 +b2
= mn，m, n都 是?1的整数，但(a + bi)(a - bi) = mn且a - bi也必是“素的”，由于唯一分解性成立，必然m, n都是素数，且“素”，还必须m, n分别 与a + bi, a - bi相伴（即差一个单位），但这是不可能的。 3.10 Gauss整数的应用现在我们用Gauss整数的算术理论重新证明和解释关于平方和的定理。 先证定理3.8.2：若p|m2 + 1 = (m + i)(m - i)，显然p + m + i, p + m + i。由Gauss整数的唯一分解性知p不是“素的”。再由命题3.9.7知p是平方和。 虽然不需要引理3.8.3了，我们还是回头重证引理3.8.3了：因为a2 + b2=素数p，故由命题3.9.8知a + bi是“素的”，由条件(a + bi)(a - bi) = p|x2 + y2知 a + bi|(x + yi)(x - yi) 必然a + bi|x + yi或a + bi|x - yi。若前者成立，记 (a + bi)(c + di) = x + yiy则有(a2 + b2)(c2 + d2) = x2 + y2，即c2 + d2 x+c, d是多少，就：22 从而c =ax+byc + di = x + yi (a - bi)(x + yi) ax + by ay - bx= + i2 2= p 我们再讲一个Gauss整数在不定方程中的应用。 解：经过简单讨论知y为偶数。将方程变形为例1 在整数范围内解方程y2 + 1 = x3。 (y + i)(y - i) = x334 CHAPTER 3.
原根与二次剩余 设法说明y + i与y - i“互素”。若它们有公共“素因子”π，则π|2i = (1 + i)2，即π = 1 + i，但 因y = 2n = -i(1 + i)2n，故y + i ≡ i (mod 1 + i)，说明1 + i + y + i。综上，y + i与y - i“互素”。 由唯一分解定理知y + i = u(a + bi)3, u是一单位 由于所有单位±1, ±i都是某元的三次方，故可设y + i = (a + bi)3比较虚部知1 = 3a2b - b3 = b(3a2 - b2)。说明b = ±1，进一步讨论知必须b = -1, a = 0 原方程解为x = 1, y = 0例2 在整数范围内解方程x2 + y2 = z10, (x, y) = 1。解：简单讨论知x, y一奇一偶，易知x + yi, x - yi“互素”，因此x + yi = u(a + bi)10，u = ±1, ±i给出全部解。 3.11 小结Gauss整数的研究显然给了我们（相比平方和问题本身）更多。特别是给我们以启发：即使 我们只关心Z中的问题，我们也常常需要跳到Z以外去。关于Gauss整数环中的“素元”可以重新 刻划如下：(1)pu，p是一个4k + 3形的素数，u是单位。 (2)满足N (α)是普通素数的α√√Gauss整数的算术理论还可推广到其他一些环Z[ ]中，请想想，什么d使得有好性质。Z[ 练习 1.
证明对任意Gauss整数x + yi，有 0 (mod 1 + i), 若x ≡ y (mod 2)x + yi ≡1 (mod 1 + i), 若x ?≡ y (mod 2) 2.
证明所有的素数中只有2有一特殊性质：在Gauss整数中有平方因子。3.
研究Z2]的带余除法及唯一分解性，然后证明对奇素数p，2 p可表为a2 + 2b2 ) = 1
p ≡ 1, 3 (mod 8)p 4. 解不定方程y2 + 2 = x35.（思考题）解不定方程y2 + 5 = x3 第九讲 模m的原根3.12.
模M 的原根存在的条件353.12 模m的原根存在的条件对m > 1，称整数g是模m的原根若g模m的次数是φ(m)。换句话说g的方幂给出一组剩余缩 系。基本问题是对什么m，模m
的原根存在？如果存在，怎么找？先看一个有用的引理 引理3.12.1. 若m = m1, m2，(m1, m2) = 1，整数a模mi的次数是ri，i = 1, 2，则a模m的次数 是r1与r2的最小公倍数[r1, r2]证明：对任意正整数n，有 an ≡ 1 (mod m)
对i = 1, 2, an ≡ 1 (mod mi)
对i = 1, 2, ri|n
[r1, r2]|n这个引理给出一个原根存在的必要条件 推论3.12.2.
模m的原根存在的必要条件是m是以下三类之一：pl, 2pl，p为奇素数，2a证明：设m
· · · plr ，那么φ(m)
φ(pl1 ) · · · φ(plr )，由引理知模m的最大次数不超过[φ(pl1 ), ..., φ(plr )]。因此模m的原根存在的必要条件是所有φ(pli )两两互素，说明m只有至多一1 r i 1 r 1 r个奇素因子。若m确有奇素因子，设m = 2apl，由φ(2a)为奇（与p - 1互素），知a = 0, 1，也就是 前两种情形；若m无奇素因子，则为后一种情形。下面研究模pn的原根，为此先给一个可用二项式定理简单证明的引理（详细证明留作练习）引理3.12.3.
设p为素数，n是正整数，则 a ≡ b (mod pn) ==> ap ≡ bp (mod pn+1)这个引理可以得出如下推论 推论3.12.4.
设p为素数，n是正整数，则 a是模pn+1的原根 ==> a是模pn的原根 证明：若a不是模pn的原根，则有正整数r < φ(pn)，满足ar
≡ 1 (mod pn)再由引理3.12.3知arp ≡ 1 (mod pn+1),而rp < pφ(pn) = φ(pn+1)，与a是模pn+1的原根矛盾。 由推论，我们知道应该通过模p的原根来造模pn的原根。定理3.12.5.
设p为奇素数，整数g是模p的原根，则：(1)gp-1 ?≡ 1
(mod p2) ==> 对任何正整数n, g是模pn的原根(2)gp-1
(mod p2) ==> 对任何正整数n, g不是模pn的原根36 CHAPTER 3.
原根与二次剩余证明：(1)设g模pn的次数是r，则由gr ≡ 1 (mod p)得p - 1|r，另外必需r|φ(pn) = pn-1(p - 1)。
因此可设r = ph(p - 1), h ≤ n - 1，由定义即可知 g是模pn的原根
gpn-2(p-1)
?≡ 1 (mod pn) (1)但因gp-1 ?≡ 1 (mod p2)，可设 gp-1
≡ 1 + ap (mod p2), a ?≡ 0 (mod p)由上述引理和二项式定理可得 gp(p-1) ≡ (1 + ap)p ≡ 1 + ap2 (mod p3)重复这个过程（即归纳）可得 gpn-2(p-1) ≡ 1 + apn-1 ?≡ 1 (mod pn),结合(1)式知g是模pn的原根。(2)若gp-1 ≡ 1
(mod p2)，反复用引理3.12.3知gpn-2(p-1) ≡ 1 (mod pn )故g不是模pn的原根。 推论3.12.6. 设p为奇素数，则对正整数n，模pn的原根存在 证明：取整数g为模p的原根。因为(g + ap)p-1 ≡ gp-1 + a(p - 1)p ≡ gp-1 - ap (mod p2)当a过一个模p的完全剩余系时，总有p - 1个g + ap满足(g + ap)p-1 ?≡ 1 (mod p2)也就是说g是模pn的原根。特别地：若g不是，则g + p一定是。 命题3.12.7.
设对整数n ≥ 3，模2n没有原根证明：对任意奇数a，a2 ≡ 1 (mod 8)，故模8没有原根，由推论3.12.4知模2n也没有定理3.12.8.
模m的原根存在的充要条件是m是以下四类之一：pl, 2pl（p为奇素数），2，4 证明：由推论3.12.2和命题3.12.7立得必要性；充分性只需分别验证即可。因为pn已经有原 根g，再要求(g, 2) = 1即可。孙子定理说明可行。剩下两类的验证是平凡的。例：对什么n，有100|2n + n2？3.13.
指数 37解只要2|n就可保证4|2n + n2，剩下只需让25|2n + n2，即-2n ≡ n2 (mod 25)由2是模5的原根和24 ?≡ 1 (mod 25)知2是模25的原根，210 ≡ -1 (mod 25)。那么2n+10
≡ n2 (mod 25)当n过模20的完全剩余系时，2n+10过模20的剩余缩系，上式成立的必要条件是2n+10是模25的 平方元，即n是偶数（与一开始的要求相符）。现 依次取n ≡ 0, 2, 4, ..., 18
(mod 20)得到n ≡±25, ±26, ±27, ..., ±214 (mod 25)。这样得到20个同余式组:n ≡ 2k (mod 20) , k = 0, 1, ..., 9, k+5 n ≡ ±2(mod 25)其中可解出4组模100的解。这里，只写出一组 n ≡ 6 (mod 20)n ≡ ±28 (mod 25) 即n ≡ 6 (mod 100)。练习1. 证明对整数a, b和素数p|a - b，有pr||a - b ==> pr+1||ap - bp（pr||a - b指pr|a - b，但pr+1 + a - b）注:这比引理3.12.3更强。2. 仔细检查定理3.12.5的证明中，哪一步对p = 2不成立。3.设p为素数，a模pn的次数为rn，证明rn+1
= rn或prn。 3.13 指数设g是模m的原根，(a, m) = 1，则存在唯一整数d，满足0 ≤ d < φ(m)和gd ≡ 1 (mod m)， 称d为a对g的指数（或离散对数），记为indg
a，有时可简单记为inda。于是有以下性质：indab ≡ inda + indb (mod φ(m))indan ≡ ninda (mod φ(m))对d|φ(m)，有a是模m的d次剩余当且仅当d|inda，特别地对奇素数p，有：a是模p的2次剩余当且仅当2|inda 练习求模49的一个原根，并求ind238CHAPTER 3.
原根与二次剩余3.14 公钥密码应用现在简要介绍两种公钥密码体制：由公开的加密密钥不能在有效时间内算出解密密钥的密 码体制。1. RSA体制取一个整数m = pq，p, q是不同的大素数，再取整数d，满足(d, φ(m)) = 1。将信息翻译 成m以内的正整数，按如下方法加密信息a， f (a) = b ≡ ad (mod pq), 解密方法是a ≡ be (mod pq)e由关系de ≡ 1 (mod (p - 1)(q - 1))确定。 公开m和d，但保密p和q，这样其他人无法计算φ(m)（除非他能分解m），因此无法得到解密密钥e。因此RSA体制是建立在大数分解这一难题基础上。 2. 离散对数体制对一个大的素数p，和给定的原根g，计算inda也没有快速算法，但计算xn mod p却有快速算 法，基于此有下列公钥密码体制：公开p，g，和a ≡ gr (mod p)，r很大。保密r。加密方案：甲方（不知r，只知a）要向乙方发送信息x（某一小于 的整数）。先取一大的随机数n， 2计算gn ≡ b (mod p)和anx ≡ y (mod p)，然后发送数组(b, y)解密方法：利用关系brx ≡ y (mod p)可算出x。 由于只有乙方知道r，故只有乙方才能解密。当然若某人有计算离散对数的快速算法，他就可破译。 注：这里只是简单介绍了数学原理，实际使用中有些变化。但这类基于数学（计算）难题的 公钥密码体制的确已经使用，而且带来了方便。因为发放密钥更方便，甚至不需要通信双方是朋 友关系。深刻的现代数论也不断地在密码领域找到应用。第十讲 必备的抽象代数（上） 3.15
群的概念及例子定义3.15.1.
设G是一个集合，G上有一个运算o，即一个G × G到G的映射，将元素对(a, b)的像 记为a o b。如果运算满足以下性质三条：1) 结合律。对任意a, b, c ∈ G，有(a o b) o c = a o (b o c)2) 单位元（或称恒等元）。存在e ∈ G，使得对任意a ∈ G，有a o e = e o a = a3.15.
群的概念及例子 393) 逆元。对任意a ∈ G，存在b ∈ G，使得a o b = b o a = e。称b为a的逆元 称G关于运算o构成一个群，或称(G, o)是一个群。有时简单地说G是一个群。如果进一步满足对 任意a, b ∈ G，有a o b = b o a，称G是一个交换群或abel群。注:单位元是唯一的，一个元的逆元也是唯一的。在群中a o b = e等价于b o a = e，这时a与b互 为逆元，记b = a-1。群运算最常见的是记为乘法·和加法+。但通常有个约定：只有abel群的运算 才可记为加法，这时逆元记为-a，也会有na（n为整数，a ∈ G）的记号；如果运算记为乘法·，常 常省略·，简单记a
b为ab，同时有记号an。群有如下基本性质：对群G中任意给定的元a, b，方程ax = b和ya = b都在G中有唯一解。 现看基本的群的例子： 例1：整数集Z按通常的加法成为群，常称整数加群。 例2：有理数集Q，实数集R和复数集C按通常的加法成为群。例3：集合Q*，R*和C*按通常的乘法成为群（这里加*表示去掉0的剩余部分）。 以上的群都是abel群，下面看一个非交换群。 例4：k上全体n阶方阵(GL)n(k)按矩阵乘法构成的群，k = Q, R或C。 下面两个例子是初等数论中常见的:例5：对整数n > 1，Z/nZ表示集合 {i + nZ|i ∈ Z} = {i + nZ|i = 0, 1, ..., n - 1}定义加法运算:(i + nZ) + (j + nZ) = {x + y|x ∈ i + nZ, y ∈ j + nZ} = (i + j) + nZ。现在简单 = i + nZ，那么Z/nZ = i|i = 0, 1, ..., n - 1}按加法成为一个abel0 = nZ为单位元。 例6：对整数n > 1，Z/nZ的子集合 |i ∈ Z, (i, n) = 1} 按照乘法运算： 构成群，也是abel群，记为(Z/nZ)×1。需注意的是要验证乘法运算的合理性==> =同时不再有({x ∈ ∈为了识别抽象的群，需要如下基本概念： 定义3.15.2. 设G1，G2是群。G1到G2的双射f 称为一个同构，如果满足 对任意a, b ∈ G1, f (ab) = f (a)f (b).如果存在这样一个f ，称G1同构于G240CHAPTER 3.
原根与二次剩余例：下列三个群互相同构(Z/pZ)×, Z/(p - 1)Z, Up-1Un = {z ∈ C|zn = 1}看一个简单的群论定理 定理3.15.3. 四个元素的群（叫四阶群）只有两个同构类。即可以给出两个不同构的四阶群，任 何四阶群都同构于两者之一。这个定理的证明留作练习，我们通过它看出群论的定理的味道。我们可以数论地给出这两个 群Z/4Z, (Z/8Z)×粗略地说：抽象代数是研究抽象的群，环，域等代数对象；数论是研究具体的群，环，域等对 象。 3.16 似曾相识的群理论定义3.16.1.
设G是群（运算记为乘法，单位元为e），a ∈
G，满足ar = e的最小正整数r称为a的 阶。如果没有这样的r，称阶为无穷。因此将群中元素分成有限阶元和无限阶元两部分命题3.16.2.
若a是群G的r阶元，则an = e
r|n命题3.16.3.
设G是n阶abel群（即含有n个元），则(1) （Euler定理的推广）对任意a ∈ G，有an = e(2) （Wilson定理的推广）G中所有元之积等于所有2阶元之积。 证明方法都完全一样。需注意(1)对非abel群也成立，只是证法不同。命题3.16.4.
设G是abel群，a ∈ G是n阶元，则as的阶是 (s,n)命题3.16.5. 设G是abel群，若a ∈ G是n阶元，b ∈ G是m阶元，且n和m互素，则ab的阶是nm命题3.16.6. 设G是有限abel群，若a是G中阶最大的元，则a的阶是所有元的阶的倍数 这些命题的证明都不过是把以前的证明用抽象的语言重新写一遍。定义3.16.7.
如果群G具有形式G =
{am|m ∈ Z}，称G是循环群，a称为G的生成元。 定理3.16.8.
如果群G是循环群，则G同构于Z或Z/nZ证明：设G = {am|m ∈ Z}，分两种情形：a是无限阶元或有限阶元。前者，可证明G同构于Z； 后者，可设a 的阶为n，可得G同构于Z/nZ。定理3.16.9. n阶abel群G是循环群的充要条件是对任意m|n，满足xm = e的群元x至多有m个。 证明：尽管还是老方法（类似于模p的原根存在性的证明），这里还是简要写一遍。必要性：因G是循环群，故G同构于Z/nZ，容易看出满足xm
e的群元x的个数恰为m个。再证充分性：设a是G中阶最大的元，它的阶为m，由命题3.16.6知m是其它元的阶的倍数，故G中的所有（n个） 元都满足xm = e，结合条件知n ≤ m，但因m是某元的阶，故m|n，因此m = n，说明G是以a为生 成元的循环群。3.17.
基本的群论定理413.17 基本的群论定理定义3.17.1. 如果群tt有子集H，满足(1)a, b ∈ H ==> ab ∈ H(2)a ∈ H ==> a-1 ∈ H，则称H（按照从tt中继承的运算）成为tt的子群，通常说H是tt的子群， 常记为H < tt对群tt的子群H和元素a ∈ tt，集合aH = {ah|h ∈ H}称为一个左陪集，同样可定义右陪集。
命题3.17.2.
如果群tt有子群H，则aH = bH
aH与bH 不交 S结合tt =
att有如下推论a∈G定理3.17.3. tt是有限群，H是tt的子群，则H的阶整除tt的阶 练习：证明对有限群，元素的阶整除群的阶。定义3.17.4.
群tt的子群H称为正规子群，记为H a tt，如果满足对任意a ∈ tt，有aH = Ha 定义3.17.5.
设群tt有正规子群H，在集合 tt/H = {aH|a ∈ tt}中定义运算(aH)(bH ) = abH ，然后tt/H成为一个群，称为tt对H的商群（当然需验证运算的合 理性！，作为练习）。注:一般地，aH = Ha并不意味着ah = ha对每个h ∈ H成立。当然若tt是abel的，则任何子 群都是正规的，因此可以做商群。例如：Z对nZ做商得Z/nZ 例：集合{1, 2, 3}到自己的全部双射 构成群（记为S3），它有2阶和3阶子群，其中3阶子群（只有一个）是正规的，但2阶子群就不是。定义3.17.6.
群tt1到tt2的映射f 称为一个同态，如果对任意a, b ∈ tt，有 f (ab) = f (a)f (b) 如果分别记e1，e2为两个群的单位元，则容易推出f (e1) = e2, f (a-1) = f (a)-1定理3.17.7.
同态基本定理。设f 是群tt1到tt2的一个满同态（即是同态，又是满射），则1) Kerf := {x ∈ tt1|f (x) = e2}是tt1的正规子群2) 存在tt1/Kerf 到tt2f 定(a) = f (a)证明:1) 容易验证Kerf 的确是子群，现验证是正规的：对任意a ∈ tt1和x ∈ Kerf ，有f (axa-1) = f (a)f (x)f (a-1) = f (a)f (a-1) = f (aa-1) = f (e1) = e2故axa-1 ∈ Kerf ，即aKerfa-1
? Kerf ，注意到a的任意性可知aKerfa-1 ? Kerf。因此aKerfa-1 = Kerf42 CHAPTER 3.
原根与二次剩余即Kerf 正规。2) 的a ，则a = bx, x ∈ Kerf ，于是 f (a) = f (b)f (x) = f (b)e2
= f (b) 是合理的。再证明是满的：由于f 满，故tt2中每个元都可以写成f (a(a)最后证明 是单的：) )，则f (a) = f (b)，于是f (a)f (b)-1
= e2，即f (ab-1) = e2，ab-1
∈ Kerf ，因此aKerf = bKerf ， 单。的单性，而这本质上是把tt1中映到同一个元的不同元强行看成一个。例：用同态基本定理证明Z/nZ同构于任意n阶循环群。例：考察线性方程组XA = α，X ∈ Rn，α ∈ Rm，A是一个n × m矩阵。线性方程理论说方程组的 通解=一个特解加相应的齐次方程的通解，那么用同态基本定理如何解释？ 最后，不证明地给出一个大的定理，有限abel群结构定理。首先，对几个已知群tt1, ..., ttm， 可以造出一个较大的群tt1 × tt2 · · · × ttm（它的群运算可以猜出）。命题3.17.8. 素数幂阶循环群Z/prZ不可能同构于形如tt1 × tt2 · · · × ttm，m > 1的群，当然tti的 阶大于1 这个命题的证明留作练习，只需比较元素的阶即可。 定理3.17.9. 任何阶数大于1的有限abel群同构于形如tt1 × tt2 · · · × ttm，m > 0的群，tti是素数 幂阶（大于1）循环群 这个定理的证明较长，有兴趣的同学可参阅我的抽象代数讲义。请比较这个定理和算术基本 定理。练习1.
72阶abel群有几个（同构类）？2.
设f 是群tt1到tt2的一个同态，则完全像f (tt1)是tt2的一个子群，且同构于tt1/Kerf 第十一讲 必备的抽象代数（下） 3.18 环和域的概念及例子定义3.18.1. 集合R带有两个运算加法“+”和乘法“·”，称(R, +, ·)是一个环或简称R是一个环， 如果(R, +)构成成交换群，乘法满足结合律且有乘法单位元；另外，乘法对加法有分配律。通常 用0和1记加法和乘法单位元。3.18.
环和域的概念及例子 43注记 有些书中的环可以没有乘法单位元1。 定义3.18.2. 对一个环R，若乘法交换，则称R为交换环；若非0元之集R*构成乘法群，则称R为 除环;交换的除环称为域；若对任意非零的a, b
R，都有ab ?=
0，称R是整环。例1：Z是环，是看起来最简单其实最难的环，高等代数中讲了一个与Z平行的环―某个域上 的多项式环Y[X]。例2：Q, R, C是域（当然也是环）。例3：整数剩余类环Z/nZ。 例4：环Z[i]，Z[。这些例子都是交换环，非交换环的例子有:例5：矩阵环Mn(k)，k为任意一个域，n > 1。 以上的例子除了例2和例3都不是整环。例2当然是整环，但例3只在n为素数时才是整环。事 实上，对素数p，环Z/nZ 是域。作为练习，可以证明域一定是整环。类似于子群，我们也可定义 子环，子域商环的概念。子环―环R的一个子环是指R的一个子集，它关于R的运算和乘法单位元构成环。注意常常 有如下说法： 域k的子环R，环A的子域L。但是，环并不能对子环做商，只能对一被称为理想的对象做商。 理想―环R的一个子加群I，如果满足 a ∈ R, b ∈ I ==> ab ∈ I, ba ∈ I, 称I为R的理想。商环―设R是环，I是R的理想，则加法商群R/I = {a + I|a ∈ R}中再定义(a + I)(b + I) = ab + I， 可得到一个环，称为R对I的商环，仍记为R/I. a = a + I. 环同态―两个环之间的映射，它保持运算和乘法单位元1. 注记―保持1这个要求并非多余的，例： φ : Z/3Z -→ Z/15Z1 -→ 10, 2 -→ 5这个φ保持运算,但不保1. 从R到商环R/I有自然同态a
a。而且有环的同态基本定理，在任何抽象代数的书上都能 查到，但我希望同学们自己把它猜出来并证明。44CHAPTER 3.
原根与二次剩余3.19 环的算术性质我们现只关心交换环，进一步只关心整环。这样的环上有整除的概念。把交换环R上的乘法 可逆元称为单位，单位的全体形成一个群，记为R×。我们已经在数论中用过一些环（比如例4）， 它们都有相应的唯一分解定理。我们将看到某些环没有这种性质。 定义3.19.1. 对一个整环R中的非单位且非零的元素a，若a = bc ==> b或c是单位，则称a为既约元；若a|bc ==>
a|b或a|c，则称a为素元注记―既约元的概念是素数按原始定义的推广，素元的概念是素数按那个等价性质的推广。 显然素元一定是既约元。而证明算术基本定理的关键就是证明对整数环这两个概念一致。 定义3.19.2. 一个整环R称为唯一分解整环（记为UFD），如果R中的任何非单位且非零的元 素a都可“唯一地”分解为既约元的积。 定理3.19.3.
一个整环R是UFD当且仅当以下两条同时成立(1) 不存在无限长的理想序列 (2) 既约元一定是素元a1R ? a2R ? · · ·这个定理的证明很简单（留作练习），就是把证明原始的唯一分解定理的基本步骤抽象出来。 原始证明的关键是带余除法，于是 定义3.19.4. 由一个元素生成的理想(a) = aR称为主理想；如果R的所有理想都是主理想，则 称R为主理想整环。 定义3.19.5. R称为Eulcid环如果存在一个映射φ : R* -→ Z>0，使得对任意a ∈ R, b ∈ R*,一定 有q, r ∈ R使a = bq + r, 且r = 0或φ(r) < φ(b).注记 可理解为a可modb同余于一个比b小的元。 定理3.19.6.
Eulcid环一定是主理想整环；主理想整环一定是UFD 定理的证明留作练习。事实上，Eulcid环推主理想整环以及Eulcid环推UFD 完全是老方法的 新（抽象）叙述，只是主理想整环推UFD时有一小步有一点新意。注意:R是主理想整环意味着集
合aR + bR一定可表为cR的形状。 练习: √ 1. 对d = -1, ±2, 3，是Eulcid环。 Z[2. 对环R = Z[X]，不存在f ∈ R满足2R + XR = f R3.20.
理想的运算453.20 理想的运算\I J, I + J = {x + y|x ∈ I, y ∈ J }前面定义了理想，事实上理想之间可以运算。对交换环R的理想I, J ，有 . IJ {xiyi|m ∈ N, xi ∈ I, yi ∈ J }i=1m即IJ 是包含{xy|x ∈ I, y ∈ J }的最小的理想。特别地I = aR, J = bR ==> IJ = abR若I = a1R + · · · + anR，称I由a1, ..., an生 成 或a1, ..., an是I的（一 组）生 成 元；若 另 有一 理 想J 由b1, ..., bm生成，则IJ 由aibj, i = 1, ..., j = 1, ..., m生成。在Z中，有aZ ? bZ
a|b aZ + bZ = (a, b)Z\aZ bZ = cZ, c = l.c.m.[a, b]事实上，理想这个概念产生于数论。看一个例子：解方程 y2 + 5 = x3√分析 从前的经验告诉我们应该利用环Z[，但它不再是唯一分解环。看√√2 × 3 = (1 + - 但Kummer（在研究Fermat大定理时）认为上式不应推翻唯一分解性，就像(1) (2 × 3) × (5 × 7) = (2 × 7) × (3 × 5)并未推翻Z的唯一分解性一样。为此需将(1)的两端继续分解为4个量√√√√(2, 1 + , (2, 1 - , (3, 1 + , (3, 1 -相乘。上述4个元被（Kummer）称为“理想数”，环上的元素被视为“正宗”数。当然，他引进了
形如(a1, ..., an)的理想数（强行当作最大公约数）以及它们之间的乘法规则从而恢复了唯一分解性。其实，那就 是今天说的理想，只要把理想作为子集合而不作为数就不难理解了。 为能解这个方程，我们列出关于这个环Z[的两个基本事实（它蕴含在未来的定理中）：√事实1 环Z[的任意非零理想可唯一分解为素理想之积。事实2
对环Z[的理想I,
若I3为主理想，则I为主理想。46 CHAPTER 3.
原根与二次剩余解
首先通过简单分析知x为奇，y为偶，将原方程变为一个关于理想的等式√(y + y - x)3 √√√√易知理想(y + 与(y - 无公因子，即理想(y + - 为单位理想，故由事实1知 存在理想I使(y + I3,再由事实2知I亦为主理想，可设I = (a + 5),代入前面的理想方程得√(y +
= (a + b3, √y +
= u(a + b3,这里u为环Z[的单位，必然u = ±1,可设√y + = (a + b3,简单比较虚部知上式不可能成立，从而，原方程无解。3.21 域的“熟知”定理高等代数中讲的是一个“数域”（即现在说的复数域的子域）上的线性空间理论，完全可以推 广到任意域上。前面讲的拉格朗日定理是关于域Z/pZ的，以前有关于实数域和复数域的类似定 理，其实也可推广到一般域： 定理3.21.1.
域上n次多项式至多有n个根定理3.21.2. 域的乘法群的有限子群一定是循环群 证明：设域为k，tt是的n阶乘法子群，由拉格朗日定理知对任意m|n，方程xm = 1在k中的解至多有m个，从而在tt中的解也至多有m个。由有限abel群是循环群的判别准则立得。取k = Z/pZ得到模p的原根存在。 Chapter 4 数论函数 第十二讲 基本的数论函数 4.1 数论函数pot称自变量取正整数的函数为数论函数，不过我们关心的是有数论背景的函数。我们将会看到 所有数论函数形成一个交换环。对任意正整数a，和素数p，若pr||a，称pr为a的p部分，记r
potpa，显然有以下性质： (1) potpab = potpa + potpb(2) potp(a + b) ≥ min(potpa, potpb)上式在potpa ?= potpb时一定取等号。 现在按如下方式将potp扩充定义域到非零有理数集Q*：potp(-a) = potpa，potp mpn - potpm，n或等价地定义为当a = pr · ，r, m, n ∈ Z, (p, m) = (p, n) = 1时， potpa = r显然，上述两条性质仍然成立，举例说明它的应用:1 例：说明a = 1 + · · · +
2 20 解：记m是a的分母，那么m的素因子只可能是20以内的素数。1 1取p = 11, 13, 17或19，则是, n = 1, 2, ..., 20中唯一的满足potpx ≥ 0的x，但pot1 -1，故反pn复用性质(2)可知 ppotpa = -1这不仅说明a非整数，进一步a的分母m满足 1potpm = 1;1
再取p = 2，pot2
= -4；对1, 2, ..., 20中任何n = 16，有pot≥ -3。因此反复用性质(2)知 2 n 16pot2a = -4 4748最后分别考察p = 3, 5, 7， CHAPTER 4.
数论函数i=1,3|i . 0 1 = 1 (1 + 1 + + 1 ) = 1 (2 + 9 )· · ·2于是pot3 .2i=1,3|i1 = -1，从而pot3a = -1，即 ipot3m = 1; i=1,5|i1 1 1 1
5 5 1 1 . 1 1= (1 + + + ) = + ) = + 2于是pot5 2 .i=1,5|i1≥ 0，从而pot5a ≥ 0，即pot3m = 0; i=1,7|i. 0 1 = 1 (1 + 1 ) = 1 3 )×2于是pot7 .2i=1,7|i1 = -1，从而pot7a = -1，即pot7m = 1; 综上a = 24 × 3 × 7 × 11 × 13 × 17 × 19 注：2部分的分析容易推广到任意1 +1 · · · 1 ，k不定的情形。2k定理4.1.1.
对任意素数p和正整数n，有 证明：设m ，则p 因n npotpn2 ] + · · ·p p n! = 1 · · · p · · · 2p · · · mp · (mp + 1) · · · n 可知potpn! = potp(pmm!) = m + potpm!归纳并注意到可得定理需要的公式。ij *定理4.1.2. 对任意素数p和正整数n，记A(n, p)为n的p进展开式的各位数字之和，则有下列公式potpn! =p - 14.1.
数论函数POT证明：还是利用*式进行归纳，因此只需检查m + = p - 1 ?p - 149对p做带余除法n = pm + a0，那么A(n, p) = a0 + A(m, p)，简单计算可知上式成立。现在利用potp在Q上定义一种绝对值| · |p-potap, pa = 0|a|p =0, a = 0 前面两条性质变成了 (1) |ab|p = |a|p|b|p(2) |a + b|p ≤ max(|a|p, |b|p)在增加一条(3) |a|p ≥ 0，等号仅在a = 0时取。一般地，域F 的一个范数是指到实数集的一个映射|| · ||，满足以下公理： (1)||xy|| = ||x||||y|| (2)三角不等式 ||x + y|| ≤ ||x|| + ||y||(3)对任意x ∈ F ，有||x|| ≥ 0，仅当x = 0时取等号。 带有范数的域称为赋范域，在赋范域中自动有了距离，极限，Kauchy序列这些概念。两个范
数|| · ||1和|| · ||2称为等价如果有常数a > 0，使得||x||1 = ||x a恒成立；换句话说，等价的范数决 定相同的收敛标准。||2赋范域F 有一个（在同构意义下）唯一的完备化，即一个完备的赋范扩域E，而且F 在E上 稠密。完备化的构造可通过取F 上的Kauchy序列的等价类来构造。在有理数域上记通常的绝对 值（即阿基米德绝对值）为| · |∞，我们有 定理4.1.3.
Q的任意一个范数必等价于某一| · |p，其中p为一个素数或∞ 定理4.1.4.
(乘积公式)对任意x ∈ Q*，有Y
|x|p = 1 p这里，p跑遍所有素数和∞.乘积公式的证明很容易，有一个有趣的推论：Q(1) 对a ∈ Q，p |a|p
a = 0(2) 对a ∈ Z和素数p，|x|p|x|∞
a = 0 Q关于p-adic绝对值的完备化Qp称为p-adic数域或称p-adic有理数域。Qp中的任意非零元x可唯一表为如下级数形式 ∞.x = aipi, ai = 0, 1, ..., p - 1i=m50 CHAPTER 4.
数论函数m为整数，am = 0. 也可记 |x|p
= p-m ordpx = m.. i和∞ bipi的加法和乘法运算按通常p进制的进位，退位运算进行。 两个元 ∞apii=m i=m也可以把Qp直接定义为上述形式作为元素的集合按上面定义的运算和范数形成的完备域， 简单验证可知Q的确是稠密的。1 = -1 - 3 2.i因|3|3
< 1。同理，若an为周期序列或（去掉有限项后是周期序列），级数i∞
aip也表有理数， =m这与通常的循环小数化分数是一样的，那些非周期序列就给出了新的数。.∞定义Zp = {x ∈ Qp||x|p ≤ 1} = { i=1 aipi, ai = 0, 1, ..., p - 1}。称Zp的元为p-adic整数。对 两个a, b ∈ Zp，a与b充分接近是指a ≡ b (mod p的充分高次幂)。利用Qp的分析工具可以解决某 些数论问题。1 + 3 + 32 + · · · =例 在3 - adic拓扑下1 4.2 麦比乌斯函数和Euler函数记u(n)为麦比乌斯函数，定义为1, n = 1u(n) = 0, n有平方因子 (-1)r, n是r个不同素数之积 定理4.2.1..u(d) =d|n1, n = 1 0, n > 1证明：对n > 1，设n = pl1
· · · plr ，则1r.. r .. .i p= 0 u(d) =
-1) id|nd|p1···pri=0我们已经学过了Euler函数φ(n)，这里只简单重复一下基本性质:(1) 乘性：对(m, n) = 1，有 .(2) φ(d) = nd|nφ(mn) = φ(m)φ(n)上式可简单解释为对n阶循环群中的元按（元素的）阶分类计数。 (3) 用u(n)的语言重新表述. nφ(n) = u(dd|n4.3.
DIRICHLET乘积 514.3 Dirichlet乘积对数论函数f (n)和g(n)，定义函数. f (n) * g(n) = f (d)gd d|n为f
(n)和g(n)的Dirichlet乘积。显然乘积是交换的，事实上也有结合律，即 (f (n) * g(n)) * h(n) = f (n) * (g(n) * h(n)) 证明是简单计算，两端都等于 . f (a)g(b)h(c)abc=n 大家可对比数列（即数论函数）的卷积运算及相关规则。记 I(n) =1, n = 1 0, n > 1 容易验证f (n) * I(n) = f (n)，即I(n)是乘法*的单位元。定理4.3.1.
设有数论函数f (n)，则f (n)有乘法逆的充分必要条件是f (1) = 0证明：必要性。设g(n)是f (n)的乘法逆，即f (n) * g(n) = I(n)。于是f (1)g(1) = I(1) = 1，故f (1) ?= 0。再证充分性。归纳地定义g(n)时之满足f (n) * g(n)
I(n)。首先定义g(1)
1/f (1)可 使f (1)g(1) = 1 = I(1)，假设对k < n已有g(k)。按0 = I(n) = f (0)g(n) +f (d)gn )可唯一 .d|n,d>1地定义出g(n)。 综上，所有数论函数按普通加法和Dirichlet乘积形成一个交换环，以I(n)为乘法单位元，其 单位群由所有在1处取非零值的函数组成。 第十三讲 分析方法初步 4.4 麦比乌斯反演公式将麦比乌斯函数的基本公式用Dirichlet乘积的语言重写为 u(n) * e(n) = I(n), e(n)定义为e(n) = 1。对任意数论函数f (n)，定义它的麦比乌斯变换为.g(n) = f (n) * e(n) = f (d)d|n52 CHAPTER 4.
数论函数. f (n) = g(n) * u(n) = g(d)u)dd|n此时有上述公式成为麦比乌斯反演公式，而.g(d)u)称为g(n)的麦比乌斯逆变换。例如d|n .φ(d) = nd|n 可导出. nφ(n) = u(dd|n当然麦比乌斯反演公式也可直接算出。另外麦比乌斯反演公式还有如下乘积形式: Y Y ng(n) = f (d) ==> f (n) = g(d)u)d|nd|n 例如：记ζn为n次本原单位根，即复数乘法群中的一个n阶元。那么全体n次单位根为ζj , nj =1, 2, ...,全体n次本原单位根为n) = 1。记 n ζ，(j, j φn(x) = Ynj(x - ζn)j=1,(j,n)=1那么 Yx- 1 = φd(x)nd|n 由乘法形式的麦比乌