离散数学基础-课件 第4章 初等数论基础

初等数论04.初等数论基础Parttwo第二部分104整除性素数同余在信息科学中的应用

初等数论基础24.1整除性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈Rx2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

3定义4.1.1整除的基本性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理4.1.1（带余除法）4命题4.1.1整除的基本性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

5证明定理4.1.1证明整除的基本性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

6定义4.1.2定义4.1.3注4.1.1整除的基本性质例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

基于引理4.1.1，我们可得到下面的欧几里得算法.该算法也称作辗转相除法.

7证明引理4.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

8证明定理4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

9例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

10解例4.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

11证明定理4.1.3（贝祖等式）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

12推论4.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

13解例4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

14证明证明命题4.1.2推论4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

15证明命题4.1.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

16证明命题4.1.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

17证明命题4.1.5最小公倍数

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

18定义4.1.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最小公倍数

19证明证明命题4.1.6引理4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最小公倍数与最大公因数之间的关系

20证明命题4.1.7例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最小公倍数与最大公因数之间的关系

21证明命题4.1.8例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.4.2素数

22定义4.2.1证明命题4.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数

23命题4.2.1证明（续）定理4.2.1（算术基本定理）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.算术基本定理

24证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

算术基本定理

25注4.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.算术基本定理

进而，可将标准分解式用于刻画最大公因数和最小公倍数.下面的结论直接由定义即得.

26命题4.2.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素性测试

27证明引理4.2.1例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素性测试

28推论4.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.埃拉托色尼筛法

29例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.埃拉托色尼筛法

表4.2.1埃拉托色尼筛法30例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布存在无限多个素数.

31证明定理4.2.2定理4.2.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

下面结果告诉我们，两个相邻素数之间可能间隔任意多个合数，这表明素数的分布是极不规则的.

32证明命题4.2.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

33定理4.2.4(素数定理)例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

34例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

35例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.4.3同余

36定义4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

37命题4.3.1注4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

38命题4.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

39解例4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

表4.3.1

加法表表4.3.2

乘法表40解例4.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

41证明推论4.3.1例4.3.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

42命题4.3.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

43证明命题4.3.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

由命题4.3.3和命题4.3.4，下面的推论是显然的.

44推论4.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.剩余系

45定义4.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧拉函数

46引理4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧拉函数下面的引理表明，可以从一个给定的既约剩余系产生新的既约剩余系.

47引理4.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧拉函数

定理4.3.1（欧拉定理）48证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧拉函数

定理4.3.2（费马小定理）49证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧拉函数下面是费马小定理的一个简单应用.

50解例4.3.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.一元一次同余方程

51定理4.3.3证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.一元一次同余方程

52解例

4.3.5例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.一元一次同余方程

53定理4.3.4证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.一元一次同余方程

定理4.3.4证明（续）54例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.一元一次同余方程定理4.3.4的证明过程给出了一种求解一般一元一次同余方程的方法.

55解例4.3.6例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.一元一次同余方程

56定理4.3.5（中国剩余定理）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.中国剩余定理

57证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.中国剩余定理

58解例4.3.7例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何