大数的欧几里得算法——最大公约数gcd和最小公倍数lcm的计算方法。 LCM (a; b) = (a × b) / gcf (a; b) - 理论、例子和解释
一种计算（查找）大数的最大公约数（gcd）的方法
- 对于大数，素数分解过程是漫长而困难的。 如果我们需要计算这些大数的最大公约数，那么与质因数分解不同的方法将非常受欢迎。 欧几里得算法，也称为辗转反侧，是一种计算最大公约数的方法。 看看下面的例子。 我们还将解释它为什么起作用。
- 该算法首先将两个数字相除并记录操作的其余部分。
- 如果 'a' 和 'b' 是两个正整数，则 'a' >= 'b'。计算公式gcd (a, b) = gcd (b, a mod b)。
- 将 'a' 除以 'b' 并得到余数 'r'。
- 如果 'r' = 0，则停止。 那么'b'就是'a'和'b'的gcd。
- 否则：将 ('a' 替换为 'b') 和 ('b' 替换为 'r')。 返回上一步。
让我们看看数字 5,3667 和 2,5527 的最大公约数 (gcd) 是多少：
- [1] 首先将较大的数字除以较小的数字：
- 5,3667 ÷ 2,5527 = 2 余数 = 2613 => 5,3667 = 2,5527 × 2 + 2613
- [2] 然后将较小的数字除以上述操作的余数：
- 2,5527 ÷ 2613 = 9 余数 = 2010 => 2,5527 = 2613 × 9 + 2010
- [3] 将第一个运算的余数除以第二个运算的余数：
- 2613 ÷ 2010 = 1 余数 = 603 => 2613 = 2010 × 1 + 603
- [4] 将第二次运算的余数除以第三次运算的余数：
- 2010 ÷ 603 = 3 余数 = 201 => 2010 = 603 × 3 + 201
- [5] 将第三次运算的余数除以第四次运算的余数：
- 603 ÷ 201 = 3 余数 = 0 => 603 = 201 × 3
- 在这一步，余数为零，所以我们停止：201 是我们正在寻找的数字。
- 结论：
- 201 是最后一个非零余数。 这是这两个数字的最大公约数 (gcd)。
任何两个给定数字的最大公约数是最后一个非零余数。
- 如果最后一个余数等于 1，则这两个数互质。
- 对于上述运算，最后一个非零余数 201 是数字 5,3667 和 2,5527 的最大公约数 (gcd)。
- 通过使用欧几里得算法，我们可以证明两个数互质，见下面的例子。
计算最大公约数 gcd (87, 41)：
- [1] 首先将较大的数字除以较小的数字：
- 87 ÷ 41 = 2 余数 = 5 => 87 = 41 × 2 + 5
- [2] 然后将较小的数字除以上述操作的余数：
- 41 ÷ 5 = 8 余数 = 1 => 41 = 5 × 8 + 1
- [3] 将第一个运算的余数除以第二个运算的余数：
- 5 ÷ 1 = 5 余数 = 0 => 5 = 1 × 5 + 0
- 上述操作的最后一个非零余数等于 1。
- gcd (87, 41) = 1，所以这些数字互质。
但是为什么这样得到的数字是初始值'a'和'b'的除数呢？
- 注意：除法 'a' ÷ 'b' = 'q' + 'r' 对应方程： 'a' = 'b' × 'q' + 'r'，其中 'q' 是除法的商。
- 如果 'r' 的最后一个值 = 0，那么 'b' 的最后一个值是 'a' 的最后一个值的除数，因为 'a' = 'b' × 'q' + 0。
- 让我们计算 gcd (a, b)：
- 步号 1: 'a' = 'b' × 'q1' + 'r1', 'r1' 不为零。
- 步号 2: 'b' = 'r1' × 'q2' + 'r2', 'r2' 不为零。
- 步号 3: 'r1' = 'r2' × 'q3' + 'r3', 'r3' 不为零。
- ...
- 步号 (n-3): 'r(n-5)' = 'r(n-4)' × 'q(n-3)' + 'r(n-3)', 'r(n-3)' 不为零。
- 步号 (n-2): 'r(n-4)' = 'r(n-3)' × 'q(n-2)' + 'r(n-2)', 'r(n-2)' 不为零。
- 步号 (n-1): 'r(n-3)' = 'r(n-2)' × 'q(n-1)' + 'r(n-1)', 'r(n-1)' 不为零。
- 步号 n: 'r(n-2)' = 'r(n-1)' × 'qn' + 'rn', 'rn' = 零。
- 余数为零，所以我们停止。
- 如果 'rn' = 0 => 根据编号为 n 的步骤： 'r(n-1)' 是 'r(n-2)' 的除数。
- 'r(n-1)' 也是最后一个非零余数。
- 根据编号为 (n-1) 的步长： 'r(n-1)' 是 'r(n-1)'（数字本身）和 'r(n-2)'的除数， 所以它也是 'r(n-3)' 的除数。
- 根据编号为 (n-2) 的步长： 'r(n-1)' 是 'r(n-2)' 和 'r(n-3)'的除数， 所以它也是 'r(n-4)' 的除数。
- 根据编号为 (n-3) 的步长： 'r(n-1)' 是 'r(n-3)' 和 'r(n-4)'的除数， 所以它也是 'r(n-5)' 的除数。
- ...
- 根据第三步： 'r(n-1)' 是 'r3' 和 'r2'的除数， 所以它也是 'r1' 的除数。
- 根据第二步： 'r(n-1)' 是 'r2' 和 'r1'的除数， 所以它也是 'b' 的除数。
- 根据第一步： 'r(n-1)' 是 'r1' 和 'b'的除数， 所以它也是 'a' 的除数。
- 因此，我们刚刚证明了最后一个非零余数 r(n-1) 是 'a' 和 'b' 的除数。
为什么这样得到的数总是等于最大公约数gcd？
- 正如我们在上面看到的，最终的非零余数是两个数 'a' 和 'b' 的除数。 让我们将这个除数命名为 't'。
- 根据第一个划分步骤： 如果 't' 是 'a' 和 'b' 的除数，那么它也是 'r1' 的除数。
- 根据第二个划分步骤： 如果 't' 是 'b' 和 'r1' 的除数，那么它也是 'r2' 的除数。
- 依此类推，直到编号为 (n-1) 的除法步骤： 如果 't' 是 'r(n-3)' 和 'r(n-2)' 的除数， 那么它也是 'r(n-1)' 的除数。 但正如我们上面计算的，这个特定的除数是最后一个非零余数，在我们的例子中是 'r(n-1)'。
- 所以 't' 不能大于 'r(n-1)' 因为它必须是它的除数。
如何对两个以上的数使用欧几里得算法：
- 欧几里得算法也可以用来求多个数的最大公约数，多于两个的数，如'a'、'b'和'c'。
- 首先计算 gcd ('a', 'b') = 'd'，然后计算 gcd ('c', 'd')。
欧几里得算法：计算大数的最小公倍数 (lcm)
- 在欧几里得算法的帮助下，不仅可以找到最大公约数 (gcd) - 如上所示，而且根据以下公式计算最小公倍数 (lcm)：
lcm ('a', 'b') = ('a' × 'b') / gcd ('a', 'b')
- 或者，如果我们使用数字 'a' 和 'b' 的最小公倍数的符号为 ['a', 'b']，... 和... 对于 'a' 和 'b' 的最大公约数，我们使用符号 ('a', 'b')：
['a', 'b'] = ('a' × 'b') / ('a', 'b')
- 当数字不超过两个时，可以使用此方法。
lcm公式的证明
- 假设分解成素数的数字 'a' 和 'b' 可以写成：
- 'a' = 'm' × 'n' × 'p', 其中 'm', 'n', 'p' 是任何素数。
- 'b' = 'm' × 'q' × 't', 其中 'm'、'q'、't' 是任何素数。
- => lcm ('a', 'b') = 'm' × 'n' × 'p' × 'q' × 't'
- => gcd ('a', 'b') = 'm'
- 因此：
- ('a' × 'b') / gcd ('a', 'b') =
- ('m' × 'm' × 'n' × 'p' × 'q' × 't') / 'm' =
- 'm' × 'n' × 'p' × 'q' × 't' =
- lcm ('a', 'b').
一些关于素数的文章