більший загальний дільник чисел знаходиться за допомогою алгоритму Евкліда. Якщо в (1.2) і (1.3) число р - фіксоване, то воно називається модулем. Тоді для нескінченного числа варіантів вибору можна отримати один і той же залишок. У таких випадках кажуть, що всі ці числа А порівнянні за модулем р. Всі цілі числа А, дають при діленні на р один і той же залишок, утворюють клас відрахувань по модулю р.
Приклад. Якщо, то,, дають один і той же решту, бо 17, 22, 32 порівняні по модулю 5. Для заданого модуля р мається р таких класів, по одному на кожен можливий залишок, який може дорівнювати 0, 1, 2,...,.
Класом з даного модуля р називається безліч всіх чисел, порівнянних з деякими даними цілим числом А.
Число класів по модулю р звичайно і одно р.
Класами, взаємно простими з модулем, називаються класи, у яких найбільший дільник дорівнює 1.
Наведеної системою вирахувань по деякому модулю є система чисел, узятих по одному з кожного класу, взаємно простого з модулем.
Кількість класів, взаємно простих з модулем р, дорівнює числу цілих чисел, що не перевершують р і взаємно простих з р. Число таких класів залежить від величини модуля і є функцією модуля. Цю функцію зазвичай називають функцією Ейлера і позначають через.
Функцією Ейлера називається число натуральних чисел, що не перевершують р і взаємно простих з р.
Розглянемо деякі властивості цієї функції, які в подальшому будуть відігравати важливу роль.
Приклад.. Щоб визначити функцію Ейлера, необхідно виписати натуральні числа від 1 до 24 і викреслити числа, які мають не рівні одиниці загальні дільники з 24, т. Е. Числа, що діляться на 2 і на 3. Решта числа (1, 5, 7, 11, 13, 17, 19, 23) утворюють наведену систему відрахувань по модулю 24; дорівнює числу цих чисел, т.е.
.
Функція Ейлера - мультиплікативна, т. е.
при. (1.7)
Приклад. ,,,,,.
Два цілих числа і, що мають однакові залишки при діленні на р, називаються порівнянними за модулем р.
Відносини порівнянності позначають наступним чином:
. (1.8)
Вираз (1.8) еквівалентно висловом.
Якщо, то.
Співвідношення порівнянності в чому схоже з рівністю, проте воно менш сильне в тому сенсі, що рівні величини можна порівняти, а порівнянні не обов'язково рівні.
З точки зору порівнянності чисел ми використовуємо тільки залишок, що утворився при розподілі числа А на число р. Очевидно, що
. (1.9)
Операція взяття вирахування визначається правилом
. (1.10)
Звідси видно, що для визначення найменшого неотрицательного вирахування від числа А необхідно з цього числа відняти число, найближче до А, яке менше А і кратно р. Повну систему представників у цьому випадку будемо називати системою найменших невід'ємних відрахувань по mod p і позначати символом
При виконанні обчислень завжди можна замінити порівняння, яке встановлює зв'язок між цілими класами чисел з одним і тим же вирахуванням, рівністю, що включає цей відрахування.
Наприклад, якщо
(1.11)
(1.12)
Обчислення з відрахуваннями зазвичай досить прості, оскільки не мають справи з числами, більшими, ніж модуль. Очевидно, що
(1.13)
Тож за всіх обчисленнях зі знаками,, можна результат обчислень на кожному кроці замінювати його вирахуванням.
Припустимо, що, де; тоді кожен елемент А з єдиним чином представлений у вигляді
(1.14)
.
Лінійна форма (1.14) при всіх можливих приймає значення з діапазону, так як.
Різним наборам констант, де, відповідають різні значення лінійної форми (1.14).
Якщо в (1.14) покласти, то отримаємо р-адических (позиційний) код. При невиконанні цієї умови код називається поліадіческіх (позиційним).
Машинна арифметика відрахувань по, виражена на мові поліадичного коду, через великі складнощів при реалізації операцій множення поступається р-адических машинної арифметики.
Як буде показано нижче, поліадіческіх система числення широко застосовується при визначенні позиційних характеристик непозиційних коду.
Якщо модулі - попарно взаємно прості, то можлива нова, відмінна від позиційної, машинна арифметика відрахувань по, яка породжує непозиційних код. Перевагою непозиционной арифметики є повне розпаралелювання операцій.
Представлення чисел в СОК забезпечується найменшими невід'ємними відрахуваннями за системою взаємно простих модулів:
(1.15)
Таке уявлення дозволяє виконувати операції з великою швидкістю внаслідок відсутності переносів від цифри до цифри.
Додавання, віднімання і множення двох чисел А і В може бути виконане за допомогою додавання, віднімання або множен...
