ДействіяМодуліЦіфри ОПСA1310800 - 111111 0297-1-1 6710229 11113218 - 11111 01012207 67414 88-6-4 - 8888 00-145 3104 0-113 - 000 0-113 349 1 310
Цифри на підставах та знаходимо з співвідношень:
Звідки отримуємо і.
Таким чином, число в системі підстав,,,, і.
Сформулюємо важливу теорему про поділ без залишку, яка буде відігравати значну роль у подальшому.
Теорема 1.
(2.4)
для всіх модулів тоді і тільки тоді, коли a ділиться на b (без залишку) і.
Проілюструємо поділ без залишку на прикладі.
Приклад. Нехай підстави системи,,,, обсяг діапазону. Розділимо число на число.
Обчислюємо зворотні елементи по множенню:
Будемо тепер ділити число A на модуль або твір першого ступенів модулів СОК. Цей поділ грунтується на теоремі про розподіл із залишком.
Теорема 2. Для будь-яких двох цілих чисел A і B завжди можливо причому єдиним чином поділ із залишком, т.е.
(2.5)
де A - ділене; B - дільник;- Неповне приватне;- Залишок. З (2.5)
де величини - цілі числа.
Якщо дільник B є модуль або твір перших ступенів модулів, то неважко знайти.
Тоді по теоремі 1 для всіх i, для яких отримуємо
(2.6)
За формулою (2.6) можна обчислити всі СОК цифри, для яких. Цифри по решті модулям можуть бути визначені за допомогою розширення системи підстав. Таким чином, алгоритм розподілу на модуль СОК, або твір першого ступенів модулів СОК, складається з двох операцій, а саме, ділення без залишку і розширення системи підстав.
Розглянемо приклад, який ілюструє наведений алгоритм.
Приклад 1. Нехай підстави системи,,,, обсяг діапазону. Розділимо число на число. Спершу знайдемо число, яке ділиться на 61, воно одно, так як, то. Це число ділиться на. Виключаючи модуль, який сам є дільником, всі модулі взаємно прості з дільником. Тому, поділ без залишку може бути застосоване для знаходження чисел приватного, крім цифри по модулю. Множачи, отримаємо
Враховуючи, що обсяг діапазону, то ми працюємо з числами з інтервалу. Так як A розташоване в цьому інтервалі, то повинно бути в інтервалі. Так як модулі,,, дають інтервал розширень, то СОК уявлення
єдино. Цифра по модулю, може бути знайдена за допомогою алгоритму розширення діапазону. Застосуємо метод розширення системи основ за допомогою ОПВ, записуючи замість відсутньої СОК цифри по модулю. Подальші обчислення наведені в таблиці.
Таблиця 2.2
ДействіяМодуліЦіфри ОПС 15740 - 11111 0463-1 671 031 231 130 - 2222 01928 6750 66-3 - 666 00-9 347 04 - 00 04 45 - 3
Якщо позначити, то отримаємо:
звідки. Отже,
Приклад 2. Нехай підстави системи,,,, обсяг діапазону. Розділимо число
на число.
Позначимо результат.
Рішення прикладу наведемо в таблиці. візьмемо з попереднього прикладу.
Таблиця 2.3
ДействіяМодулі 1574- - 1555 002-1- 1-67- 0-1212-
Записуємо в бракуючі стовпці для розширення підстав.
Таблиця 2.4
ДействіяМодуліЦіфри ОПС 0012120 - 00000 0012120 671031 0660 - 6666 50055 6347 8023 - 000 8023 745 1-2
Цифри на підставах та знаходимо з співвідношень:
і
Звідки і. Отже,
З прикладів 1 і 2 випливає, що вони містять не більше n складань і таке ж число множень. Крім того, в кінці алгоритму необхідно вирішити рівняння для Z. Важливо зауважити, що число операцій не залежить від того, чи є дільником один модуль або твір модулів. Спочатку ми помітили, що дільник повинен складатися тільки з n перших ступенів модулів. Якщо, де, то не містить інформацію, необхідну для визначення. Отже, не може бути визначене безпосередньо. Операцію ділення на ступінь модуля можна здійснити тільки через повторення операції ділення.
Можна відзначити два важливих недоліку розглянутого алгоритму: округлення результату завжди відбувається з недоліком, і цей алгоритм застосуємо тільки для позитивних чисел. Перший недолік можна усунути: якщо при діленні числа на підставу залишок то в якості найближчого цілого числа, що ділиться на слід вибирати; якщо ж то в якості найближчого цілого числа, що ділиться на остачі, слід вибрати
.
При розподілі числа на одне або декілька підстав системи залишкових класів фактично всі цифри приватного, крім цифр з підстав, на які здійснюється поділ, визначаються за допомогою формального розподілу цифр діленого на відповідні цифри дільника. Для решти ж цифр виникає невизначена ситуація. Один із способів розкриття цієї невизначеності за допомогою операції розширення системи підстав проаналізований вище.
Розглянемо операцію масштабування в системі залишкових ...
