Индексы и их свойства (Дискретный код)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 08:31, 12 мая 2016.

Определение индекса

первообразный корень.


Рассмотрим множества

- порядок первообразного корня.

Если (т.е. - мультипликативная группа), то всегда

TemplateDifinitionIcon.svg Определение «Индекс числа»
Индексом числа a по модулю p при основании g называется целое неотрицательное число и обозначается

Таким образом индексов может быть много, но в пределах по модулю p существует единственный.

Для индексов справедливо

1. Если степени сравнимы

2. Для (аналогично свойству логарифмов)

3. Если числа сравнимы между собой по модулю p, то:

Свойства индексов

TemplateTheoremIcon.svg Теорема Свойство 1
Доказательство

По свойству сравнимости перемножим их:

Если два числа сравнимы, то переходя к индексам


TemplateTheoremIcon.svg Теорема Свойство 1'(другой способ)
Доказательство


Ранее создавались таблицы индексов. Остроградский М.В. в 1837 году построил таблицу индексов до . К.Якоби построил таблицу индексов для простых чисел до

TemplateExampleIcon.svg Пример Пример 1(применение индексов к решению сравнений)
Рассмотрим сравнение . Частный случай - , - простое. Если сравнимы по простому модулю , индексы тоже сравнимы по . Таким образом

.

Пользуясь таблицей индексов знаем индексы и , получаем сравнение первой степени . Знаем вид/количество решений и т.д.

Находим . Если , то решение единственное. Если , то либо решений , либо решений нет при .

Упрощаем. Если


TemplateExampleIcon.svg Пример Пример 2(Критерий разрешимости сравнения)

критерий Эйлера

Если числа сравнимы, сравнимы и их индексы:

переходим к сравнению по модулю простого( по свойству):

- условие разрешимости сравнения

Если

если -простое большое, то -четное. Тогда перепишем