数论/唯一分解和积性函数
给定两个不互质的数,求其最大公约数。
该算法基于以下两个观察结果
1. If b|a then gcd(a, b) = b.
事实确实如此,因为任何数(特别是 b)的除数都不能大于该数本身(我在这里谈论非负整数)。
2. If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r).
实际上,a 和 b 的任何公约数也除以 r。因此 gcd(a, b) 除以 r。但是,当然,gcd(a, b)|b。因此,gcd(a, b) 是 b 和 r 的公约数,因此 gcd(a, b)=gcd(b, r)。反之亦然,因为 b 和 r 的任何除数也除以 a。
例子
Let a = 2322, b = 654. 2322 = 654*3 + 360 gcd(2322, 654) = gcd(654, 360) 654 = 360*1 + 294 gcd(654, 360) = gcd(360, 294) 360 = 294*1 + 66 gcd(360, 294) = gcd(294, 66) 294 = 66*4 + 30 gcd(294, 66) = gcd(66, 30) 66 = 30*2 + 6 gcd(66, 30) = gcd(30, 6) 30 = 6*5 gcd(30, 6) = 6 Therefore, gcd(2322,654) = 6.
对于任何一对 a 和 b,该算法一定会终止,因为每一步都会生成一个类似的问题(即求 gcd)对于一对较小的整数。令 Eulen(a,b) 表示一对 a,b 的欧几里得算法的长度。Eulen(2322, 654) = 6,Eulen(30, 6) = 1。我将在以下算法的重要结果的证明中使用此符号:推论对于每对整数 a 和 b,都存在两个整数 s 和 t,使得 as + bt = gcd(a, b)。例子
2322×20 + 654×(-71) = 6。证明
设 a > b。证明是通过对 Eulen(a, b) 进行归纳。如果 Eulen(a, b) = 1,即如果 b|a,那么 a = bu 对于某个整数 u。因此,a + (1 - u)b = b = gcd(a, b)。我们可以取 s = 1 和 t = 1 - u。
假设对于所有 Eulen 小于 n 的数字对,推论已经成立。设 Eulen(a, b) = n。执行一步算法:a = bu + r。Eulen(b, r) = n - 1。根据归纳假设,存在 x 和 y 使得 bx + ry = gcd(b,r) = gcd(a,b)。将 r 表示为 r = a - bu。因此,ry = ay - buy;bx + (ay - buy) = gcd(a, b)。最后,b(x - uy) + ay = gcd(a, b),我们可以取 s = x - uy 和 t = y。
还有一个利用鸽巢原理的简单证明。备注
注意,任何线性组合 as + bt 都可以被 a 和 b 的任何公因子整除。特别是,a 和 b 的任何公因子也整除 gcd(a, b)。在“逆”应用中,任何线性组合 as + bt 都可以被 gcd(a, b) 整除。由此得出,gcd(a, b) 是可以表示为 as + bt 形式的最小正整数。所有其他数都是 gcd(a, b) 的倍数。推论在任意域上的推广被称为贝祖恒等式或贝祖引理,以法国数学家埃蒂安·贝祖 (1730-1783) 的名字命名,因此在推论中陈述的结果通常也称为贝祖恒等式或贝祖引理。
对于互质数,我们得到存在 s 和 t 使得 as + bt = 1。这个推论是一个强大的工具。它出现在 3 个玻璃杯和沙漏问题中。例如,让我们证明欧几里得命题 VII.30 如果两个数相乘得到一个数,并且任何素数除以该乘积,那么它也除以其中一个原始数。
设素数 p 除以乘积 ab。假设 pa。那么 gcd(a, p) = 1。根据推论,对于某些 x 和 y,ax + py = 1。乘以 b:abx + pby = b。现在,p|ab 且 p|pb。因此,p|b。
实际上,这证明了命题 VII.30 的一个推广,我在这些页面上多次使用:设 m|ab 且 gcd(a, m) = 1。那么 m|b。
命题 VII.30 直接蕴含算术基本定理,尽管欧几里得从未明确地陈述过它。它第一次是在 1801 年由高斯在他的《算术研究》中提出的。算术基本定理任何整数 N 都可以表示为素数的乘积。这种表示对于素因子的顺序来说是唯一的。
因为,根据定义,如果一个数除了 1 和它本身之外还有其他因子,则它是合数,而这些因子必然小于该数,我们可以不断提取因子,直到只剩下素因子。这表明表示的存在:N = pqr...,其中所有 p、q、r... 都是素数。为了证明唯一性,假设有两个表示:N = pqr... = uvw... 我们看到 p 除以 uvw... 根据推论,它除以其中一个因子 u、v、w... 将它们消去。我们可以继续将左右两侧剩余的因子消去,直到没有因子剩余。
将一个数表示为素数的乘积称为素数分解。算术基本定理断言,每个整数都有唯一的素数分解。