воспользоваться представлением числа в виде (6.1), то имеет место очевидная теорема.

Теорема 6.8. При любом расширении системы модулей с помощью модулей p„+i, /»„+2.--. Рп+н ЩфрЫ Ь, b„i,..., „+fe i, в представлении (6.1) для чисел из М будут равны нулю.

Доказательство. Справедливость теоремы вытекает из того, что

KPi-Pz- - •Р2---Р„ + K+iPiPi---Pn+i + - + t>n+k-i X XPi-Pi- -rPn+H-i - O,

так как по условию л <PiP2* •••

Простой способ расширения основан на соотношении (6.3). цС учетом результата теоремы 6.8 можно переписать это соотношение в следующем виде

Но тогда из (6.1) получаем

%+1-\п+1)Л+--+К+1)(п-1уК-1 (6.4)

hn+f)l<Pn+f

Расчет по формулам (6.4) требует 2п тактов работы машины для определения Ь/ и еще двух тактов работы для вычисления Ь„ в разряде р j. Таким образом, при расширении системы модулей на k модулей требуется 2 (« + й) тактов работы машины.

Пример 6.10. Для системы модулей {2, 3, 5, 7, 11} код в остатках числа X имеет вид {х) = 10259. К системе модулей добавляется модуль, равный 13. Найти код в остатках для числа х в новой системе модулей.

По формулам (6.3) получаем. &о = 1> = 1. &2 = 4> = 3, &4 =2. Так как 65 = О, то из (6.3)

35 = - Ю&о - 7&1 - Щ - 8Ьз-7Й4 (mod 13)

bs = K + 2bi + 6&g + .4&з + 2&4 (mod 13).

Это выражение есть запись в виде соотношения (6.4). Отсюда &5 = 4. Окончательно {х) = 102594.

♦

Задачи

1. Для системы модулей = 7, = 11, = 2 определить знак числа х, если (л) = 340.

2. Перевести число <х) = 0501 из системы, модулей {2, 7, 11,13} в десятичную запись с помощью перехода к представлению (6.1).

3. Перевести число <х) = 1116 из системы модулей {2, 3, t6, 7} в десятичную запись с помощью векторного представления.

§ 6.3. Выполнение операций в коде в остатках"

Код в остатках позволяет весьма просто осуществлять операцию сложения и умножения положительных чисел. Пусть чисйа хну принадлежат некоторому множеству относительно системы модулей pi, Р2, - , Рд. Предположим, что этому же множеству принадлежат х + уи ху. Не теряя общности, можно предположить, что множество AIj является множеством главных элементов. Код в остатках для -X Vi. у имеет вид *:

-(x) = rest-; rest - ;...; rest-""

Pi P2 Pg.

(j;) = rest -; rest-;...; rest-=.

Pt Pz Pg

Эта запись эквивалентна следующим двум системам сравнений

XSSrest -(тойpi); a; = rest -(mod/jj);... ;.х: =

Pi . Р2

= rest -(mod р),

• Pg

у = rest - (modр); у es rest - (modP2);...; y pi .P2

= rest - (mod p„). Pg

Ha основании теоремы 6.1 сравнения, записанные в одном столбике, можно почленно складывать и перемножать. Тогда

• jc 4-= rest+ rest - (modPi);...; x Ч- Pt Pt

= rest -+ rest - (modрЛ, . Pq Pq

xy = rest--rest (modpi)\...; xy =

.Pi Pi .

= rest • rest ~ (mod рЛ.

Fg . Pq .

* Здесь {x) означает,. как и раньше, код в остатках числа х.

. 19* 291

Но это означает, что

(x4-j> = rest

...; rest

rest - + rest - Pi Pi

(xy) = -rest

rest --rest - Pi Pi

;...; rest

X у rest --rest -

РЗ

Отсюда вытекает следующее правило для нахождения суммы и произведения двух положительных чисел Б системе остаточных классов (коде в остатках). Для нахождения суммы двух положительных чисел в коде ► в остатках достаточно произвести поразрядное суммирование и в каждом разряде найти остаток от деления полученной суммы на модуль этого разряда. АнЕлогично для нахождения произведения двух положительных чисел в коде в остатках достаточно произвести поразрядное умножение и в каждом разряде найти остаток от деления полученного произведения на модуль этого разряда.

Пример 6.11. В системе модулей {2, 3, 5, 9} найти сумму и произведение чисел {х\=?\4 и (j)io = 9.

Коды в остаткахдля данных чисел имеют вид (x) = 0240 и (;;) = 1042.

0 2 4 0 10 4 2

12 8 2

X

О 2 4 О 10 4 2 0 0 1 6 0.

Для получения истинного кода в остатках делим Б каждом разряде полученный результат на модуль данного разряда. Окончательно получаем {x-ify) = = 1232 и (XV) = 0010.

Пример 6.12. Считая, что произведено разбиение множества М на множества М и М", найти сумму и