数论 - ExGCD 算法推导

2017/10/10

我好菜啊。 _(:з」∠)_

推导

递归推导

推导这么一件事,已知

因为 exgcd 是递归的,所以假设我们知道了这么一件事,妄图通过这件事推导出上面那件事。

联立一下

因为 ,接着让 对齐

然后我们希望把取模搞成一个带余除法

这个时候 xjb 整理一波

此时有

嘻嘻。

终止条件

然后考虑一波终止条件,这个时候有式子:

一组最小解为