1、数论基础知识刘汝佳基本概念 整除与约数、倍数 . 注意负数 可整除性的基本性质 若 a|b, a|c, 则 a|(b+c) 若 a|b, 那么对所有整数 c, a|bc 若 a|b, b|c, 则 a|c 整除关系具有传递性 . 它是偏序关系 (partial order), 是一个格素数和合数 如果大于 1的正整数 p仅有的正因子是 1和 p, 则称 p为素数 (prime) 大于 1又不是素数的正整数称为合数(compound) 如果 n是合数 , 则 n必有一个小于或等于 n1/2的素因子算术基本定理 每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的 “乘积
2、”可以有 0个、 1个或多个素因子）。 换句话说 , 任意正整数 n可以写成 n=2a1*3a2*5a3*,其中 a1,a2,a3等为非负整数 这个定理也叫做 惟一分解定理 。它是一个定理而不是公理！虽然在大多人看来，它是 “显然成立 ”的，但它的确是需要证明的定理除法和同余 令 a为整数， d为正整数，那么有惟一的整数 q和 r，其中 0rd，使得 a=dq+r 可以用这个定理来定义除法： d叫除数， a叫被除数， q叫商， r叫余数。如果两个数 a,b除以一个数 c的余数相等，说 a和 b关于模 c同余，记作 ab(mod c) 同余 为什么有同余 ? 132412341+432435.2
3、=24.7 余数可以作为原数的一个 signature(标记 ). 如果标记下的运算错误 , 一定错误 如果标记下的运算正确 ?最大公约数和最小公倍数 令 a和 b是不全为 0的两个整数，能使 d|a和d|b的最大整数称为 a和 b的最大公约数，用gcd(a,b)表示，或者记为 (a,b)。 令 a和 b是不全为 0的两个整数，能使 a|d和b|d的最小整数称为 a和 b的最小公倍数，用lcm(a,b)表示，或者记为 a,b 定理 : ab = gcd(a,b) * lcm(a,b)定理的证明 使用惟一分解定理 . 设 则有 : 容易验证定理成立基本问题 如何求 1n的所有素数 ? 如何判断一个数 n是否为素数 ? 如何求两个数的最大公约数 ? 如何给一个数 n分解素因数 ?问题 1: 1n的素数 假设要求 1100的素数 2是素数 , 删除 2*2, 2*3, 2*4, , 2*50 第一个没被删除的是 3, 删除 3*3, 3*4, 3*5,3*33 第一个没被删除的是 5, 删除 5*5, 5*6, 5*20 得到素数 p时 , 需要删除 p*p, p*(p+1), p*n/p, 运算量为 n/p-p, 其中 p不超过 n1/2(想一想 , 为什么 )
