How to Convert from a Residual Number System to a

Question

I understand the concept of a Residual Number System and the concept of a Mixed Radix system, but I'm having difficulty getting any of the conversion methods I find to work in a simple case study.

I started at Knuth's Art of Computer Programming but that had a bit too much on the theory of the conversion, and once Euler was mentioned I was lost. Wikipedia has a nice section on the subject, which I tried here and here but both times I couldn't get back to the number where I started.

I found a good article here (PDF), which I condensed the relevant sections here, but I don't understand the multiplicative inverses and their notation. Specifically, how y_2 = |(3 - 19)|(1/31)|_7|_7 = |5 * 5|_7 Especially how |1/31|_7 = 5

Answer 1

The multiplicative inverses are to be taken with respect to a modulus (here 7). Since the modulus 7 is prime, every number (modulo 7) has an inverse. In particular, 31_7 = 3_7 (since 31 = 4*7 +3 - sorry if I'm too didactic), and its inverse is 5 because 3 * 5 = 15 = 1_7. So we can write |1/31|_7 = 5.

Now

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