Визначення та властивості відрахувань
Короткі відомості з теорії
Застосовуючи теорему про розподіл із залишком можна безліч цілих чисел розбити на ряд класів. Розглянемо приклад. Нехай m = 6. Тоді маємо шість класів розбиття множини цілих чисел по модулю 6:
де через r позначений залишок від ділення цілого числа на 6.
Нагадаємо теорему про розподіл із залишком:
Теорема. Розділити число на число. . із залишком, значить, знайти пару цілих чисел q і r. таких, що виконуються наступні умови:.
Легко доводиться, що для будь-яких цілих чисел а і розподіл із залишком можливо і числа q і r визначаються однозначно. У нашому прикладі повна система найменших невід'ємних лишків є безліч; повна система найменших позитивних відрахувань - безліч; повна система найменших по абсолютній величині відрахувань - безліч; наведена система відрахувань - безліч, так як; фактор-безліч
Один з методів виконання арифметичних операцій над даними цілими числами заснований на простих положеннях теорії чисел. Ідея цього методу полягає в тому, що цілі числа представляються в одній з непозиційних систем - в системі залишкових класів. А саме: замість операцій над цілими числами оперують із залишками від ділення цих чисел на заздалегідь обрані прості числа - модулі.
Найчастіше числа вибирають з безлічі простих чисел.
Так як в кільці цілих чисел має місце теорема про розподіл із залишком, т. Е. Де. то кільце Z. за визначенням, є евклідовим.
Таким чином, в якості чисел можна вибрати залишки від ділення числа А на рi відповідно.
Система відрахувань дозволяє здійснювати арифметичні операції над кінцевим набором чисел, не виходячи за його межі. Повна система лишків за модулем n # 8213; будь-який набір з n попарно непорівнянних по модулю n цілих чисел. Зазвичай в якості повної системи лишків за модулем n беруться найменші невід'ємні відрахування
Числа а також називають відрахування по модулюm. НеотріцательниеВИЧЕТи а = r (при q = 0), що приймають значення з інтервалу [0, 1. m - 1]. утворюють повну систему найменших відрахувань по модулюm.
Наприклад, при m = 5 класи найменших відрахувань утворюють
r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Обидві наведені сукупності чисел утворюють повні системи відрахування ів по модулю 5.
Клас вирахуванням. елементи якого взаємно прості з модулем m
називають наведеним. Функція Ейлера визначає скільки вирахуванням з повної системи найменших відрахувань по модулюm взаємно прості з m. При простому m = p маємо = p-1.
Визначення. Максимальний набір попарно непорівнянних по модулю m чисел, взаємно простих з m. називається наведеної системою лишків за модулем m. Будь-яка наведена система відрахувань по модулю m містить елементів, де - функція Ейлера.
Визначення. Будь-яке число з класу еквівалентності є m будемо називати відрахування му по модулю m. Сукупність відрахування ів, взятих по одному з кожного класу еквівалентності є m. називається повною системою відрахування ів по модулю m (у повній системі вирахування ів, таким чином, всього m штук чисел). Безпосередньо самі залишки при діленні на m називаються найменшими невід'ємними відрахування ами і, звичайно, утворюють повну систему відрахування ів по модулю m. Відрахування r називається абсолютно найменшим, якщо ïrï найменший серед модулів відрахування ів даного класу.
Приклад. Перевірити, чи утворюють числа 13, 8, - 3, 10, 35, 60 повну систему відрахувань по модулю m = 6.
Рішення. За визначенням числа утворюють повну систему відрахувань по модулю m. якщо їх рівно m і вони попарно непорівнянні по модулюm.
Попарно непорівнянність можна перевірити, замінивши кожне число найменшим невід'ємним вирахуванням; якщо повторень не буде, то це повна система відрахувань.
Застосуємо теорему про розподіл із залишком: a = mq + r.
13 = 6 2 + 1 13 1 (mod 6); 8 = 6 1 + 2 8 2 (mod 6);
-3 = 6 (-1) + 3 -3 3 (mod 6); 10 = 6 1 +4 10 4 (mod 6);
35 = 6 5 + 5 35 5 (mod 6); 60 = 6 10 + 0 60 0 (mod 6).
Отримали послідовність чисел: 1, 2, 3, 4, 5, 0, їх рівно 6, повторень немає і вони попарно непорівнянні. Тобто, вони утворюють повну систему відрахувань по модулю m = 6.
Приклад. Замінити найменшим за абсолютною величиною, а також найменшим позитивним вирахуванням 185 по модулю 16.
Рішення. Застосуємо теорему про розподіл із залишком:
185 = 16 11 + 9 185 9 (mod 16).
Приклад. Перевірити, чи утворюють числа (13, -13, 29, -9) наведену систему відрахувань по модулю m = 10.
Рішення: Будь-яка наведена система відрахувань по модулю m містить елементів, де - функція Ейлера. У нашому випадку = 4, бо серед натуральних чисел тільки 1, 3, 7, 9 взаємно прості з 10 і не перевершують його. Тобто, можливо, що ці чотири числа складають шукану систему. Перевіримо ці числа на їх попарно непорівнянність:
13 = 10 1 +3; 13 3 (mod 10); - 13 = 10 (- 2) + 7; -13 7 (mod 10);
29 = 10 2 + 9; 29 9 (mod 10); - 9 = 10 (- 1) + 1; - 9 1 (mod 10).
Всі числа попарно непорівнянні, серед них немає повторень, їх рівно 4 і вони не перевершують модуль. Отже, вони утворюють наведену систему відрахувань.
Приклад. Перевірити, чи утворюють числа (-349, -193, 231, 401) наведену систему відрахувань по модулю m = 12.
Рішення: В нашому випадку = 4, бо серед натуральних чисел тільки 1, 3, 7, 9 взаємно прості з 10 і не перевершують його. Тобто, можливо, що ці чотири числа складають шукану систему. Перевіримо ці числа на їх попарно непорівнянність:
-349 = 12 (-30) + 11; -349 11 (mod 12);
- 193 = 12 (-17) + 11; -193 11 (mod 12);
231 = 12 19 + 3; 231 3 (mod 12);
401 = 12 33 + 5; 401 5 (mod 12).
Серед чисел є повторення, маємо два порівнянних числа -349 і -193. Отже, числа не утворюють наведену систему відрахувань.
Завдання 1. Замінити число а найменшим за абсолютною величиною, а також найменшим позитивним вирахуванням по модулю m.
Варіант 1. a = 185, m = 12; Варіант 2. a = 84, m = 9;
Варіант 3. a = 180, m = 10; Варіант 4. a = 82, m = 9;
Варіант 5. a = 85, m = 11; Варіант 6. a = 84, m = 8;
Варіант 7. a = 103, m = 87; Варіант 8. a = 84, m = 16;
Варіант 9. a = 15, m = 10; Варіант 10. a = 81, m = 9;
Варіант 11. a = 85, m = 15; Варіант 12. a = 74, m = 13;
Варіант 13. a = 185, m = 16; Варіант 14. a = 14, m = 9;
Варіант 15. a = 100, m = 11; Варіант 16. a = 484, m = 15;
Варіант 17. a = 153, m = 61; Варіант 18. a = 217, m = 19;
Варіант 19. a = 625, m = 25; Варіант 20. a = 624, m = 25;
Завдання 3. Записати повну і наведену систему найменших