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 是合数。
