разность чисел <x)io==10 и <.>)io=-4 в системе модулей {2, 3. 5i 7, 1U.

Для данной системы модулей интервал представления чисел есть (- 1155, -f 1154). Коды чисел имеют вид (10) = О, 1, О, 3, 10, (~ 4)-(2310) = О, 2, 1, 3, 7, (4) = 0, 1,-4, 4, 4.

. . 0.1 О 3 10 . О 1 О 3 10

" 0 2 1 3 7 О 1 4 4 4

О 3 1 6 17 О 2 4 7 14

После деления на модули соответствующих разрядов получаем {х-у) = 001С6 и {х-\-у)== 02403.

• Переходя к представлению 6.1, можно проверить, что первый код соответствует коду десятичного числа 6 в данной системе модулей, а второй код соответствует коду десятичногр числа 14 в данной системе модулей.

Отметим, что результаты вычислений будут верны только в том случае, когда при сложении или при умножений не происходит переполнения, т. е. когда результат операции еще не выходит за пределы произведения модулей.

В вычислительных машинах, работающих в коде в остатках, можно избежать операции умножения, заменив эту операцию суммированием специальных индексов, однозначно связанных с данным кодом в остатках. Дадим описание индексной арифметики, введя для этого некоторые дополнительные понятия из теории сравнений.

Рассмотрим некоторое число а, взаимно простое с модулем р,

и будем образовывать степени а, а,..., а", Так как несравни;?

мых между собой по модулю и не-делящихся на р чисел не может быть более/? -1,-то среди степеней а всегда найдутся какие-то степени, сравнимые между собой по модулю р. Пусть первое такое сравнение произошло для степеней / и /и, т. е. й" (mod р).

Преобразуем это сравнение в сравнение а~ 1 (modр). Обозначая 1 - т через k, получим сравнение я*=1 (mod/?). Любой показатель степени л разделим на k и, полагая п = qk + г, где О </<*, получим = = я (mod р). Таким образом, среди

Первых Астепеней числа «нет сравнимых между собой по модулю р, « начиная с показателя /г == 1,-начинается периодическое повг

торение а а (modр), а а (mod р),..., «2* = 1 (modр). В частности, я" s 1 только тогда, когда л = qk. Но по теореме 6.5 а sl(modip) и» :еледовател?,н6, чР.сгг Vp=eft. так. что длина

периода есть делитель числа р ~ I. Если ft-/;-1 для данного числа а и данного модуля р, то -число а называется первообразным корнем простого числа р. Так как числа а, а,..., а~ образуют множество Mk> то можно строить все операции над кодами в остатках, цифры в которых берутся из множества

[а, а,..., с~}. При этом упрощается производство операций, умножения, возвышения в степень, деления и извлечения корня, так как соответствующие операции заменяются суммированием, умножением, вычитанием и делением показателей степени.

Можно построить таблицы, с помощью которых для - данного модуля р и выбранного первообразного корня * а находить для - каждого остаточного класса по модулю р, заданного своим пред-

ставителем rest ~ - If- соответствующий показатель степени г,

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

что и rest -. Другими словами, у я (mod в). Это число г, опре-Р

деленное по модулю р~\ (т, е. с точностью до кратного

р - 1), называется индексом числа rest - при основании а по

юдулю р и обозначается следующим образом indr- Иногда там, где это не приводит к неясностям, индекс числа t обозначают просто как indY-

На основании определения индексов легко выводятся следую-1цие соотношения. При f = а (mod р) и 6 = а* (mod р) имеем

ind (т6) = ind т + ind 8 (mod (/7 - 1)); ind (т; 6) = ind 1 ~-ind 6 (mod (1)); ind (f"") = 6 ind Y (mod ( p -- 1)).

Bee соотношения доказываются одинаково. Докажем, например первое соотношение. Для этого перемножаем почленно два сравнения Y = (mod р) и В S я* (mod р). Полагая, -ficf (mod р), находим, что ef = я*"*"* (mod р). Но это возможно лишь при условии, что tr -i-s + п(р - 1) или =зг + s(mod (р -1)). что соответствует написанному в первой формуле соотношению между индексами.

Для перехода от одного основания индексов я к другому основанию b достаточно заметить, что при b = я* (mod р) и с = Ь (mod р), са (mod р), получаем я* я* (mod р). Отсюда л- = йг (mod(p.-1)) или ШаСщШаЬ-ШьС (mod(p -1)).

Для нахождения индексов по данному числу из Л1 и обратной лперацин обычно используют специальные таблицы. Для чисел р от 3 до 13 эти таблицы выглядят следующим образом:

* Можно доказать, что для любого простого модуля р существует по крайней мере один первообразный корень.

р==7

Эти таблицы устроены следующим образом. Левая служит дли перехода от числа к его индексу, а правая -- для обратного перехода от индекса к числу. Цифры над столбиками означают цифры, стоящие в разрядах .единиц, а цифры слева от строк -цифры, стоящие в -разрядах десятков.

Условимся считать, что цифре О соответствует специальный индекс X, который обладает свойством Х + /=./-+>,=Х для любого индекса