2.2 数论.ppt

文档介绍：数论
Number Theory
1、算术基本定理
2、同余关系
3、密码学基础
11/22/2018
1
Deren Chen, Zhejiang Univ.
以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它,而一些数学家却一辈子踏着它往皇冠上攀。现在,计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。我们这里介绍的虽然只是初等数论的基础知识,但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。
1、算术基本定理
11/22/2018
2
Deren Chen, Zhejiang Univ.
Definition 1
定义1 设a,b,c是任意的三个整数,若满足a=bc则称b(或c)是a的因子/factor,a是b(或c)的倍数/multiple,b(或c)能整除(也称除尽/divides)a。记为 b∣a 和 c∣a。
特别地,若b≠a且b≠1,则称b是a的直因子。
11/22/2018
3
Deren Chen, Zhejiang Univ.
Theorem 1
定理1 . 设a、b、c 是任意三个整数,则下列各式成立
(1)       若b∣a, 则下列各式成立(b≠0)
(―b)∣a, b∣(―a), (―b)∣(―a), ∣b∣┃∣a∣
(2)       若c∣b且b∣a (c≠0,b≠0), 则c∣a
(3)       若b∣a (b≠0), 则b∣ac
(4)       若b∣a且b∣c (b≠0), 则b∣(a±c)
(5)       若a∣b且b∣a (a≠0,b≠0), 则a=±b
11/22/2018
4
Deren Chen, Zhejiang Univ.
Theorem 2.
定理2 设a,b是两个整数,b≠0,则恰存在两个
整数q、r使满足
a=bq+r 其中0≤r<∣b∣
定理2中的等式 a=bq+r也可以用地板(下整)函数表示为

a=ba/b+(a-ba/b)
由此可知,定理2对于实数集R也是成立的。
11/22/2018
5
Deren Chen, Zhejiang Univ.
EXAMPLE 2
定义2 设d,a1,a2,…,an (n>=2)是任意整数,若有
d|a1, d| a2, …, d| an
则称d是a1,a2,…,mon divisor。
若d是a1,a2,…,an的一个公因子,对a1,a2,…,an的任一个公因子c,存在cd,则称d是a1,a2,…,an的最大公因子/mon divisor ,记为(a1,a2,…,an )。或 gcd ( a1,a2,…,an )或GCD ( a1,a2,…,an )
11/22/2018
6
Deren Chen, Zhejiang Univ.
theorem 3
定理3 设a、bI 且满足
a=b*q+r
这里 ab,0rb,则
gcd(a,b) = gcd(b,r)
11/22/2018
7
Deren Chen, Zhejiang Univ.
Theorem 4
定理4 任意两个整数都存在最大公因子。
求两个整数的最大公因子的欧几里德算法(Euclid,也称辗转相除法)。
设a、b是任意两个整数, a=qi b+ ri
i=0、1、2、…
11/22/2018
8
Deren Chen, Zhejiang Univ.
Example 1
例1:求133 和301 的最大公因子
k
0
1
2
3
4
qk
2
3
1
4
rk
35
28
7
0
11/22/2018
9
Deren Chen, Zhejiang Univ.
Theorem 5
定理5 设a、b是正整数,则存在整数s、t,满足
s*a + t*b = gcd(a,b)
s*t+t*b:gcd(a,b)的线性组合表达/
bination
例2、求gcd(252,198)的线性组合表达。
11/22/2018
10
Deren Chen, Zhejiang Univ.