本文共 1850 字，大约阅读时间需要 6 分钟。

一、Bezout定理的证明

证明：

构造集合S={am+bn：m，n∈Z ，且am+bn≥0}

显然，集合S非空，根据良序原则，取其中最小值d=ar+bs，我们要证明 d=gcd（a，b）

令$a=dq+r_1$，且0 ≤ r₁＜d。

如果r₁大于0，可以得到

$r1=a-dq$

$=a-(ar+bs)q$

$=a-arq-bsq$

$=a(1-rq)+b(-sq)$

  该结果属于S集合,但是与d是该集合的最小元素相矛盾，因此r₁=0，并且d整除a，同理可得d整除b，因此d是a和b的公因子

  假设d₁是a和b的另一个公因子，我们需要证明d₁ | d.

令$a=d_{1}h$ , $b=d_{1}k$,则

$d=ar+bs=d_{1}hr+d_{1}ks=d_1(br+ks)$

  则可以得到 d₁ | d ，因此d一定是a和b的最大公因子。

二、实现GCD的迭代版本

#include
   
    int gcd(int a,int b){
   	if(a
    
     b	int r=0;	r=a%b;	while(r!=0)	{
   		a=b;		b=r;		r=a%b;	}//辗转相除法	if(b<0){
   b=-b;}	return b;}int main(){
   	int a,b;	printf("请输入两个数a和b：\n");	scanf("%d %d",&a,&b);	printf("a和b的最大公因子为：%d\n",gcd(a,b));	return 0;}
    
   

三、实现EGCD算法

输入a，b两个整数，输出：r，s，d三个数，满足$ar+bs=d$：

#include
   
    int* egcd(int a,int b){
   	int A[3];	int r1=1,s1=0;//a,b的系数，即a=1*a+0*b	int r2=0,s2=1;//b=0*a+1*b	int M=a,N=b;	if(a
    
     N){
   A[1]=r2;A[2]=s2;}	else   {
   A[1]=s2;A[2]=r2;}	return A;}int main(){
   	int a=0,b=0;	printf("请输入两个整数a和b:\n");	scanf("%d %d",&a,&b);	printf("d=%d r=%d s=%d\n",egcd(a,b)[0],egcd(a,b)[1],egcd(a,b)[2]);	return 0;}
    
   

四、实现一种批处理版本的GCD算法

即给定一个整数数组a，输出：一个整数d，是a数组中所有整数的最大公因子。

#include
   
    int array_gcd(int *a,int n){
   	int i=0;	int r=0;	for(i=0;i
    
     =a[i+1]	     r=a[i]%a[i+1];	     while(r!=0)		{
   		    a[i]=a[i+1];		    a[i+1]=r;		    r=a[i]%a[i+1];	    }//辗转相除法	}	return a[i];}int main(){
   	int n=0;	int *a=new int[100];	printf("请输入一组数（输入0停止）：\n");    do	{
   scanf("%d",&a[n]);n++;}	while(a[n-1]!=0);	printf("这个数组的最大公因子为：%d\n",array_gcd(a,n-1));	delete a;	return 0;}
    
   

转载地址：https://blog.csdn.net/m0_55443969/article/details/120499726 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！