最大公约数是什么

最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个整数共有约数中最大的一个，换句话说，它是能同时整除这些整数的最大正整数，最大公约数在数学、计算机科学和密码学等领域都有广泛的应用。

最大公约数的性质

1、若a、b是整数，且a>b，则gcd(a, b) = gcd(b, a mod b)。

2、若a、b是整数，且gcd(a, b) = d，则gcd(a+b, b) = d。

3、若a、b是整数，且gcd(a, b) = d，则gcd(ab, b) = d。

4、若a、b是整数，且gcd(a, b) = d，则gcd(ab, b) = d。

5、若a、b是整数，且gcd(a, b) = d，则gcd(a/b, 1) = d。

求最大公约数的方法

1、欧几里得算法（辗转相除法）：通过不断将较大的数除以较小的数，然后用余数替换较大的数，直到余数为0，此时的除数就是最大公约数。

公式：gcd(a, b) = gcd(b, a mod b)

2、更相减损法：通过不断将两个数相减，然后用差替换较大的数，直到两数相等，此时的差就是最大公约数。

公式：gcd(a, b) = a b

最大公约数的应用

1、简化分数：通过求两个分数的最小公倍数和最大公约数，可以将分数化为最简形式。

2、解决线性方程组：通过求解线性方程组的公共解，可以得到最大公约数。

3、素数分解：通过求解两个数的最大公约数，可以对大整数进行素数分解。

4、密码学：在RSA加密算法中，需要求解两个大质数的最大公约数，以生成公钥和私钥。