АРИФМЕТИКА. Теория делимости 6 страница

Лемма 13.31. Если число принадлежит показателю по модулю , то число принадлежит показателю по модулю .

Доказательство. Во-первых, . С другой стороны, если бы для некоторого , то, так как , то противоречило бы понятию показателя по модулю .

Лемма 13.32. Если принадлежит показателю , а принадлежит показателю по модулю и , то число принадлежит показателю .

Доказательство. С одной стороны,

.

Это говорит о том, что число может служить показателем данного произведения. С другой стороны, если является показателем указанного произведения модулю , то . Кроме того, имеем

.

Тогда по следствию из леммы 13.30 получим, что , но . Поэтому .

Аналогично,

.

Значит, , но , поэтому . И вновь в силу взаимной простоты и находим, что , т.е., . А тогда .

Теорема 13. 18. Существуют первообразные корни по простому модулю .

Доказательство. Пусть будут все различные показатели, которым принадлежат числа по модулю . Обозначим через – НОК указанных чисел. Пусть . Каждый множитель последнего разложения , , делит по крайней мере одно число , , которое, следовательно, можно представить в виде . Пусть будет одним из чисел ряда , принадлежащих показателю . Тогда число принадлежит показателю по лемме 13.31. А в соответствии с леммой 13.32 произведение принадлежит показателю . Отсюда заключаем, что число является делителем . Но поскольку все числа делят , то все числа ряда являются решениями сравнения . Поэтому по лемме 13.13 количество таких решений . Следовательно, и тогда – первообразный корень по модулю . Теорема доказана.

Теорема 13.19. Пусть – первообразный корень по модулю . Существует такое , что число , определяемое равенством , не делится на . Тогда будет первообразным корнем по модулю при любом .

Доказательство. Действительно, имеем

,

,

где, одновременно с , пробегает ПСВ по модулю . Поэтому можно указать с условием, что не делится на . При таком из последнего равенства выводим

,

,

. . . . . . . . . . . . . . .

,

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

,

Откуда, в частности, находим

.

Поэтому по следствию 1 из леммы 13.30 и по следствию 2 из той же леммы , т.е., , поэтому должно иметь вид , где есть одно из чисел . А так как выше указанные равенства показывают, что

Верно при и неверно при , то . Значит, –

первообразный корень по модулю . Теорема доказана.

Теорема 13.20. Пусть и – первообразный корень по модулю . Нечетное из чисел и будет первообразным корнем по модулю .

Доказательство. Действительно, . Далее, сравнения

и

Могут выполняться лишь одновременно, так как . А так как – первообразный корень по модулю и первое сравнение верно при и неверно при , то тем самым и второе сравнение верно при и неверно при . Тогда – первообразный корень по модулю . Теорема доказана.

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

Теорема 13.21. Пусть или и – все различные простые делители числа . Для того, чтобы число , взаимно простое с , было первообразным корнем по модулю , необходимо и достаточно, чтобы это не удовлетворяло ни одному из сравнений

, , . . . , .

Доказательство. Необходимость. Если – первообразный корень по модулю , то тем самым оно принадлежит показателю , и поэтому не может удовлетворять указанным выше сравнениям.

Достаточность. Пусть теперь не удовлетворяет ни одному указанному сравнению. Если показатель , которому принадлежит , меньше , то, обозначая один из простых делителей через , имели бы . Тогда и , что противоречит условию. Следовательно, и – первообразный корень по модулю . Теорема доказана.

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

Пример 13. 27. Пусть требуется найти первообразный корень по модулю 43. Вычисляем . Выберем в качестве предполагаемого первообразного корня число . Далее, проверяем выполнимость сравнений

, , .

Первое и третье сравнения дают соответственно и , а вот второе оказывается справедливым. Поэтому 2 не является первообразным корнем по модулю 43. Возьмем теперь число . Имеем

, , .

Ни одно из сравнений не выполняется, поэтому 3 – первообразный корень по модулю 43.

Вычислим теперь первообразный корень по модулю . Применим теорему 13.19. Имеем

,

.

Теперь при число не делится на 43. Поэтому будет первообразным корнем по модулю 43.

По модулю тогда по теореме 13.20 будет первообразным и по этому модулю.

Вновь считаем, что или и – первообразный корень по модулю .

Лемма 13.33. Если пробегает наименьшие неотрицательные вычеты по модулю , то пробегает приведенную систему вычетов по модулю .

Доказательство. Простое следствие леммы 13.29.

Определение 13.23. Пусть число взаимно просто с и – первообразный корень по модулю . Тогда, если

,

где , число называется дискретным логарифмом числа по основанию по модулю , или индексом и обозначается .

Ввиду леммы 13.33 каждое число взаимно простое с имеет единственный индекс среди чисел . Зная какой-либо индекс из указанного набора можно представить все дискретные логарифмы числа . Это будут все неотрицательные числа класса . А числа с данным индексом образуют класс чисел по модулю .

Лемма 13.34. Для и взаимно простых с

.

Доказательство. Имеем

, .

Перемножив почленно эти сравнения, получим

.

Значит, сумма в показателе последнего сравнения есть один из дискретных логарифмов произведения .

Следствие. .

Ввиду практической пользы дискретных логарифмов имеются таблицы индексов для всех не очень больших . Нахождение дискретных логарифмов для больших значений представляет собой сложную вычислительную задачу.