Первообразные корни

Говорят, что число а, взаимно простое с модулем т, принадлежит показателю d, если d — такое наименьшее натуральное число, что выполняется сравнение a^d ºl(mod т). Справедливы следующие свойства.

Свойство 1. Числа a⁰, a¹,…, a^{d -1} попарно несравнимы по модулю т.

Свойство 2. а^g º a^h (mod т) <=> g º h(mod d).

Свойство 3. d |j(т). Число, принадлежащее показателю j(т), называется первообразным корнем по модулю т.

Свойство 4.По любому простому модулю р существует первообразный корень.

Гауссом доказано сущест­вование первообразных корней по модулям р^k и 2р^k при любом нечетном про­стом р. Легко убедиться, что при т = 4 первообразный корень также существу­ет. Таким образом, первообразные корни существуют по модулям 2, 4, р^k, 2 р^k, где р — нечетное простое, kÎN.

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

Нахождение первообразных корней упрощает следующее свойство.

Свойство 5. Пусть с = j(т) и q₁,q₂, ...,q_k — различные простые делите­ли числа с. Число a, взаимно простое с модулем т, будет первообразным корнем тогда и только тогда, когда не выполнено ни одно из следующих сравнений:

a^c/q1º1(mod m), a^c/q2ºl(mod m),..., a^c/qkºl(mod m). (3.1.11.1)

Пример. Пусть т = 41. Имеем с =j(41) = 40= 2³•5. Итак, первообразный корень не должен удовлетворять двум сравнениям

а⁸º1(mod41), a²⁰ºl(mod 41).

Испытываем числа 2, 3, 4, ...: 2⁸ º10, 2²⁰ º 1, 3⁸ º1, 4⁸º18, 4²⁰ º 1, 5⁸ º18,5²⁰ º 1, 6⁸ = 10, 6²⁰ = 40. Отсюда видим, что 6 является наименьшим первообраз­ным корнем по модулю 41.

3.1.12. Индексы по модулям р^k и 2р^k

Обозначим через т модуль вида р^k или 2р^k, а через g – первообразный корень по этому модулю. Положим с=j(т).

Свойство 1. Если число g принимает последовательно значения 0, 1, ..., с -1, то g^g пробегает приведенную систему вычетов по модулю т.

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

Пусть а º g^g(mod т). Число g (g ³0) называется индексом числа а по модулю т при основании g. Используются обозначения g = ind_ga или g = ind а. В силу тео­ремы Эйлера индекс определен по модулю с. Тем самым было бы правильнее говорить о классе вычетов по модулю с.

Свойство 2. ind ab ºind а + ind b (mod с).

Свойство 3. ind aⁿ º n ind а(modc).

Если воспользоваться таблицами индексов, то можно решать показательные и степенные сравнения путем их индексирования (дискретного логариф­мирования). В самом деле, степенное сравнение xⁿ º a(mod т) равносильно сравнению n ind x º ind a(modc), решение которого при наличии таблиц не со­ставляет труда. Положим d = (п, с).

Свойство 4. Сравнение хⁿ ºa(mod т) разрешимо тогда и только то­гда, когда d делит ind а. В случае разрешимости имеется d решений.