1-数论基础知识.pptVIP

数论基础知识 刘汝佳 基本概念 整除与约数、倍数. 注意负数 可整除性的基本性质 若a|b, a|c, 则a|(b+c) 若a|b, 那么对所有整数c, a|bc 若a|b, b|c, 则a|c 整除关系具有传递性. 它是偏序关系(partial order), |,Z是一个格 素数和合数 如果大于1的正整数p仅有的正因子是1和p, 则称p为素数(prime) 大于1又不是素数的正整数称为合数(compound) 如果n是合数, 则n必有一个小于或等于n1/2的素因子 算术基本定理 每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。 换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数 这个定理也叫做惟一分解定理。它是一个定理而不是公理！虽然在大多人看来，它是“显然成立”的，但它的确是需要证明的定理 除法和同余 令a为整数，d为正整数，那么有惟一的整数q和r，其中0≤rd，使得a=dq+r 可以用这个定理来定义除法：d叫除数，a叫被除数，q叫商，r叫余数。如果两个数a,b除以一个数c的余数相等，说a和b关于模c同余，记作a≡b(mod c) 同余 为什么有同余?1+432435..2=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) 定理的证明 使用惟一分解定理. 设 则有: 容易验证定理成立 基本问题 如何求1~n的所有素数? 如何判断一个数n是否为素数? 如何求两个数的最大公约数? 如何给一个数n分解素因数? 问题1: 1~n的素数 假设要求1~100的素数 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(想一想, 为什么) Eratosthenes的筛子 小知识 () 近似公式(Legendre常数B=-1.08366) 问题2: 素数判定 枚举法: O(n1/2), 指数级别 改进的枚举法: O(phi(n1/2))=O(n1/2/logn), 仍然是指数级别 概率算法: Miller-Rabin测试 + Lucas-Lehmer测试 Miller-Rabin测试 对于奇数n, 记n=2r*s+1, 其中s为奇数 随机选a(1=a=n-1), n通过测试的条件是 as≡1(mod n), 或者 存在0=j=r-1使得a2^j*s≡-1(mod n) 素数对于所有a通过测试, 合数通过测试的概率不超过1/4 只测试a=2, 3, 5, 7, 则2.5*1013以内唯一一个可以通过所有测试的数为3215031751 注意: 先要判断此数本身是否为2, 3, 5, 7的约数 思考：区间内的素数 给出n, m(n=106, m=105), 求n~n+m之间的素数有多少个 哪种方法快? 筛还是依次素数判定? 问题3: 最大公约数 方法一: 使用惟一分解定理, 先分解素因数, 然后求最大公约数 方法二: (Euclid算法)利用公式gcd(a, b)=gcd(b, a mod b), 时间复杂度为O(logb) 方法三: (二进制算法) 若a=b, gcd(a,b)=a, 否则 A和b均为偶数, gcd(a,b)=2*gcd(a/2,b/2) A为偶数, b为奇数, gcd(a,b)=gcd(a/2,b) 如果a和b均为奇数, gcd(a,b)=gcd(a-b,b) 不需要除法, 适合大整数 扩展问题 一定存在整数x,y，使得ax+by=gcd(a,b) int gcd(int a, int b, intx, int y){ if(!b){ x = 1; y = 0; return a; } else{ int r = gcd(b, a%b, x, y); t = x; x = y; y = t – a/b*y; return r; } } 由数学归纳法可证明ax+by=gcd(a,b) 满