《欧几里德(Euclid)算法》由会员分享，可在线阅读，更多相关《欧几里德(Euclid)算法（3页珍藏版）》请在金锄头文库上搜索。
1、欧几里德（欧几里德（Euclid）算法）算法首先我们介绍整数的带余除法，它是整个数论的基础性定理之一。定理定理 1 （带余除法）（带余除法）设且，那么存在一对整数 q 和 r，使得Zba,0b且 (1)rbqa|0br 满足以上条件的整数 q 和 r 是唯一确定的。由(1)式显然有(a,b)=(b,r)我们知道，对于两个整数 a 和 b，可以对其进行分解来计算它们的最大公因数，但对于大整数而言，目前还没有足够有效的办法进行。实际中常用的用来计算两个数的最大公因数的算法称为欧几里德算法。它的理论依据正是前面所述的带余除法。欧几里德算法的数学表述如下：且，重复应用带余除法，我们有：Zba,0bnn
2、nnnnnnnnnn rrrrqrrrrrqrrrrrqrrrrrqbbrrbqa1111112233231122121110,0,0,0,|0,L这时，由于小于|b|的正整数只有有限个以及 1 整除任0|21Lrrb一整数，所以这过程不能无限制地做下去，必定会出现某个 n，要么，要么，此时余数。1,|1nnnrrr1nr01nr我们容易得到定理定理 2 ),(barn这是因为nnnnnrrrrrrrrbba),(),(),(),(),(112211L另外，由(1)式我们可得：112232313121221110,0,0,|0,nnnnnnrrrqrrrrrqrrrrrqbrbrbqarLL把
3、前面的式子依次代入到后面的除式中，相应地消去，最后，1321,nrrrrL可以表示为 a 和 b 的整系数线性组合，这时的系数即为使 ax+by=(a,b)的系数。nr习题习题、什么是计算复杂性、空间复杂性？简述 P 问题、NP 问题和 NP完全问题之间的关系。2、1. O(ax7+3x3+sin(x)=2. O(en+an10)=3. O(n!+n50)= 、对于整数 15 和 18，问：(1) 它们是否互素？(2) 试用欧几里德算法求它们的最大公因子。4、是否有解，为什么？如果有解，请给出两种计算方法。15mod281x5、求下列各数的最大公因数：(45,75), (102,222), (
4、666,1414), (3961,952), (147,64)并用它们的线性组合表示。6、试证若 a=bq+r, 则gcd(a, b)=gcd(b, r)7、试证若(a,b)=1,a|(bc), 那么 a|c。8、若 d=gcd(a, b), 则存在整数 p 和 q，使得 d=pa+qb9、求下列问题的解(1) 7mod53 x(2) 7mod54 x(3) 35mod1510 x(4) 16mod157 x10、证明nnmod0) 1(21Lnnmod0) 1(21333L其中 n 是正整数。11、求下列方程组的解：2mod0x3mod0x5mod1x7mod6x12、求下列方程组的解：11mod4x17mod3x2mod1x3mod2x5mod3x
