最大公约数（GCD），能同时整除多个整数的最大正整数。欧几里得算法：gcd(a,b)=gcd(b,a mod b)，时间复杂度O(log min(a,b))。扩展算法可求贝祖系数ax+by=gcd(a,b)。应用：分数约简（分子分母除gcd）、密码学（RSA密钥生成）、线性同余方程求解。性质：gcd(a,b)×lcm(a,b)=a×b，多个数gcd可迭代计算gcd(gcd(a,b),c)。