扩展欧几里得算法

• 下载演示项目 - 16.6 Kb

引言

扩展欧几里得算法定理的表述。(扩展欧几里得算法。) 设m和n为正整数。定义

   a[0] = m,  a[1] = n,
 
   q[k] = Floor (a[k-1]/a[k])  for  k > 0,
 
   a[k] = a[k-2] - a[k-1] q[k-1]  for  k > 1,
 
   x[0] = 1,  x[1] = 0,  y[0] = 0,  y[1] = 1,
 
   x[k] = x[k-2] - q[k-1] x[k-1]  for  k > 1,
 
   y[k] = y[k-2] - q[k-1] y[k-1]  for  k > 1.

如果a[p]是最后一个非零的a[k]，那么

   a[p] = (m,n) = x[p] m + y[p] n.

(实数x的Floor是指小于或等于x的最大整数。所以Floor(1.5) = 1，Floor(-2.1) = -3，并且Floor(0) = 0。)

不要被所有的下标吓到! 信不信由你，如果你小心地将数字排列在一个表格中，这个算法对于手工计算来说并不难。

在我给出证明之前，这里有一个快速的概述。q通过连续除法计算最大公约数，即使用标准的欧几里得算法。 这没什么新鲜的! x和y用于簿记; 它们最终会产生线性组合中的系数。

证明。我将接受标准欧几里得算法的陈述和证明。

忽略x和y，a和q的计算与标准欧几里得算法的计算相同：a是余数，q是商。因此，该算法终止，当它终止时，最后一个非零的a是最大公约数(m,n)。

我声明

x[k]a[0] + y[k]a[1] = a[k]  for  k > 0.

我将用归纳法证明这一点。

对于k = 1，我有

x[1]a[0] + y[1]a[1] = 0[1] a[0] + 1[1] a[1] = a[1].

现在，取k > 1，并假设结果对于所有小于或等于k的指数都成立。 我想证明k + 1的结果。 计算

   x[k+1] a[0] + y[k+1] a[1] =
 
      (x[k-1] - q[k] x[k]) a[0] + (y[k-1] - q[k] y[k]) a[1] =
 
      (x[k-1] a[0] + y[k-1] a[1]) - q[k] (x[k] a[0] + y[k] a[1]) =
 
      a[k-1] - q[k] a[k] =
 
      a[k+1].

第一个等式来自x和y的定义。 我使用归纳假设来得到第三个等式。 最后一个等式使用a的定义。

该结果对于k + 1 成立，所以通过归纳法，它对于所有k > 0 成立。 特别是，如果a[p] = (m,n)是最后一个非零的a，那么

   x[p] a[0] + y[p] a[1] = a[p] = (m,n).

扩展欧几里得算法

如果m和n是整数（不都为0），则m和n的最大公约数(m,n)是能同时整除m和n的最大整数。 欧几里得算法使用重复除法来计算最大公约数。

m和n的最大公约数可以表示为m和n的整数线性组合。 也就是说，存在整数c和d，使得

   (m,n) = c m + d n.

存在无限多对数字c，d有效； 有时，您可以通过反复试验找到一对。 例如，(10,7) = 1，通过在我脑海中调整数字，我看到

  1 = (-2)(10) + (3)(7).

另一方面，(367,221) = 1，但你不太可能弄清楚

   1 = (-56)(367) + (93)(221)

通过在你脑海中调整数字!

扩展欧几里得算法计算整数m和n的最大公约数(m,n)，以及数字c和d，使得

   (m,n) = c m + d n.