算法中的模块化反演

Question

我正在阅读Sanjoy das gupta在Algorithms第33页的算法书中的扩展Euclid算法

假设我们想计算11^-1 mod 25。使用扩展的Euclid算法，我们发现15 * 25 - 34 * 11 = 1。减少双方模25，我们有-34 * 11全等于1 mod 25.所以-34全等于16 mod 25是11 mod 25的倒数。

我的问题作者如何得出结论“-34 congruent等于16 mod 25是11 mod 25的逆。”从以前的声明。

Answer 1

从15 * 25 - 34 * 11 = 1你有15 * 25 - 34 * 11 = 1 mod 25导致-34 * 11 = 1 mod 25。

如果你有a * b = 1，那么a是b的乘法逆，如果a和b是矩阵，场元素或残余类环的元素。

当你将-34标准化为0到24之间的范围时，得到结果16：16 = 2 * 25 - 34，因此16 * 11 = 1 mod 25。注意：恰好有一个自然的k，k * 25 - 34在0到24之间，在这种情况下这是2。