辗转相除法（gcd）求两个数的最大公约数_gcd辗转相除法

辗转相除法求两个数的最大公约数

简介

欧几里得算法又称辗转相除法，是指用于计算两个非负整数$a，b$的最大公约数（Greatest Common Divisor，简称gcd）。
其基本思想是：以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

定理

其计算原理依赖于下面的定理：
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
设两数$a，b（a\ge b）$并用$gcd(a,b)$表示$a，b$的最大公约数，$amodb$表示$a$模$b,$比如$10mod3=1$,有：
$$gcd(a,b)=gcd(b,amodb)$$
比如：$gcd(25,10)=gcd(10,5)$

定理证明（选看）

定理证明过程：
设$c=gcd(a,b)$,即$c$是$a,b$的最大公约数。则有：
$$a=mc,b=nc(m\ge n\ge 1且m，n互质)(1)$$
设$a=k\ast b+r$,即
$$amodb=r,a÷b=k$$
对$a=k\ast b+r$进行变形：
$$r=a-k\ast b=m\ast c-k\ast n\ast c=(m-k\ast n)\ast c$$
接下来只需证明 $m-k\ast n$ 与 $n$ 互质即可，这是因为：
$$b=n\ast c$$
$$r=(m-k\ast n)\ast c$$
根据最大公约数的定义，只要 $m-k\ast n$ 与 $n$ 互质，就可以说明$c$是$b和r$的最大公约数，即：
$$gcd(b,c)=c=gcd(a,b)$$
这就是定理的结论。
接下来用反证法证明：$m-k\ast n$与 $n$互质
假设$gcd（n,m-k\ast n）=d$,即：
$$n=x\ast d,m-k\ast n=y\ast d$$
则有：
$$m=y\ast d+k\ast n=(y+k\ast x)\ast d$$
又因为$n=y\ast d$，
所以$m$与$n$有公约数$d$,与式$(1)$矛盾
即证$m-k\ast n$ 与 $n$ 互质，所以定理成立。

展辗转相除法

展辗转相除法就是反复利用该定理，直到$r=0$时，对应的$b$就是两数的最大公约数；
因为$r=0$表示$a/b=k(余0)$,即$a=k\ast b$,
则$a,b$有最大公约数b。

假如需要求 615 和 152 两个正整数的最大公约数,用辗转相除法计算过程：
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1。
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 615 和 152 的最大公约数 1。

代码

c语言代码

int gcd(int p,int q){
    if(q==0) return p;
    int r=p%q;
    return gcd(q,r);
}
1
2
3
4
5

注意事项

这里说明的是调用gcd（）函数时的注意事项。
1.调用时不一定要求$p\ge q$。
2.$p,q$可以是负数，但是一般最大公约数的讨论范围是正整数,结果与都是正数的情况也只是在数值上相等。
3.当有一个参数为0时，结果是另一个参数。

#include<stdio.h>
int gcd(int p, int q) {
	if (q == 0) return p;
	int r = p % q;
	return gcd(q, r);
}
int main()
{
	printf("%d\n",gcd(25, 10));
	printf("%d\n",gcd(10, 25));
	printf("%d\n",gcd(25, -10));
	printf("%d\n",gcd(-25, 10));
	printf("%d\n",gcd(-25, -10));
	printf("%d\n",gcd(0, 10));
	printf("%d\n",gcd(25, 0));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

输出结果
5
5
5
-5
-5
10
25