欧几里得算法中的系数符号交替（在初始零消失之后），因此我们可以仅使用幅度来计算它们，并在迭代奇偶性的末尾重构符号。
扩展欧几里得算法求正互素整数 u 和 v 的乘法逆 a 和 B，即求 a 和 b，使得 a·u 模1 v，b·v 模1 u。我们从两个方程开始：

• u = 1·u + 0·v。
• v = 0·u + 1·v。

则算法为：

• 令 x 和 y 为最后两个方程的左边（y 在后面）。
• 如果 y 是1，我们就完成了。右边的 u 和 v 的系数分别是 u 和 v 的逆。
• 否则，令 q 为整数商 x 除以 y。附加一个新的等式，该等式等于前一个等式减去后一个等式乘以 q。

这在方程的左边实现了欧几里得算法，所以我们知道它对于互质的 u 和 v 终止于1。那么最后一个方程具有以下形式：

• 1 = a·u + B·v。

在这里，很明显 a 是 u 模 v 的乘法逆，B 是 b 模 u 的乘法逆。
注意，在第三个方程中，u 的系数为1−0·q，因此它是正的;v 的系数为0−1·q，因此它是负的;在第四个方程中，u 的系数是正的，从这一点开始，我们总是从正数中减去负数，或者从负数中减去正数。因此我们交替符号。
在第 n 个方程中，如果 n 是奇数，则 u 的系数是非负的，如果 n 是偶数，则 u 的系数是非正的，对于 v 的系数，反之亦然。
因此，我们可以通过仅保留系数的幅度来用无符号算术实现这一点：

• 给定已知非负系数的量值 g 和已知非正系数的量值 h，计算新的量值为 g+h·q。
• 给定已知非正系数的量值 g 和已知非负系数的量值 h，计算新的量值为 g+h·q。

13和10的示例：

• 13 = 1·13 + 0·10。
• 10 = 0·13 + 1·10。
• 13/10的商为1，计算13−1·10 = 3，1+0·1 = 1，0+1·1 = 1，得到：
• 3 = 1·13 − 1·10（符号是隐式已知的，而不是计算出来的）。
• 10/3的商为3，计算10−3·3 = 1，0+1·3 = 3，1+1·3 = 4，得到：
• 1 = -3 13 + 4 10。

此时，无论我们用什么变量来保存 u（13）的系数，它都包含3，但我们知道它是负的，因为我们在偶数次迭代（第四次）中，所以 u 的逆是-3。如果需要，我们可以加上 u（计算为 u 减去存储的量值），得到正的结果。
我已经证明了这些计算不会超过 * v * 的系数 u 或 *v * 的系数 u，但我无法访问该证明。（它嵌入在前一个雇主的源代码中。）

Eric Postpischil是完全正确的，但是答案很难读懂，特别是如果您正在寻找只会工作的代码，那么下面就开始吧：

template<typename T>
typename std::enable_if<std::is_unsigned<T>::value,tuple<T,T>>::type
constexpr extended_euclidean(const T a, const T b)
{
  T r0 = a;
  T r1 = b;
  T s0 = 1;
  T s1 = 0;
  T t0 = 0;
  T t1 = 1;
  size_t n = 0;
  while (r1) {
    T q = r0 / r1;
    r0 = r0>q*r1?r0-q*r1:q*r1-r0; swap(r0,r1);
    s0 = s0+q*s1; swap(s0,s1);
    t0 = t0+q*t1; swap(t0,t1);
    ++n;
  }
  // gcd = r0
  if (n%2) s0=b-s0;
  else     t0=a-t0;
  return tuple<T,T>({s0,t0});
}

所以基本上我们是在做标准的欧几里得算法，但是当计算余数时，我们只关心大小，当更新系数时，我们只需要相加。大小的符号需要在最后使用奇偶性，使用计数器n来固定。