最大公约数的性质以及求解方法

小鱼儿 2022-03-16 01:40 309阅读 0赞

最大公约数是指两个不同时为0的正数a和b的公约数中的最大值。记做![gcd(a, b)][gcd_a_ b]。下面是公约数的一些性质：

1.  ![gcd(a, b) = gcd(b, a)][gcd_a_ b_ _ gcd_b_ a]
2.  ![gcd(a, b) = gcd(-a, b)][gcd_a_ b_ _ gcd_-a_ b]
3.  ![gcd(a, b) = gcd(\\left | a \\right |, \\left | b \\right |)][gcd_a_ b_ _ gcd_left _ a _right _ _left _ b _right]
4.  ![gcd(a, 0) = \\left | a \\right |][gcd_a_ 0_ _ _left _ a _right]
5.  ![gcd(a, ka) = \\left | a \\right | 对于任意 k \\in Z][gcd_a_ ka_ _ _left _ a _right _ _ k _in Z] 对于任意![k\\in Z][k_in Z]
6.  ![gcd(a, b)][gcd_a_ b] 是a与b的线性集合![\\\{ax + by : x, y \\in Z\\\}][ax _ by _ x_ y _in Z]中的最小元素

最大公约数的求解方法，最先想打的是下面的解法：

int gcd(int a, int b){
    	int ans = 1;
    	for(int i = 1; i <= min(a, b); i++){
    		if(a % i == 0 && b % i == 0){
    			ans = max(ans, i);
    		}
    	}
    	return ans;
    }

我们可以把上面的程序变化一下，可以得到下面的程序。

int gcd(int a, int b){
    	for(int i = min(a, b); i >= 1; i--){
    		if(a % i == 0 && b % i == 0){
    			return i;
    		}
    	}
    }

下面我们提出另外的一种解法（辗转相除法）：

int gcd(int a, int b){
    	a = max(a, b);
    	b = min(a, b);
    	while(a % b != 0){
    		int tem = a % b;
    		a = b;
            b = tem;
    	}
    	return b;
    }

这种方法还可以写成递归的形式：

int gcd(int a, int b){
        if(b==0)
            return a;
        else
            return gcd(b, a%b);
    }

还有一种方法是辗转相减法：

int gcd(int a, int b){
    	while(1){
    		if(a > b){
    			a -= b;
    		}
    		else if(a < b){
    			b -= a;
    		}
    		else{
    			return a;
    		}
    	}
    }

写成递归的形式：

int gcd(int a, int b){
    	if(a > b){
    		return gcd(a - b, b);
    	}
    	else if(a < b){
    		return gcd(a, b - a);
    	}
    	else{
    		return a;
    	}
    }

[gcd_a_ b]: https://private.codecogs.com/gif.latex?gcd%28a%2C%20b%29
[gcd_a_ b_ _ gcd_b_ a]: https://private.codecogs.com/gif.latex?gcd%28a%2C%20b%29%20%3D%20gcd%28b%2C%20a%29
[gcd_a_ b_ _ gcd_-a_ b]: https://private.codecogs.com/gif.latex?gcd%28a%2C%20b%29%20%3D%20gcd%28-a%2C%20b%29
[gcd_a_ b_ _ gcd_left _ a _right _ _left _ b _right]: https://private.codecogs.com/gif.latex?gcd%28a%2C%20b%29%20%3D%20gcd%28%5Cleft%20%7C%20a%20%5Cright%20%7C%2C%20%5Cleft%20%7C%20b%20%5Cright%20%7C%29
[gcd_a_ 0_ _ _left _ a _right]: https://private.codecogs.com/gif.latex?gcd%28a%2C%200%29%20%3D%20%5Cleft%20%7C%20a%20%5Cright%20%7C
[gcd_a_ ka_ _ _left _ a _right _ _ k _in Z]: https://private.codecogs.com/gif.latex?gcd%28a%2C%20ka%29%20%3D%20%5Cleft%20%7C%20a%20%5Cright%20%7C%20%25u5BF9%25u4E8E%25u4EFB%25u610F%20k%20%5Cin%20Z
[k_in Z]: https://private.codecogs.com/gif.latex?k%5Cin%20Z
[ax _ by _ x_ y _in Z]: https://private.codecogs.com/gif.latex?%5C%7Bax%20&plus;%20by%20%3A%20x%2C%20y%20%5Cin%20Z%5C%7D