数论基础与集合的基数问题.pdfVIP

1

数论基础

回顾

2

问题1：什么是集合的基数？

-有限集合的基数就是一个自然数，表示集合的元素个数

-无限集合中最小的那一个就是自然数集合，它的基数是ℵ0

-我们也可以判断一个集合是有限还是无限

问题2：(基数)最大的集合有多大？

-实数集比自然数集大

-任意集合的幂集比自身大

问题3：如何比较两个(无限)集合的基数？

-利用双射函数证明等势

-利用Bernstein定理证明等势

本节提要

3

问题1：什么是(初等)数论？

问题2：素数有哪些性质？

现代数论的早期铺垫

4

什么是数论

5

整数集

6

整数的代数性质

整除

对任意整数a和b,a0,我们说a整除b(记作a|b),

如果存在整数c使得b=ac.

设a,b和c是整数，a0,

若a|b，且a|c，则a|(b+c)

若a|b，则a|(bc)

若a|b，且b|c，则a|c

余数

同余算术(高斯,Gauss)



同余算术

令a和b为整数，d为正整数，则

(a+b)modd=(amodd+bmodd)modd.

(ab)modd=((amodd)(bmodd))modd.

模m算术：令Zm表示小于m的非负整数集合，定义

+/·为模m加法/乘法

mm

a+mb=(a+b)modm

a·b=(a·b)modm

m

本节提要

12

问题1：什么是(初等)数论？

-研究整数的性质：整除、余数、同余算术

问题2：素数有哪些性质？

素数（Prime）

大于1的正整数p称为素数，如果p仅有的正因子是1

和p。大于1又不是素数的正整数称为合数。

正整数n是合数iffaN.1an,且a|n.

算术基本定理：每个大于1的正整数都可以唯一地

写为一个素数或者若干个素数的乘积，其中素数因

子以非递减序出现。

12k

n=p1p2…pk

素数举例：2,3,5,7,11,13,17,19,…

22310

合数举例：100=25.999=337,1024=2.

算术基本定理的证明(存在性)

14

大于1的自然数必可写成素数之积

用反证法：

假设存在大于1的自然数不能写成质数的乘积，把最小

的那个称为n。

大于1的自然数可以根据其可除性（是否能表示成两个

不是自身的自然数的乘积）分成2类：质数、合数。

首先，按照定义，n不是质数，因为质数p可以写成质

数乘积：p=p，这与假设不相符合。

因此n只能是合数，但每个合数都可以分解成两个严格

小于自身而大于1的自然数的积。设n=a*b，其中a

和b都是介于1和n之间的自然数，因此，按照n的定义，

a和b都可以写成质数的乘积。从而n=a*b也可以写成

质数的乘积。由此产生矛盾。

算术基本定理的证明(唯一性)

15

引理：若质数p|ab，则不是p|a，就是p|b。

证明：

(1)若