数论-lsx.pptVIP

整除是数论中所有其他内容的基础。 * |（竖线）表示整除，a|b念做 a整除b 若a整除b,那么a是b的约数（因子），b是a的倍数。这个在我们中学的时候就学过。 比如说3|6，我们能不能说3|2 ？ 一般地，a整除b意味着b大，a小 * 性质1，整除具有传递性。 性质2，a整除b的倍数 性质3，a整除b与c的线性组合 性质4，若两个整数互相整除，那么这两个数要么相等，要么互为相反数。 * 那么怎样求两个整数的最大公约数，我们后面会讲。 最小公倍数可以通过最大公约数求出。 欧几里德算法是用来求两个整数的最大公约数。 它具体的求解过程非常简单，运用到的原理就是这个等式：gcd(a,b) = gcd(b,a mod b) ，a是大数，b是小数。a mod b 表示a除以b的余数， 也就是说，辗转相除法的本质是：把求两个非负整数的最大公约数转化为求两个较小数的最大公约数。 我们来简要证明一下，对于大数a, 我们可以把它写成 a=kb + c，。。。 利用这个原理，两数一直辗转相除下去直到两数整除，其中的除数就是要求的最大公约数。 * 辗转相除法： **定理：gcd(a,b) = gcd(b,a mod b) 用程序语言描述就是这样： 它是一重循环，当余数为0时循环结束。也就是说辗转相除法直到整除为止，此时小的那个数就是最大公约数 * 我们理解下欧几里德算法最坏情况为什么是斐波那契数列相邻的两项。 首先我们口述一下利用欧几里德算法求解(13, 8)，(12, 8)的过程。 （13,8）（8，5）（5,3）（3,2）（2,1） （12,8）（8,4） 所以我们看出，当两数互素的时候，辗转相除的次数比较多。 我们再看，a = k*b + c, 得出c = a - k*b，当k=1时，c减少得最少，相应地，辗转相除的次数比较多。 所以从上述两点可以看出，同时满足k = 1，两数最大公约数为1时，序列递减得最慢，即辗转相除法的次数最多。 而这种情况展开来正好是斐波那契数列。 * 下面我们讲求最大公约数的另一算法stein算法。 gcd(ka,kb)=k*gcd(a,b) 2.当k与b互素时，gcd(ka,b)=gcd(a,b) k与b互素说明 k与b没有公约数，很显然，ka与b的公约数即为a 与 b的公约数 3. (a, b) = (b, a-b) a = b + (a - b)，利用整除基本性质5 * * 用逻辑语言描述就是这样， 算法终止的具体情况：两个都为奇数而且相等的时候 r 记录了出现两个都是偶数的次数，也就是记录了2的个数 ar ， a = a * 2^r 移位运算：左移1位，即该数乘以2；右移一位，即该数除以2. * 算法评价： 它的核心精髓跟欧几里德算法一样，将两个大数的最大公约数转化为两个较小数的最大公约数 优点：加法，减法和移位运算，是最基本的运算，时间消耗最小 乘法，除法，取余运算较慢 * * 即它能用来解二元模线性方程。 * * * 同模情况下，有这样的性质 观察：乘法原则 8 mod 7 = 1 7 mod 7 = 0 16 mod 7 = 2 64 mod 7 = 8 N = a * k + 1 N mod a = 1 10*N = a *10 * k + 10 所以10N mod a = 10 加法原则: 8 mod 7 = 1 10 mod 7 = 3 18 mod 7 = 4 中国剩余定理： 基底 讨论两个互素的数 3， 5 在0 – 14之间找到一个数，使得这个数除以3余1， 除以5余2， 经求解该数为7，而且该数唯一。 不限定数：7， 22， 37 中间相差一个[3, 5] = 15， 余数不变 3k1 + 1 5k2+ 2 7 + 15k, k是整数 1） 3k1 + 1， 5k2 （10） 2） 3k1， 5k2+2 （12） 3） 3k1 + 1， 5k2 + 2 （22） 如何理解： 取余的加法原则 10 mod 3 = 1 12 mod 3 = 0 10 mod 5 = 0 12 mod 5 = 2 3k1 + 2, 5k2 + 3 标准解法： 1） 3k1 + 1， 5k2 (10) 2) 3k1, 5k2 + 1 (6) 2 * 10 + 3*6 = 38 38-[3, 5]*2 = 8 利用了加法原理与乘法原理 2k1 + 1, 3k2 + 2, 5k3 + 3 2k1 + 1, 3k2, 5k3 2k1, 3k2+1, 5k3 2k1, 3k2, 5k3+1 为什么重视中国剩余定理： 2， 3， 5， 7（相互互素） 乘积 为210 结论： 1）0-210之间的任何数都可以用2， 3， 5， 7的余数表示，而且表法唯一； 2）