math - 如何从余数系统转换为混合基数系统？

Question

我了解残数系统的概念和混合基数系统的概念，但我很难让我发现的任何转换方法在一个简单的案例研究中起作用。

我从 Knuth 的《计算机编程艺术》开始，但是这对转换的理论有点过多，一旦提到欧拉，我就迷路了。维基百科有一个关于这个主题的好部分，我在这里和这里尝试过，但两次我都无法回到我开始时的号码。

我在这里找到了一篇好文章(PDF)，我在此处浓缩了相关部分，但我不了解乘法逆元及其符号。具体来说，如何 y_2 = |(3 - 19)|(1/31)|_7|_7 = |5 * 5|_7 特别是如何 |1/31|_7 = 5

score 1 · Accepted Answer

乘法逆元将针对模数（此处为 7）进行。由于模 7 是素数，因此每个数（模 7）都有一个倒数。特别是 31_7 = 3_7（因为 31 = 4*7 +3 - 对不起，如果我太说教了），它的倒数是 5，因为 3 * 5 = 15 = 1_7。所以我们可以写成 |1/31|_7 = 5。

现在

y_2 = |(3 - 19) |(1/31)|_7 |_7
    = | (-16) * 5 |_7
    = | 5 * 5 |_7            since -16 = (-3)*7 + 5
    = 4

1 回答 1