UD5工具箱
最大公约数（GCD）
最大公约数（Greatest Common Divisor），也称最大公因数，是指两个或多个整数共有约数中最大的一个。例如，12和18的公约数有1、2、3、6，其中最大的是6，因此gcd(12, 18) = 6。GCD是数论中最基础的概念之一，它描述了整数之间共享因数的程度。在本工具中，GCD是核心计算目标，用户输入多个正整数后，工具通过辗转相除法求出它们的最大公约数。
最小公倍数（LCM）
最小公倍数（Least Common Multiple）是指两个或多个整数公倍数中最小的一个。例如，4和6的公倍数有12、24、36...，其中最小的是12，因此lcm(4, 6) = 12。LCM与GCD通过公式a × b = gcd(a, b) × lcm(a, b)紧密联系。在分数通分、周期同步等场景中，LCM有广泛应用。本工具在计算GCD的同时自动计算并展示LCM，为用户提供完整的公因数/公倍数信息。
辗转相除法
辗转相除法是求解两个正整数最大公约数的经典算法。其基本思想是：gcd(a, b) = gcd(b, a mod b)，即用较大数除以较小数取余数，然后用除数和余数重复此过程，直到余数为0，此时的除数即为GCD。该算法步骤少、效率高，时间复杂度为O(log min(a, b))。它是本工具的核心算法，每一步的除法、余数和状态转换都会在结果区域详细展示。
欧几里得算法
欧几里得算法（Euclidean Algorithm）是辗转相除法的正式名称，以古希腊数学家欧几里得的名字命名。欧几里得在约公元前300年编写的《几何原本》中首次系统描述了这一算法，它是人类数学史上最古老的仍然广泛使用的算法之一。算法的核心定理是：如果a = b × q + r（其中0 ≤ r < b），那么gcd(a, b) = gcd(b, r)。这个定理保证了算法的正确性和终止性。
互质
互质（Coprime或Relatively Prime）是指两个整数的最大公约数为1。例如，8和15互质，因为gcd(8, 15) = 1，它们没有除了1以外的公共因数。互质是数论中一个非常重要的概念，在RSA加密、模逆运算、分数化简等场景中都有关键应用。两个素数一定互质，一个素数和任何不被它整除的数也互质。在本工具中，如果计算结果显示GCD=1，就说明输入的数字两两互质（或整体互质）。
公约数
公约数（Common Divisor）是指能同时整除两个或多个整数的数。例如，12的约数有1、2、3、4、6、12，18的约数有1、2、3、6、9、18，它们的公约数有1、2、3、6。公约数中最大的那个就是最大公约数（GCD）。公约数的概念是理解GCD的基础——GCD本质上就是所有公约数中的最大值。在分数化简中，找到分子分母的公约数是约分的关键步骤。
因数分解
因数分解（Factorization）是将一个整数表示为若干个素数乘积的过程。例如，12 = 2² × 3，18 = 2 × 3²。通过比较各素因数的最小指数，可以求出GCD：gcd(12, 18) = 2¹ × 3¹ = 6。因数分解是理解GCD的另一种视角，虽然在大数场景下不如辗转相除法高效，但对于小数字非常直观。本工具使用辗转相除法而非因数分解法，因为辗转相除法在大数场景下效率远高于因数分解。
更相减损术
更相减损术是中国古代数学著作《九章算术》（约公元1世纪）中记载的求最大公约数的方法。其原理是：用较大数减去较小数，然后用差和较小数重复此过程，直到两数相等。例如，求gcd(48, 18)：48-18=30, 30-18=12, 18-12=6, 12-6=6，两数相等，GCD=6。与辗转相除法相比，更相减损术使用减法代替除法，运算更简单但步数可能更多（尤其当两数相差悬殊时）。本工具的FAQ中详细对比了这两种算法的异同。
RSA加密算法
RSA是一种广泛使用的非对称加密算法，其安全性基于大整数因数分解的困难性。在RSA密钥生成过程中，需要选择两个大素数p和q，计算n=p×q，然后求φ(n)=(p-1)(q-1)，接着选择e使得gcd(e, φ(n))=1（即e与φ(n)互质）。GCD计算在RSA中扮演着关键角色：验证e与φ(n)互质需要计算GCD，扩展欧几里得算法用于求模逆元。这也是为什么工具FAQ中将RSA列为GCD的重要应用场景之一。
斐波那契数
斐波那契数列是每个数等于前两个数之和的数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55...。斐波那契数与辗转相除法有一个著名的关系：连续的斐波那契数是辗转相除法的最坏情况输入。例如，求gcd(55, 34)需要最多的除法步骤。这是因为斐波那契数的相邻两项之比逼近黄金比例，每步除法的余数恰好是前一个斐波那契数，导致需要最多步数才能达到余数为0。工具的FAQ中提到了这一有趣的数学联系。
时间复杂度
时间复杂度是衡量算法效率的指标，表示算法执行时间随输入规模增长的增长速率。辗转相除法的时间复杂度为O(log min(a, b))，意味着计算步数与较小数的对数成正比。例如，输入1000和1只需约10步，输入1000000和1只需约20步。这种对数级别的效率使得辗转相除法即使面对数百位的大整数也能在毫秒内完成。O(log min(a, b))这个上界可以通过拉梅定理精确描述：步数不超过较小数十进制位数的5倍。
模运算
模运算（Modular Operation）是求两个数相除的余数的运算，记作a mod b。例如，48 mod 18 = 12（因为48 ÷ 18 = 2 余 12）。模运算是辗转相除法的核心操作——算法的每一步都涉及一次模运算来获取余数，然后用余数更新计算状态。在编程中，模运算通常用%符号表示。模运算在数论、密码学、哈希函数等领域有广泛应用，是本工具算法实现中使用最频繁的基本运算。