浙江大学：《离散数学》课程教学资源（PPT课件讲稿）第二章 算法（2.2）数论

数论 22数论 Number Theory 、算术基本定理 2、同余关系 3、密码学基础 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 1 2.2 数论 Number Theory 1、算术基本定理 2、同余关系 3、密码学基础

算术基本定理 数论 以整数集为典型代数系统的数论知识一直被认为是 既神秘又古老。虽然绝大多数人自小学生起就开始认识它, 而一些数学家却一辈子踏着它往皇冠上攀。现在,计算机 终于给数论这门再纯洁不过的数学分支扬起了应用的帆。 我们这里介绍的虽然只是初等数论的基础知识,但它们在 计算机的数据表示、数据传输以及电子商务应用中的数据 保密等方面起着非常重要的作用。 2/24/202111:15PM Deren Chen Zhejiang univ 2

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 2 以整数集为典型代数系统的数论知识一直被认为是 既神秘又古老。虽然绝大多数人自小学生起就开始认识它， 而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机 终于给数论这门再纯洁不过的数学分支扬起了应用的帆。 我们这里介绍的虽然只是初等数论的基础知识，但它们在 计算机的数据表示、数据传输以及电子商务应用中的数据 保密等方面起着非常重要的作用。 1、算术基本定理

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的直因子。 2/24/202111:15PM Deren Chen Zhejiang univ 3

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 3 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的直因子

Theorem 1 数论 定理1.设a、b、c是任意三个整数,则下列各式成立 (1)若b|a,则下列各式成立(b≠0 (-b)|a,b|(-a),(-b)|(-a),|b (2)若c|b且bla(c≠0,b≠0),则ela (3)若b|a(b≠0),则b|ac (4)若b|a且b|c(b≠0),则b|(a±c) (5)若a|b且b|a(a≠0,b0),则a=±b 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 4 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

Theorem 2 数论 定理2设ab是两个整数,b≠0,则恰存在两个 整数q、r使满足 a=batr 其中0≤r<b 定理2中的等式a=bq+r也可以用地板(下整)函数表示为 a=ba/b+(abLa/b」 由此可知,定理2对于实数集R也是成立的 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 5 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也是成立的

EXAMPLE2 数论 定义2设d,a1,a2…,n1(m>=2)是任意整数,若有 da1,da2,…,dlan 则称d是a1a2,…,1a公因子/ common divisor s 若 d是a1a2y…y an的一个公因子,对 a1,a) an的任 个公因子c,存在cd,则称d是a1,a2,21的最大公因子 greatest common divisor,记为(a;a2,,an)。或gcd (a1,a2x…,an)或GCD( 1942。an 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 6 EXAMPLE 2 定义2 设d,a1 ,a2 ,…,an (n>=2)是任意整数，若有 d|a1 , d| a2 , … , d| an 则称d是a1 ,a2 ,…,an的公因子/common divisor。 若d是a1 ,a2 ,…,an的一个公因子，对a1 ,a2 ,…,an的任一 个公因子c，存在cd，则称d是a1 ,a2 ,…,an的最大公因子 /greatest common divisor ，记为(a1 ,a2 ,…,an )。或 gcd （ a1 ,a2 ,…,an ）或GCD （ a1 ,a2 ,…,an ）

theorem 3 数论 定理3设a、b∈I且满足 a=b*g+r 这里a>b,0<r<b,则 gcd(a, b )=gcd(b, r) 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 7 theorem 3 定理3 设a、bI 且满足 a=b*q+r 这里 ab，0rb，则 gcd(a,b) = gcd(b,r)

Theore 4 数论 定理4任意两个整数都存在最大公因子。 求两个整数的最大公因子的欧几里德算法 ( Euclid,也称辗转相除法)。 设a、b是任意两个整数,a=q;b+r1 i=0、1、2、 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 8 Theorem 4 定理4 任意两个整数都存在最大公因子。 求两个整数的最大公因子的欧几里德算法 （Euclid，也称辗转相除法）。 设a、b是任意两个整数， a=qi b+ ri i=0、1、2、…

Example 1 数论 例1:求133和301的最大公因子 k 2 3 3 35 28 7 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 9 Example 1 例1：求133 和301 的最大公因子 k 0 1 2 3 4 qk 2 3 1 4 rk 35 28 7 0

Theorem 5 数论 定理5设a、b是正整数,则存在整数s、t,满足 s*a+t*b=ged (a, b) s*t+tb:gcd(a,b的线性组合表达/ linear combination 例2、求gcd(252,198)的线性组合表达。 2/24/202111:15PM Deren Chen Zhejiang univ

数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 10 Theorem 5 定理5 设a、b是正整数，则存在整数s、t，满足 s*a + t*b = gcd（a，b） s*t+t*b：gcd(a,b)的线性组合表达/ linear combination 例2、 求gcd(252,198)的线性组合表达