扩展欧几里得算法迭代实现的变量作用与运算逻辑疑问

核心不变式（解决a'、b'作用的疑问） #

整个迭代过程始终维持两个恒成立的等式，这是理解所有变量设计的核心：

• a' * m + b' * n = c
• a * m + b * n = d
  其中a'、b'就是当前迭代中变量c对应m、n的线性组合系数，a、b是当前迭代中变量d对应m、n的线性组合系数。

初始化规则的逻辑 #

E1步骤的初始化完全是为了满足上述两个不变式：
初始状态下c = m，d = n，代入上面的等式很容易得到：

• 要满足a'*m + b'*n = m，直接取a'=1、b'=0即可
• 要满足a*m + b*n = n，直接取a=0、b=1即可
  和你给出的E1步骤a′ ← b ← 1, a ← b′ ← 0完全对应。

迭代更新逻辑推导 #

系数更新公式的来源 #

普通欧几里得算法中，每轮计算余数r = c - q*d，我们把c和d的线性组合代入这个式子，就能得到r的线性组合：

r = c - q*d
  = (a'*m + b'*n) - q*(a*m + b*n)
  = (a' - q*a) * m + (b' - q*b) * n

这就是a = t - qa、b = t - qb的来源，其中t就是更新前的a'、b'的值。

变量交换的逻辑 #

欧几里得算法下一轮迭代的输入是(d, r)，对应下一轮的新c是原来的d，新d是原来的r，所以系数也要对应更新：

• 新c（原d）的系数：a' = 原a，b' = 原b
• 新d（原r）的系数：a = 原a' - q*原a，b = 原b' - q*原b
  你给出的E4步骤就是严格按照这个逻辑实现的：先暂存旧的a'、b'到临时变量t，再把a'、b'更新为原a、b，最后把a、b更新为我们推导的r的系数。

流程验证示例 #

以m=30，n=21为例，走一遍算法流程：

1. 初始化：a'=1, b=1, a=0, b'=0, c=30, d=21
2. E2：30/21得商q=1，余数r=9
3. E4更新：c=21，d=9；a'=0, a=1-1*0=1；b'=1, b=0-1*1=-1 → 验证：1*30 + (-1)*21=9，符合不变式要求
4. 下一轮E2：21/9得商q=2，余数r=3
5. E4更新：c=9，d=3；a'=1, a=0-2*1=-2；b'=-1, b=1-2*(-1)=3 → 验证：-2*30 +3*21=3，符合不变式要求
6. 下一轮E2：9/3得商q=3，余数r=0，终止，最终得到a=-2、b=3，满足30*(-2)+21*3=3，结果正确。

内容的提问来源于stack exchange，提问作者Prithvidiamond