Математические основы системы остаточных классов (стр. 14 из 19)

, (3.14´)

в котором находится число

и по цифре числа в СОК по модулю , т.е.

. (3.15´)

Так как (

, ) = 1, то по теореме Эйлера:

, (3.16´)

где

– функция Эйлера. Причём если – простое число, то = –1. Подставляя (3.15´) в (3.4´), учитывая (3.1´) и (3.4´) число можно записать в виде

. (3.17´)

Для определения номера интервала

подставим (3.17´) в (3.14´):

. (3.18´)

Учитывая, что

перепишем (3.18´) в виде

. (3.19´)

Так как

является делителем чисел то

где

и –

постоянные коэффициенты, определённые системой оснований.

Таким образом,

. (3.20´)

Подставляя (3.20´) в (3.15´), получим позиционное представление числа

. (3.21´)

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

наибольшие модули системы, представляющие числа Мерсенна или Ферма . При этом предпочтение отдаётся числам Мерсенна, так как арифметика по этим модулям проще.

Проиллюстрируем рассмотренный метод на примере.

Пример. Пусть дана система оснований

тогда = 210. Пусть надо перевести число =(0,1,4,3). В качестве дробирующего модуля выберем тогда , номер интервала

, а само число . Определим Так как

то

Тогда

Таким образом,

13·7 + 3 = 94.

На основе этой же характеристики числа – номера интервала, с применением теоремы Эйлера предлагается алгоритм перевода числа в ПСС. Разность между модулями можно представить в виде

= – и тогда

, (3.22´)

но с другой стороны

( ). (3.23´)

Из (3.22´) и (3.23´) следует, что

Так как

. (3.24´)

Решение сравнения (3.24´) можно записать в виде

(3.25´)

где

– функция Эйлера. Если – простое число, то Поэтому в случае простого выражение (2.3.13) примет вид:

Перепишем (3.15´) с учётом (3.25´)

(3.26´)

где

– константа, определяемая выбором оснований СОК. Нетрудно заметить, что – наименьший неотрицательный вычет по составному модулю · . Исходя из этого можно записать:

(3.27´)

где

показывает, сколько раз произведение · укладывается в числе . Для нахождения можно считать, что число представлено в системе оснований в виде и после этого можно воспользоваться формулой (3.27´). Проводя аналогичные рассуждения, после преобразований получим:

(3.28´)

Где

(3.29´)

Тогда искомая величина числа

( – наименьший неотрицательный вычет числа по составному модулю ) определяется за – 1 шагов, где – число оснований СОК.