大数的欧几里得算法——最大公约数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').