Модуль 2
Практичне заняття 6
Індекси за простим модулем.
Двочленні конгруенції за простим модулем.
Арифметичні застосування теорії конгруенцій
Основні теоретичні відомості
Порядок числа і класу лишків за модулем. Первісні корені,
існування їх та кількість за простим модулем
Нехай , і . Порядком числа а за модулем називається таке найменше натуральне число , що . Число позначають ще як і називають показником, до якого належить число за модулем . Оскільки за теоремою Ейлера , то число завжди існує і . Якщо , то число називають первісним коренем за модулем .
Якщо , то . Ця властивість дає змогу казати про порядок класу лишків, а саме: клас лишків має порядок за модулем . якщо порядок його представника за цим самим модулем дорівнює .
Якщо , то клас лишків називається класом первісних коренів за модулем .
Якщо , то числа попарно не конгруентні між собою за модулем .
Якщо — первісний корінь за модулем , тобто , то числа утворюють зведену систему лишків за модулем .
Якщо , то тоді і тільки тоді, коли . Зокрема, тоді і тільки тоді, коли .
Якщо і , то
Якщо , то .
Якщо , то .
Якщо , то .
Якщо - попарно взаємно прості числа, то . тоді і тільки тоді, коли .
Якщо , то класи лишків є різними розв'язками конгруенції .
Якщо — просте число, то зазначені класи лишків вичерпують усі розв'язки даної конгруенції.
За простим модулем кожен дільник числа є порядком для класів лишків. Зокрема, існує класів первісних коренів (теорема Гаусса).
Якщо первісний корінь за простим модулем , то інші первісні корені містяться серед степенів і мають вигляд , де і .
Якщо — канонічний розклад числа , то число тоді і тільки тоді є первісним коренем за простим модулем , коли
для всіх .
Первісні корені існують тільки за модулями ; і , де - просте непарне число, а .
Нехай —первісний корінь за простим модулем . Тоді можна знайти таке число , що число , яке визначається з умови
,
не ділиться на . Відповідне число є первісним коренем за модулем при будь-якому .
Нехай і — первісний корінь за модулем . Непарне з чисел і є також первісним коренем за модулем .
Якщо і - різні прості дільники числа , то число , взаємно просте з , тоді і тільки тоді є первісним коренем за модулем ; коли
для всіх .
Індекси за простим модулем. Двочленні конгруенції за простим модулем; таблиці індексів і застосування їх.
Нехай - первісний корінь за простим модулем , і . Ціле невід’ємне число називається індексом за модулем при основі , якщо
(1)
Взагалі, довільне значення , яке задовольняє конгруенцію
, (2)
називається індексом числа за модулем при основі і позначається
. (3)
При цьому може бути й складним числом , проте
.
Означення індексу можна записати ще так:
. (4)
Користуючись цим означенням, складають таблицю Індексів за даною основою і модулем. Таблиці індексів за кожним простим модулем (не дуже великим) містять дві таблиці: одна — знаходження індексу за числом, а друга — знаходження числа за індексом (таблиця анти індексів).
Основні властивості індексів
1°. Усі індекси числа за простим модулем утворюють клас чисел за модулем . Точніше, якщо і — індекси числа за модулем (при будь-якій тій самій основі), то
.
2°. Для того щоб , необхідно і достатньо, щоб
.
Якщо значення чисел або індексів виходять за межі таблиць, то ці дві властивості дають змогу переходити до найменших невід'ємних лишків: для чисел — за модулем , для індексів — за модулем ;
3°. ;
4°. ;
5°. ;
6°. ;
7°. Якщо , то .
Зазначимо, що перехід від конгруенції між числами до конгруенції їхніх індексів називається індексацією, а зворотний перехід –потенціюванням. Якщо задано двочленну конгруенцію
го степеня за простим модулем
, , (5)
то її розв'язок знаходять з конгруенції
(6)
Арифметичні застосування теорії конгруенцій
Теорія конгруенцій має ряд арифметичних застосувань. Основними з них є:
1) виведення ознак подільності;
2) обчислення остач при діленні;
3) перевірка результатів арифметичних дій;
4) визначення довжини періоду при перетворенні звичайного дробу в десятковий.
Нехай в -й системі числення число має вигляд
Позначимо через абсолютно найменші лишки числа за модулем , тобто , і . Тоді , де (ознака подільності Паскаля).
З конгруенції випливає, що при діленні на т числа і дають однакові остачі. Зокрема, число ділиться на тоді і тільки тоді, коли на ділиться . Покладаючи , , дістаємо конкретні ознаки подільності. З метою обчислення остач від ділення, крім ознаки Паскаля, використовують також теореми Ейлера і Ферма, властивості індексів тощо.
Якщо
(1)
де — многочлен від цілих чисел з цілими коефіцієнтами, то виконується конгруенція
(2)
де —будь-яке натуральне число, — остача від ділення на , . Конгруенція (2) є умова, необхідна для рівності (1), але не достатня. Інакше кажучи, якщо (2) не виконується, то не виконується й (1); якщо (2) виконується, наприклад, для або , то напевно помилки в обчисленнях (1) не виявлено. Так, виконуючи перевірку для , помилку не виявили, оскільки: 1) не було взято до уваги нуль у доданку або множнику; 2) в результаті цифри записані не в тому порядку; 3) неповні добутки перебувають не на своїх місцях; 4) взагалі, помилка становить число, кратне 9. Під час складних обчислень доцільно робити дві перевірки: одну за модулем 9, а другу — за модулем 11.
Нескоротний дріб виду , де , і , у скінчений
десятковий дріб не перетворюється.
Якщо — нескоротний дріб і , то цей дріб перетворюється у чистий періодичний десятковий дріб. При цьому число цифр у періоді дорівнює порядку числа 10 за модулем .
Якщо — нескоротний дріб і , де , то цей дріб перетворюється в мішаний періодичний десятковий дріб. При цьому число цифр у періоді дорівнює , де — більше з чисел і ; число цифр у періоді дорівнює порядку числа 10 за модулем .