初等数论讲义修改版

初等数论讲义
张起帆 April, 2010
Fra Baidu bibliotek 2
Contents
1 唯一分解定理 第一讲 唯一分解定理的证明及简单应用 . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 带余除法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 同余语言的引进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 唯一分解定理及证明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 进一步的思考 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eratosthenes筛法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 一次不定方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fermat数与Mersenne数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 7 8 8 9 10 10 10 11 12 13 13 13 14 15 15 15 17 18 18 19 20 23 23 23 24 25
3.10 Gauss整数的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第九讲 模m的原根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 模m的原根存在的条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 指数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 公钥密码应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第十讲 群， 环， 域理论简介（上） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 群的概念及例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.16 似曾相识的群理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.17 基本的群论定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第十一讲 必备的抽象代数（下） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.18 环和域的概念及例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.19 环的算术性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.20 理想的运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.21 域的“熟知”定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 数论函数 第十二讲 基本的数论函数及运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 数论函数pot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 麦比乌斯函数和Euler函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dirichlet乘积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 麦比乌斯反演公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 积性函数和完全积性函数 素数分布 同余方法 柯召方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第四讲 孙子定理及应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第五讲 高次同余方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第八讲 素数表平方和问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 素数表平方和主要定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gauss整数的算术 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 原根与二次剩余 第六讲 模p的原根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 3.2 3.3 原根的存在性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 原根的判别准则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 二次剩余和勒让德符号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4
CONTENTS 第七讲 二次互反律 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 3.5 3.6 3.7 3.8 3.9 Gauss引理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 二次互反律的证明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 推广的二次互反律 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 特殊的二次同余方程的解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 26 27 28 29 30 31 32 33 34 34 35 37 38 38 38 40 41 42 42 44 45 46 47 47 47 50 51 51 51 52 53 56 56 57 58 61
第二讲 一些数论问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 同余式 第三讲 周期问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 同余的概念及基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 周期 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wilson定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 孙子定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Euler函数的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 解同余方程的一般原则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 模素数幂的同余方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 模素数的同余方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .