Символ Якоби
Обобщением символа Лежандра является символ Якоби.
Определение 13.20. Пусть
и нечетное,
и
.
Тогда символом Якоби называется
арифметическая функция
(читается «
по
»),
определяемая соотношением:
,
где
,
– простые числа,
– символ Лежандра,
.
Этот символ можно использовать при вычислениях символа Лежандра. Отметим свойства символа Якоби, вытекающие из соответствующих свойств символа Лежандра.
1.
;
2.
;
3.
;
4.
;
5.
;
6.
.
Доказательства этих свойств легко воспроизводятся на основании, как сказано, свойств символа Лежандра. Поэтому уделим внимание только свойствам 2 и 6 . Пусть .
Доказательство свойства 2 .
Имеем
.
При этом
,
.
Отсюда и получается, что
.
Доказательство 6 в известном смысле повторяет идею доказательства 2 . Действительно,
.
Но
,
.
Тогда из предыдущей формулы находим, что
.
Похожим образом можно получить и закон взаимности для символов Якоби.
Теорема 13.17 (закон взаимности символов Якоби).
Пусть
и
– натуральные взаимно простые нечетные
числа. Тогда
.
Доказательство. Пусть
и
,
где
и
– простые числа,
,
.
Имеем
.
Далее, так же как и при доказательстве свойства 2 , находим
,
,
.
Поэтому в итоге получаем требуемое
.
Пример 13.26. Пусть требуется узнать, является ли число 185 квадратичным вычетом по модулю 631. Вычислим символ Лежандра
Результат вычислений показывает, что число 185 не является квадратом (квадратичным вычетом) по модулю 631.
Ясно, что число 185 не простое, тем не менее, символ можно «перевернуть» по теореме 13.17.
Первообразные корни и дискретный логарифм
Рассмотрим теперь мультипликативную
группу классов вычетов. Пусть
–
кольцо классов вычетов по модулю
.
Обозначим через
множество классов из
взаимно простых с
.
Как уже отмечалось, такое подмножество
существует как следствие свойства 14
числовых сравнений.
Лемма 13.28. Множество относительно операции умножения классов образует мультипликативную группу порядка .
Доказательство. Учитывая теорему
13.7 требуется проверить обратимость
классов. Действительно, пусть
и
.
Тогда по линейному представлению НОД
(т. 13.2) получим, что для некоторых
,
откуда, переходя к классам, находим
.
Таким образом, класс
является обратным к классу
,
т.е.,
.
Кроме того,
есть число классов взаимно простых с
модулем
.
Это доказывает лемму.
Определение 13.21. Пусть
и
.
Тогда наименьшее натуральное число
такое, что
называется показателем, которому
принадлежит
(или класс
)
по модулю
.
Это определение имеет смысл хотя бы
потому, что по теореме Эйлера
.
Лемма 13.29. Если показатель числа
по модулю
равен
,
то
есть система чисел попарно несравнимых
между собой по модулю
.
Доказательство. Если представить,
что
,
где
,
то легко находим, что
,
где
,
а это противоречит определению показателя.
Лемма 13.30. Если показатель,
которому принадлежит число
по модулю
равен
,
то
.
Доказательство. Разделим
и
на число
с остатком. Имеем
,
,
,
.
Необходимость. Из того, что
следует,
что
.
Откуда
.
Так как
,
то сравнение возможно лишь, если
,
т.е.,
.
Достаточность. Если
,
то
.
Значит,
,
а тогда
.
Умножая обе части последнего сравнения
на
,
где
,
получим, что
.
Следствие 1.
.
Следствие 2.
.
Последнее следствие приводит к определению, так как любой показатель обязательно делит число , и наибольший среди всех делителей.
Определение 13.22. Если показатель, которому принадлежит число по модулю , равен , то а называется первообразным корнем по модулю .
Из определения не ясно, существуют
ли первообразные корни по модулю
.
Докажем существование первообразных
корней по модулям
и
,
где
–
простое нечетное. Но предварительно,
рассмотрим два свойства показателей.
Лемма 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. Для и взаимно простых с
.
Доказательство. Имеем
,
.
Перемножив почленно эти сравнения, получим
.
Значит, сумма в показателе последнего сравнения есть один из дискретных логарифмов произведения .
Следствие.
.
Ввиду практической пользы дискретных логарифмов имеются таблицы индексов для всех не очень больших . Нахождение дискретных логарифмов для больших значений представляет собой сложную вычислительную задачу.