了解扩展欧几里德算法的实现

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)，我也看不出为什么那个表达式 returns 的值是 t.

as + bt = gcd(a, b)中有一个著名的计算s和t的方法。在求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 是 return 的不错选择。

了解扩展欧几里德算法的实现

Understanding implementation of Extended Euclidean algorithm

haskell

euclidean-algorithm