1、第 31章 数论算法预备 知识1数论基础数论是一门古老的数学分支。以前人们都认为它是完全纯粹数学，在现实生活中很难找到它的实际应用。自从 1976年公开密钥密码体制诞生以来，现代密码学就和数论有着千丝万缕的联系。一、引言约定：字母 N表示全体自然数集合， Z表示整数集合，即N=0， 1， 2， Z=， -2， -1， 0， 1， 2， 自然数与整数定义 1：如果存在一个整数 k使得 n=kd，则称 d整除 n,记作 d|n，其中 d称作 n的因子，n称作 d的倍数。如果不存在这样一个整数使得 n=kd，则称 d不整除 n，记为 dn。整除定义 2：整数 p1称为素数，如果除了 1和其本身外，
2、p没有任何其它因数。不是素数的整数称为合数。 素数与合数带余除法 ：设 a,b是两个整数，其中 b0。则存在两个整数 q,r使得 a=qb+r。其中 q和 r是唯一确定的。 带余除法公因数 ：设 a,b是两个整数，既是 a的因数又是 b的因数的数称为 a,b的公因数。 公因数最大公因数 ： a和 b的所有公因数中最大者，称为 a和 b的最大公因数，记作gcd(a,b)。 最大公因数公倍数 ：设 a,b是两个整数，既是 a的倍数又是 b的倍数的数称为 a,b的公倍数。最小公倍数 ： a和 b的所有公倍数中最小者，称为 a和 b的最小公倍数，记作lcm(a,b)。 公倍数与最小公倍数lcm(a,b) gcd(a,b)=ab. 最小公倍数与最大公因数
