大数的欧几里得算法

一种计算（查找）大数的最大公约数（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' × 'q₁' + 'r₁', 'r₁' 不为零。
步号 2: 'b' = 'r₁' × 'q₂' + 'r₂', 'r₂' 不为零。
步号 3: 'r₁' = 'r₂' × 'q₃' + 'r₃', 'r₃' 不为零。
...
步号 (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)' × 'q_n' + 'r_n', 'r_n' = 零。
余数为零，所以我们停止。

如果 'r_n' = 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)' 是 'r₃' 和 'r₂'的除数，所以它也是 'r₁' 的除数。
根据第二步： 'r_(n-1)' 是 'r₂' 和 'r₁'的除数，所以它也是 'b' 的除数。
根据第一步： 'r_(n-1)' 是 'r₁' 和 'b'的除数，所以它也是 'a' 的除数。

因此，我们刚刚证明了最后一个非零余数 r_(n-1) 是 'a' 和 'b' 的除数。

为什么这样得到的数总是等于最大公约数gcd？

正如我们在上面看到的，最终的非零余数是两个数 'a' 和 'b' 的除数。让我们将这个除数命名为 't'。
根据第一个划分步骤：如果 't' 是 'a' 和 'b' 的除数，那么它也是 'r₁' 的除数。
根据第二个划分步骤：如果 't' 是 'b' 和 'r₁' 的除数，那么它也是 'r₂' 的除数。
依此类推，直到编号为 (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').