5. Індекси. Загальні властивості

Загальновідомо, яке велике значення в різних розділах математики і особливо в обчислювальній практиці мають логарифми. У теорії чисел вводиться схожий з логарифмами апарат, який ми називатимемо індексами. Логарифмом b за основою а, як відомо, називається показник степеня а, рівний b. У теорії чисел аналогічно цьому розглядають показник степеня а, порівнянною з b по даному модулю m, і такий показник називають індексом b по модулю m і основою а.

Означення 1. Нехай (а,m) = l, (b,m) = 1; число s називається індексом b по модулю m і основою а, якщо

Таким чином, згідно з означенням:

. (1)

Якщо , то з слідує також , тобто індекс числа b є також індексом і всіх чисел з , і ми можемо таке число s називати індексом класу .

Означення 2. Нехай (а, m) =l, (b, m) = 1. s називається індексом класу пo модулю m і основою а, якщо по цьому модулю .

Приклади. Нехай модуль m =13, основа а = 2, тоді , тобто , і для будь-якого буде також , тобто , і в той же час, оскільки , маємо також .

Нехай модуль m = 21, основа а = 5. Тоді , , тобто по модулю 21 , . По цьому модулю не існує, оскільки не існує s такого, що .

Якщо як основу взяти число а, що не є первісним коренем по модулю m, то індекси будуть існувати не для всіх чисел, взаємно простих з модулем m.

Теорема 1. Нехай g-будь-який первісний корінь по модулю m. Для кожного числа b, взаємно простого з модулем m, існують індекси за основою g, тобто існують s такі, що

.

Безліч всіх таких індексів s для даного фіксованого b збігається з не від?ємними числами деякого класу по модулю .

Властивості:

1. Нехай g - первісний корінь по модулю m, (b,m) = 1; порівняння

(2)

має місце тоді і лише тоді, коли

. (3)

2. Нехай g - первісний корінь по модулю m

. Тоді

.

3. Нехай g - первісний корінь по модулю m,

. Тоді

(5)

4. Нехай g - первісний корінь по модулю m, (а,m) = l, ; тоді

. (6)

Означення 2. Якщо , , то під розумітимемо , тобто індекс будь-якого числа з класу пo модулю m.

5. Нехай g - первісний корінь по модулю ; тоді

.

Індекси по простому модулю.

Особливо велике значення має випадок, коли модуль - просте число. Оскільки, по будь-якому простому модулю р існують первісні корені, то, узявши за основу який-небудь з них, отримаємо систему індексів, в якій кожне число, що не ділиться на р, матиме свої індекси.

Індекси кожного такого числа згідно з теоремою 1 є невід?ємні числа деякого класу по модулю р-1, а теореми а теореми 2-5 дають наступні правила операцій з індексами по модулю р.:

якщо,

то , і, навпаки,

з виходить .

.

.

.

Скорочено тут скрізь опущений знак g, який вказує основу, яка передбачається однаковою в лівій і правою частинах. Всі індексовані числа передбачаються що діляться на р.

По простому модулю р для кожного числа існує безліч індексів, порівнянних по модулю р - 1, і як індекс можна брати будь-яке з них. Зазвичай зі всіх можливих значень індексів по даній основі беруть найменше; при такому виборі індексів вони мають значення менші ніж р - 1.

Таблиці індексів для простих модулів р містять індекси чисел від 1 до р - 1. Для кожного такого числа і всіх порівнянних з ним по модулю р в таблиці вказується індекс, який являє собою одне з чисел: 0,1., р - 1. У деяких таблицях як індекс одиниці вказується не 0, а р - 1. Таблиці індексів складалися багатьма авторами. У 1839 р. таблиці індексів для простих чисел, менших чим 1000, були опубліковані Якобі.

Індекси по складеному модулю.

Для складених модулів вигляду і , де р - просте число (р>2), існують первісні корені, і тому для будь-якого числа, взаємно простого з таким модулем, існують індекси.

Приклад. Скласти таблицю індексів по модулю 27 з основою g = 5.

Власні дільники числа рівні 1, 2,3. Оскільки незрівнянні з 1 по модулю 9, то 5 - первісний корінь по модулю , а отже і по модулю .

Отримуємо послідовно:

Досить мати таблиці індексів по модулях з основами g, що є непарними первісними коренями.

Теорема 2. Нехай g-непарний первісний корінь по модулю ; тоді кожен індекс числа а по модулю і основою g є індексом а по модулю і основою g. Теорема 3. При два числа вигляду і порівнянні по модулю тоді і тільки тоді, коли

і .

Теорема 4. При будь-яке непарне число порівнянне по модулю з одним і тільки одним числом з множини:

.

Означення 3. Індексом непарного числа а по модулю при називається пара чисел , де , така, що

.

Таку пару ( (u, v)) інколи записуватимемо також у вигляді ind a.

Приклад. Пара ( (0, 0)) є індексом 1 по будь-якому модулю . Дійсно: .

Означення 4. Дві пари: і - називаються порівнянними по подвійному модулю , якщо

.

Порівнянність пар: і - по подвійному модулю записуватимемо у вигляді:

.

Очевидно, що дві пари, порівнянні по подвійному модулю з однією і тією ж третьою, порівнянні між собою.

Теорема 5. При тоді і тільки тоді, коли індекс а порівнянний з індексом b пo подвійному модулю .

Означення 5. Сумою індексів називається індекс .

Теорема 6. При для модуля індекс добутку непарних чисел порівнянний з сумою індексів співмножників по подвійному модулю . Індекси можна застосовувати для обчислення залишків від ділення на заданий модуль добуток з двома або декількома співмножниками і, зокрема, степенів.

Маючи таблицю індексів по модулю , щоб знайти остачу від ділення на , де всі взаємно прості з , ми шукану остачу позначаємо через і записуємо

.

Індексуючи попереднє рівняння отримуємо:

.

Знаходимо в таблиці індексів , так що

,

Звідси

.

В частинному випадку, якщо , ми отримуємо прийом для обчислення остачі від ділення на модуль степеня .

Приклад. Користуючись таблицею індексів, знайти остачу від ділення на 61 числа .

.

У таблицях по модулю 61 з підставою g=59 або g=-2 знаходимо і , так що

.

За значенням індексу знаходимо х. Число 24 є індексом 20, так що .

Якщо , то для знаходження остачі від ділення на добутку або степеня знаходимо остачі при діленні на модулі потім розв?язуємо систему рівнянь:

При , остача від ділення на знаходимо іншими методами (без вживання теорії індексів) або розглядаємо індекси по модулю .

При ми можемо представити у вигляді і знаходимо за допомогою індексів остачі від ділення на .

Приклад. Знайти остачу від ділення на 1242 числа .

Знаходимо остачу від ділення по модулю 27 з основою знаходимо

.

так що

.

По модулю 27 знаходимо, що , так що

.

Знаходимо остачу від ділення на 23.

Розвязуючи систему , знаходимо . Остача рівна 127.