Арифметичні застосування теорії конгруенцій (стр. 5 из 6)

Його можна подати так:

Звідси виводимо таке правило: щоб перетворити мішаний періодичний дріб у звичайний, треба від числа, що стоїть між комою і другим періодом (тобто від числа

), відняти число, яке стоїть між комою і першим періодом (тобто число ), і цю різницю зробити чисельником; у знаменнику треба написати стільки дев'яток, скільки цифр у періоді, й після них - стільки нулів, скільки цифр між комою й першим періодом, і цей дріб додати до цілої частини N.

Зауваження. Можна відразу перетворити періодичний дріб у звичайний неправильний дріб (не виділяючи цілої частини). Для цього треба цифри цілої частини вважати цифрами, що стоять до періоду, й застосувати правило для перетворення мішаного періодичного дробу в звичайний. При такій побудові знаменника цифри цілої частини враховувати не слід.

Приклад.

, або

.

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 - первісний корінь по модулю , а отже і по модулю .

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

	1	2	4	5	7	8	10	11	13	14	16	17	19	20	22	23	25	26
	0	11	4	1	14	15	12	17	16	7	8	3	6	5	10	13	2	9

Досить мати таблиці індексів по модулях

з основами g, що є непарними первісними коренями.