1、 NEC-DM离散数学第 5章 数 论 简 介NEC-DMv数论是数学里研究整数的一个分支。传统上,由于它的抽象本质大于它的应用,因此将数论看做是数学的一个纯粹的分支。v英国数学家 G. H. Hardy将数论看做是一个漂亮的、但不实用的数学分支。v然而,在 20 世纪后期,数论在密码系统(为了通信安全的系统)中得到了极大的应用。NEC-DM内容v基本的数论定义,如 “整除 ”和 “素数 ”。v因子分解、最大公因子和最小公倍数。v整数的表示和一些整数算术的算法。v用来计算最大公因子的欧几里得算法v用于安全通信的 RSA 系统。NEC-DM5.1 因子定义 5.1.1 令 n 和 d 是整数,
2、d 0。如果存在一个整数 q 满足 n = dq,称d 整除 n。称 q 是商, d是 n 的一个因子或者约数。如果 d 整除 n,记做 d | n。如果 d 不能整除 n,记做 d | n。NEC-DM例 5.1.2v由于 21 = 3*7, 3 整除 21,记做 3 | 21。商是 7,称 3 是 21 的一个因子或者约数。v注意到如果 n 和 d 是正整数,且 d | n,那么 d n。(如果 d | n ,那么存在一个整数 q 使得 n = dq。由于 n 和 d 是正整数, 1 q。因此, d dq = n。)v无论整数 d 0 是否整除整数 n,存在一个惟一的整数 q(商)和 r(
3、余数)满足 n = dq + r, 0 r 1是合数,那么它有一个正因子 d 既不是 1 也不是其自身。v由于 d 是正的且 d 1, d 1。因为 d 是 n 的一个因子, d n。由于 d n, d n。v因此,判断一个正整数 n 是否是合数,只需要试验一下整数 2, 3,., n - 1中的任何一个是否可以整除 n。v如果序列中存在某个整数能整除 n,那么 n 是合数。如果序列中没有整数可以整除 n,那么 n 是素数。NEC-DM例 5.1.6序列 2, 3, 4, 5,., 41, 42中没有数可以整除 43;因此, 43 是一个素数。检查序列 2, 3, 4, 5,., 449, 450中 451 的可能的因子。11 可以整除 451( 451 = 1141);因此, 451 是一个合数。NEC-DM定理 5.1.7v一个大于 1 的正整数 n 是合数当且仅当它有一个因子 d,满足 2 d 。v证明 必须证明如果 n 是合数,那么 n 有一个因子 d,满足 2 d ,而且如果 n 有一个因子 d,满足 2 d ,那么 n 是合数。