Как преобразовать из системы остаточного числа в смешанную систему Radix?

Question

Я понимаю концепцию Residual Number System и концепцию Mixed Radix system, но мне трудно получить какие-либо методы преобразования, которые я нахожу для работы в простом примере.

Я начал с искусства программирования Кнута, но это слишком сильно повлияло на теорию преобразования, и как только Эйлер упоминался, я был потерян. В Википедии есть nice section по этому вопросу, в котором я пробовал here и here, но оба раза я не мог вернуться к тому, с чего я начал.

Я нашел хорошую статью here (PDF), которую я сгустил в соответствующих разделах here, но я не понимаю мультипликативные обратные и их обозначения. В частности, как y_2 = | (3 - 19) | (1/31) | _7 | _7 = | 5 * 5 | _7 Особенно, как | 1/31 | _7 = 5

Answer 1

Мультипликативные обратные должны быть взяты с относительно модуля (здесь 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