Первообразные корни их существование и свойства

Определение 1. Число g называется первообразным корнем по модулю m, если порядок числа g по модулю m равен j(m), т.е. P_m (a) = j(m).

Из этого определения свойств порядка вытекают следующие свойства первообразного корня.

1⁰ Если g первообразный корень по модулю m, то , то aºb(mod j(m).

2⁰ Если g первообразный корень по модулю m, то все степени

                                                  (1)

попарно несравнимы по модулю m.

3⁰ Если g первообразный корень по модулю m, то любое число класса ` g  по модулю m первообразный корень по модулю m.

Из 2⁰ следует,   что числа (1) образуют приведенную систему классов вычетов по модулю m, а множество всех соответствующих классов вычетов совпадает с группой Z _m ´. Таким образом, для модуля m существует первообразный корень тогда и только тогда, когда группа примитивных классов Z _m ´ по модулю m является циклической. При этом класс ` g является образующим элементом группы Z _m ´.

Теорема 1. Для любого простого числа p существует ровно j(p -1) классов первообразных корней по модулю p.

Доказательство. Рассмотрим полную систему вычетов по модулю p:

1, 2,…, p -1.                                                   (2)

 Каждое из чисел a этого множества имеет показатель d = P_p (a), который является делителем числа j(p) = p -1. Обозначим через y(d) число чисел данного множества (2), которые имеют показатель d. Тогда справедливо равенство

.                                                (3)

Из свойств функции Эйлера следует, что справедливо равенство

.                                                (4)

Докажем, что y(d) £ j(d).

Если y(d) =0, то это неравенство очевидно. что

Пусть y(d) > 0. Тогда существует такое число a из множества (2), что           P_p (a) = d. По свойству показателя классы

` a, ` a ²,…, ` a^k                                                          (5)

образуют различные решения сравнения  

x^d º 1(mod p).                                                 (6)

Так как последнее сравнение имеет не более d решений, то классы (5) есть все решения последнего сравнения.

С другой стороны, любое число b из множества (2), для которого показатель равен d, удовлетворяет сравнению, т.е. класс ` b совпадает с одни из классов (5): ` b =` a^k для некоторого значения k = 1, 2,…, d. Если НОД(d, k) = s > 1, то

и показатель числа a будет меньше d. Следовательно, если число b =` a^k имеет показатель d, то (d, k) = 1, и таких чисел во множестве 1, 2,…, d не более j(d).

Из (3) и (4) следует

.

Так как для любого d |(p -1) имеем y(d) £ j(d), то получим, что для любого d |(p -1) равенство y(d) = j(d). Последнее верно и для d = p -1. Так как  y(p -1) равно числу первообразных корней во множестве (2), то теорема доказана.ÿ  

Первообразный корень по модулю p можно находить, перебирая a все числа начиная с 2. Вычислить показатель P_p (a) числа a по модулю p. Если P_p (a) = p -1, то a - первообразный корень, если P_p (a) < p -1, то берем следующее число a + 1.

Алгоритм нахождения первообразного корня по модулю p.

Ввод: Простое число p.

g:= 1;

if p >2 then

Repeaet

g:= g +1; P:= function Показатель ( g, p);

until  P = p -1;

Вывод: g.

Теорема 2. Пусть g – первообразный корень по модулю простого числа p > 2.  Существует такое целое число t с условием, что число u, определяемое равенством

,                                     (7)

не делится на p. Тогда число g + pt является первообразным корнем по любому модулю p ^a.

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

,

(8)

где число u вместе с числом t пробегают полную систему вычетов по модулю p. Поэтому можно указать такое t, что в равенстве (7) число u не делится на p.

При таком t имеем

(9)

где все числа u ₂, …, u_k не делятся на p.

Покажем, что для любого числа a>1 число g + pt является первообразным корнем по модулю p ^a. Допустим, что показатель числа g + pt по модулю p ^aравен d. Тогда . Отсюда . Так как показатель числа g по модулю p равен p -1, то по свойству показателя (p -1)|d и d = (p -1) q, где q Î Z. По свойству показателя по модулю p ^a имеем d|j(p ^a), т.е. (p -1) q | (p ^a-1(p -1)). Отсюда q | p ^a-1 и q = p^r, 0 £ r £ a-1.

Равенства (8) и (9) показывают, что сравнение

верно при r = a и неверно при r < a. Таким образом, g + pt - первообразный корнь по модулю p ^a. ÿ

Теорема 3. Если a ³1, g – первообразный корень по модулю p ^a, то нечетное из чисел g, g + p ^a является первообразным корнем по любому модулю 2 p ^a.

Теорема 4. Первообразные корни по модулю m существуют лишь в случаях, когда m = 2, 4, p ^a, 2 p ^a , где p – нечетное простое число, a - целое число ³1.

Если известно каноническое разложение числа j(m), то для нахождения первообразного корня по модулю можно воспользоваться следующим критерием первообразного корня.

Теорема 5. Пусть - каноническое разложение числа c = j(m),     (g, m) =1. Для того, чтобы число g было первообразным корнем по модулю m необходимо и достаточно, чтобы не выполнялось ни одно из сравнений

.                                    (10)

Доказательство. Если g - первообразный корень по модулю m, то число g имеет порядок с по модулю m и ни одно из сравнений (10) выполнятся недолжно.

Обратно, пусть не выполняется ни одно из сравнений (10). Покажем, что порядок числа g по модулю m равен c. Допустим, что P_m (g) = d < c. Тогда число , и пусть q один из простых делителей этого числа, , u Î N. Тогда

получаем противоречие с (10).ÿ

Пример 2. Найти первообразный корень по модулю 722.

Имеем 722 = 2×19². Найдем первообразный корень по модулю 19.

Находим j(19) = 18 = 2²×3. Возьмем число 2.

Имеем

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

Далее

.

Так как 3 не делится на 19, то по теореме 2 является первообразным корнем по любой степени числа 19, т.е. 2 первообразный корень по модулю 19².

Так как число 2 + 19² = 363 нечетное, то по теореме 3 первообразным корнем по модулю 722 =2×19² является число 363.