haskell - 理解扩展欧几里得算法的实现

Question

经过一些实验和搜索，我想出了以下定义：

emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b = 
  let (g, t, s) = emcd' b r
  in (g, s, t - (q * s))
    where
      (q, r) = divMod a b

• 这个表达背后的含义是什么t - (q * s)？

我试图手动评估它；即使我得到了正确的结果(1, -4, 15)，我也看不出为什么该表达式返回t.

有一种著名的计算方法s和tin as + bt = gcd(a, b)。在寻找 gcd 的过程中，我得到了几个方程。

通过反转欧几里得算法中的步骤，可以找到这些整数a和b。那些得到的方程看起来像表达式t - (q * s)；但是，我无法弄清楚确切的过程。

Answer 1

因为(q, r) = divMod a b，我们有方程

a = qb + r

由于递归调用，我们有：

tb + sr = g

代a-qb入r第二个等式，这意味着

tb + s(a-qb) = g
tb + sa - qsb = g
sa + (t-qs)b = g

这解释了为什么s并且t - q*s是返回的好选择。