взаимно простых модулей, каждое число л из Ж записывается в следующей форме, обобщающей запись вида (1.1)

п j=0

-Ь ... + [(аД . р,-Ь [(а,.)]о. (6.1)

Дя простоты символы [(aj)]i будем записывать как bi. Тогда соотношение (6.1) принимает вид

xb„Pi-p2...p„ + b„ i-pi-p2... • p„ i + ... il - Pi -Ь

Теорема 6.6. Если х принадлежит к множеству М, определяемому данной системой модулей, то х -однозначно представимо в виде (6.1).

Доказательство. Докажем сначала возможность представления любого л; из Ж в виде соотношения (6.1). Доказательство будем вести по индукции. Для систем из одного модуля справедливость утверждения очевидна. Для системы из двух модулей pi и р, причем P\<iPi, справедливость утверждения вытекает из следующего. Для х возможны три взаимно исключающиеся случая х<р, x = Pi и Pi<x<p-p2. В первом случае х = 0-р +bo, mebo = x. Во втором случае х=[ р + 0. В третьем случае из того, что

Pi<x<pipi, вытекает -=--Ь где io<A и

Pi Pi

К < Р2- Отсюда л = • />, -Ь V Теперь докажем справедливость для случая трех модулей Pi, р, Рз- Пусть PiPi Ръ- Для X имеется три взаимно исключающих случая х<рр2, x=piP2 и PiP2<x<PiP2Pz- В первом случае по доказанному выше л; = O-Pi* Р2+ lA+o-Во втором случае х=1-pi-Р2 + 0-pi + 0. В третьем случае из того, что PiP2<x<pi-Р2-Рз, вытекает

~- = 2 Ч--~ • При этом" Ь2<РзЬ <Pi- Р2. Следо-

PiPi Pi-Pi

вательно, л = • Рг Рг + Но так как b<CPiP2, то = *1 • Pi + V Отсюда x = b2-Pi- Р2 + bi-Pi + bg, причем &o<Pl. *Г<Р2. *2<Рз-

Теперь уже нетрудно сделать последний индуктивный шаг, предположив справедливость утверждения теоремы верным для k модулей и доказав справедливость ее для (k + 1)-го модуля. Этот шаг предостав-

ляется сделать читателю самостоятельно в качестве упражнения.

Заметим, что одновременно с доказательством возможности представления в виде (6.1) мы доказали, что при таком представлении всегда выполняется условие bi < />,.f.i для всех L

Доказательство единственности разложения в виде (6.1) предоставляется читателю.

Представление (6.1) может быть получено из кода в остатках с помощью следующего приема. Если соотношение (6.1) взять по ьюдулю р, то единствен-, ный член, оставшийся в правой части (6.1), будет равен о. Взятие равенства по модулю р эквивалентно делению с остатком обеих частей (6.1) на р с выде-

* лением остатков от деления и приравнивания остатков между собой. Отсюда вытекает, что Ь совпадает с цифрой кода в остатках, которая записана в разряде, соответствующем модулю /?,. Для получения 6, образуем разность х-Ьъ коде в остатках. После этого производим деление полученной разности на модуль

• Pi. Тогда . • .

- = КР2Ръ- -Pn + n-lPPs -•Pn-i + Pi

Если это равенство взять по модулю Pz, то мы получим значение i&, и т.-д.

Пример 6.6. Дана система, модул ей Pi = 7, Р2 = 11. Рз = 13. Перевести число (х) = 435 из кода в остатках в представление в виде (6.1).

На основании вышеприведенного рассуждения Ь(,=4. Вычитаем из каждого разряда Исходного числа цифру 4 по модулю этого разряда. Полученный после этого код имеет вид О, 10, 1. При вычитании по модулю р, <Гледует помнить, что число О эквивалентно Р;. Поэтому-1, получающаяся при вычитании 4 в разряде, сопоставляемом модулю 11, эквивалентна 10.

Берем обратную величину основания р,, = у .

Умножаем найденную разность на -~. Это умножение

происходит по модулю данного разряда с учетом, что 282 . . - . .

.: /», И О эквивалентны. Вместо - используем формаль-

* ную обратную величину из таблицы, приведенной в предыдущем параграфе. Как следует из этой таблицы, формальная обратная величина для 7 при /, = 11 есть 8, а при Pi = 13 есть 2. Поэтому код О, 10, 1 умножается на и на 2 в соответствующих разрядах. После умножения мы получаем код 032. На основании вышесказанного = 3. Производим вычитание 3 по модулям данного разряда. Полученный код есть О, О, 12. Для величины 11 формальная обратная величина для /7,-=13 есть 6. Умножаем полученные разряды кода на 6. Получаем код 007. Таким образом, = 7.

Итак, jc = 7-7-ll+3-7-b4 = 872.

Другой путь преобразования чисел из кода в- остатках в обычное представление заключается в следующем. Пусть мы имеем систему модулей {Р\, р., - ,P, Рассмотрим ортонормированную систему векторов

ai = (l, О, 0,...,0, 0) : а2 = (0, 1, 0,...0, 0) .

аз = (0. О, 1,...0, 0)

а„ = (0. О, О, ...О, 1). .

Тогда для любого числа х

jc = rest --«х-Ь rest--a2-b ....+ rest-.а„. (6.2)

Р\ Pi Рп

Будем рассматривать вышеприведенные вектора как коды в остатках некоторых чисел из М. Пусть десятичная запись этих чисел есть (a,)io,..., (a„)io. Тогда десятичная запись числа х получа-ется весьма просто

=.fest -(•a,)io + rest -(аг) -Ь ... +

Pi .Pi

• • +rest.(a„)j„.

Поскольку система модулей фиксирована, то не представляет особого труда заранее вычислить числа (a,)io и использовать их при получении десятичного значения x.