欧几里德(Euclid)算法

欧几里德（Euclid）算法

首先我们介绍整数的带余除法，它是整个数论的基础性定理之一。

定理1 （带余除法）设a,bZ且b0，那么存在一对整数q和r，使得

abqr且0r|b| (1)

满足以上条件的整数q和r是唯一确定的。

由(1)式显然有(a,b)=(b,r)

我们知道，对于两个整数a和b，可以对其进行分解来计算它们的最大公因数，但对于大整数而言，目前还没有足够有效的办法进行。实际中常用的用来计算两个数的最大公因数的算法称为欧几里德算法。它的理论依据正是前面所述的带余除法。

欧几里德算法的数学表述如下：

a,bZ且b0，重复应用带余除法，我们有：

aq1br1,bqrr,212r1q3r2r3,rn2qnrn1rn,rn1qn1rnrn1,0r1|b|0r2r10r3r20rnrn10rn1rn

这时，|b|r1r20，由于小于|b|的正整数只有有限个以及1整除任一整数，所

以这过程不能无限制地做下去，必定会出现某个n，要么rn|rn1,rn1，要么rn1，此时余数rn10。

我们容易得到

定理2 rn(a,b)

这是因为(a,b)(b,r1)(r1,r2)(rn2,rn1)(rn1,rn)rn

另外，由(1)式我们可得：

r1aq1b,rbqr,221r3r1q3r2,rnrn2qnrn1,0r1|b|0r2r10r3r20rnrn1

把前面的式子依次代入到后面的除式中，相应地消去r1,r2,r3,,rn1，最后，rn可以表示为a和b的整系数线性组合，这时的系数即为使ax+by=(a,b)的系数。

习题

１、 什么是计算复杂性、空间复杂性？简述P问题、NP问题和NP－完全问题之间的关系。

2、1. O(ax7+3x3+sin(x))=

2. O(en+an10)=

3. O(n!+n50)=

３、 对于整数15和18，问：

(1) 它们是否互素？

(2) 试用欧几里德算法求它们的最大公因子。

14、28xmod15是否有解，为什么？如果有解，请给出两种计算方法。

5、求下列各数的最大公因数：

(45,75), (102,222), (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+qb

9、求下列问题的解

(1) 3x5mod7

(2) 4x5mod7

(3) 10x15mod35

(4) 7x15mod16

10、证明

12(n1)0modn

1323(n1)30modn

其中n是正整数。

11、求下列方程组的解：

x0mod2

x0mod3

x1mod5

x6mod7

12、求下列方程组的解：

x4mod11

x3mod17

x1mod2

x2mod3

x3mod5