引子 素数奇趣与猜想 1
0.1 哥德巴赫猜想 2
0.2 孪生素数猜想 2
0.3 回文素数猜想 4
0.4 梅森素数的故事 5
第1章 整除理论 9
1.1 整除概念与判定 9
1.1.1 整除与带余除法 9
1.1.2 奇数与偶数 11
1.1.3 整除判定 12
1.1.4 整除概念基础训练与拓展 14
1.2 最大公因数与最小公倍数 15
1.2.1 最大公因数 15
1.2.2 最小公倍数 23
1.2.3 最大公因数基础训练与拓展 25
1.3 整数分解与素数分布 27
1.3.1 素数与合数概念及特征 27
1.3.2 算术基本定理 30
1.3.3 两种初等整数分解方法 33
1.3.4 n！素因数分解 35
1.3.5 整数分解正因数定理与完全数 39
1.3.6 素数分布及素数定理 41
1.3.7 整数分解基础训练与拓展 47
第2章 同余理论 49
2.1 同余概念及应用 49
2.1.1 同余概念 49
2.1.2 同余四则运算 51
2.1.3 同余在整除判别中的应用 53
2.1.4 同余在末位数判别中的应用 54
2.1.5 例说同余实际应用 56
2.1.6 同余概念基础训练与拓展 61
2.2 剩余类与剩余系 61
2.2.1 概念及其判别 62
2.2.2 剩余系构造 64
2.2.3 威尔逊定理与素数判别 68
2.2.4 例说完全系实际应用 69
2.2.5 剩余类基础训练与拓展 72
2.3 欧拉函数的计算与经典同余定理 72
2.3.1 欧拉函数的计算公式 73
2.3.2 欧拉定理与费马小定理 76
2.3.3 费马小定理之逆与伪素数 79
2.3.4 欧拉定理对循环小数的应用 83
2.3.5 欧拉定理对RSA体制的应用 85
2.3.6 欧拉函数基础训练与拓展 89
第3章 同余方程 91
3.1 一次同余方程 91
3.1.1 方程系数与模互素的一次同余方程 92
3.1.2 方程系数与模不互素的一次同余方程 94
3.1.3 一次同余方程对RSA体制的应用 96
3.1.4 一次同余方程基础训练与拓展 97
3.2 一次同余方程组与中国剩余定理 98
3.2.1 中国剩余定理 98
3.2.2 中国剩余定理的思想原则应用 102
3.2.3 模不互素的一次同余方程组 103
3.2.4 一次同余方程组基础训练与拓展 106
3.3 高次同余方程 107
3.3.1 高次同余方程的解与解数 107
3.3.2 模为素数的高次同余方程 110
3.3.3 模为素数幂的高次同余方程 113
3.3.4 高次同余方程基础训练与拓展 117
3.4 二次剩余与二次同余方程 117
3.4.1 二次剩余 118
3.4.2 勒让德符号 121
3.4.3 高斯二次互反律 128
3.4.4 雅可比符号 132
3.4.5 二次同余方程解的模式 135
3.4.6 二次剩余在零知识证明中的应用 139
3.4.7 二次剩余基础训练与拓展 141
3.5 原根与离散对数 142
3.5.1 阶与原根 142
3.5.2 原根存在定理 145
3.5.3 原根的个数与求法 148
3.5.4 离散对数 151
3.5.5 离散对数在密码学中的应用 155
3.5.6 n次剩余 158
3.5.7 原根基础训练与拓展 161
第4章 不定方程 162
4.1 实用的一次不定方程 162
4.1.1 二元一次不定方程 163
4.1.2 二元一次不定方程实际应用 165
4.1.3 二元一次不定方程的非负解 167
4.1.4 多元一次不定方程 171
4.1.5 一次不定方程基础训练与拓展 174
4.2 诱惑人的费马方程 174
4.2.1 毕达哥拉斯方程 175
4.2.2 4次幂费马方程 178
4.2.3 费马方程基础训练与拓展 182
4.3 魅力无限的同余与不定方程联姻 183
4.3.1 奇素数平方和表示 183
4.3.2 拉格朗日平方和定理 187
4.3.3 奇异的佩尔方程 191
4.3.4 同余观下的不定方程 196
4.3.5 同余观下的不定方程基础训练与拓展 199
基础训练与拓展解答提示 201
参考文献 225