辗转相除法

​来源

设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下:用a除以b，得a÷b=q......r1(0≤r1)。若r1=0，则(a，b)=b;若r1≠0，则再用b除以r1，得b÷r1=q......r2 (0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个非零除数即为(a，b)。

原理

设两数为a、b(b

第一步:令c=gcd(a,b)，则设a=mc，b=nc

第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c

第三步:根据第二步结果可知c也是r的因数

第四步:可以断定m-kn与n互质【否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。

证毕。

演算法

自然语言描述

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:

1. 若 r 是 a ÷ b 的余数，则

gcd(a,b) = gcd(b,r)

2. a 和其倍数之最大公因子为 b。

另一种写法是:

1. a ÷ b，令r为所得余数(0≤r

若 r = 0，演算法结束;b 即为答案。

2. 互换:置 a←b，b←r，并返回第一步

伪代码

这个演算法可以用递归写成如下:

function gcd(a,b) {

if b<>0

return gcd(b,a mod b);

else

return a;

}

gcd 简易函式

c语言辗转相除代码:

int GCD(int a,int b)

{returnb==0?a:GCD(b,a%b);}

C语言实现

/*题目:输入两个正整数，求其最大公约数。*/

#include

unsigned gcd ( unsigned,unsigned ) ;

int main( void )

{

unsigned m,n;

printf(请输入两个正整数:);

scanf(%u%u,&m,&n);

printf(%u与%u的最大公约数为:%u\n,m,n,gcd ( m,n ) );

return 0;

}

/* 功能:返回正整数m和n的最大公约数*/

unsigned gcd ( unsigned m,unsigned n )

{

unsigned temp;

if (m

{

temp=m;

m=n;

n=temp;

}

if ( m % n == 0)

{

return n;

}

else

{

return gcd ( n,m % n) ;

}

}

/*题目:输入两个非负整数u和v，求其最大公约数。*/

#include

main()

{

int u,v,r;

printf(please input u and v:);

scanf(%d,%d,&u,&v);

while(v!=0)

{

r=u%v;

u=v;

v=r;

}

printf(%d\n,u);

}

C#语言实现

static int sucDivison/*除法*/(int m, int n)

{

int remainder = 0;

if (m % n == 0)

{

return n;

}

else

{

do

{

remainder = m % n;

m = n;

n = remainder;

} while (remainder > 0);

}

if (n == 0)

{

return m;

}

return n;

}

Basic实现

INPUT m,n

DO

r=m MOD n

m=n

n=r

LOOP UNTIL r=0

PRINT m

END

Pascal实现

function gcd(a,b:integer):integer;

begin

if b=0 then gcd:=a

else gcd:=gcd (b,a mod b);

end ;

Common Lisp实现

(defun my-gcd (number-a number-b)

(do ((r (mod number-a number-b) (mod ea eb))(eb number-b r) (ea number-a eb))

((= 0 r) eb)))

Java 实现

/**

*

* @return int

* @tags @param m

* @tags @param n

* @tags @return

* @todo 【方法二】利用辗除法

*/

public static int gcd(int m, int n) {

while (true) {

if ((m = m % n) == 0)

return n;

if ((n = n % m) == 0)

return m;

}

}

资料举例

其中a mod b是指取 a ÷ b 的余数。

例如，123456 和 7890 的最大公因子是 6，这可由下列步骤看出:

时间复杂度

辗转相除法的运算速度为 O(n)，其中 n 为输入数值的位数。

辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数(十进位下)的五倍。加百利·拉梅(GabrielLamé)于1844年证明了这点，开创了计算复杂性理论。

套用

求不定方程的一组整数

方法

(注:以下出现的q(i)，r(i)括弧中的是下标，gcd(a,b)为a,b的最大公约数)

辗转相除法可以求出特定条件的不定方程的一组整数解。

设不定方程为ax+by=c，其中a,b,c为整数，且 gcd(a,b) | c

a,b辗转相除的算式为

b=q(1) a+r(2)

a=q(2) r(2)+r(3)

r(2)=q(3) r(3)+r(4)

...

r(n-2)=q(n-1)r(n-1)+r(n)

r(n-1)=q(n)r(n)

其中r(n)=gcd(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0

第i个算式为

r(i-1) = q(i) * r(i) + r(i+1)

所以r(i+1) = r(i-1) - q(i) * r(i) (*)

用公式(*)可以得到r(n)=gcd(a,b)关于a,b的线性组合sa+tb=gcd(a,b)

所以不定方程a*x+b*y=c的一组特解为x=s*c/gcd(a,b) y=t*c/gcd(a,b)

举例说明

例如不定方程为326x+78y=4，求出一组整数解x,y

求(326,78)的算式为:

326=4*78+1414=326-4*78

78=5*14+8 8=78-5*14

14=1*8+6 6=14-1*8

8=1*6+2 2=8-1*6

6=3*2

所以

2=8-6=8-(14-8)

=2*8-14=2*(78-5*14)-14

=2*78-11*14=2*78-11*(326-4*78)

=46*78-11*326

即2=(-11)*326+46*78

所以4=(-22)*326+92*78

所以x = - 22, y = 92是不定方程326x+78y=4的一组解。

相关原理

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如，252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 / 105 = 2余42，所以105和42的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。

辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数(十进位下)的五倍。加百利·拉梅(Gabriel Lamé)于1844年证明了这点，开创了计算复杂性理论。