GCD

GCD（最大公约数）是同时整除两个或多个整数的最大正整数，用欧几里得算法高效计算。

用途

求多整数的最大公共因子，用于分数化简与数论。

机制

欧几里得算法：gcd(a,b) = gcd(b, a mod b)，直至 b=0。扩展欧几里得算法额外求 Bezout 系数 x,y 使 ax+by=gcd(a,b)，用于模逆元。lcm(a,b) = |a×b|/gcd(a,b)。

用例

分数化简
模逆元计算
RSA 密钥验证
有理数运算

示例

输入
```
gcd(48, 18)
```
输出
```
6
```
48=6×8, 18=6×3

常见错误

gcd with 0 left unhandled: gcd(a,0)=|a|, gcd(0,0)=0

相关词条

LCM（最小公倍数）是两个或多个整数的公共倍数中最小的正整数，通过 GCD 计算。

Modular Arithmetic

模运算是整数运算后取模的算术，结果在 [0, n) 范围内，是数论与密码学的基础。

素数是大于 1 且仅能被 1 和自身整除的自然数，是数论的积木，所有整数可唯一分解为素数积。

相关工具

高精度计算器

高精度算术计算器，无浮点误差。免费、隐私本地化、100% 客户端运行。

参考链接