数论 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=ba/b+(a-ba/b ) 由此可知，定理2对于实数集R也是成立的