Построение первообразного корня по модулю n (Указание к лабораторной работе № 9)

Лабораторная работа №9

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

Цель работы

          Ознакомится с теоремой Эйлера, а также построить первообразные корни по модулю n.

Указание к работе

В силу теоремы Эйлера, для любых взаимно простых а и n выполняется соотношение

a^f(n) º 1 modn,                                               (9.1)

где f(n) обозначает функцию Эйлера, значение которой равно числу положительных целых значений, меньших n и взаимно простых с n. Для простого числа p

f(p)=p-1,

Если предположить, что два числа p и q простые, тогда для n=p^a*q^bфункция Эйлера будет иметь вид

f(n)= f(p^a*q^b)= f(p^a)* f(q^b)=[(p-1) p^a-1]*[(q-1)q^b-1].           (9.2)

Рассмотрим более общее соотношение, чем (9.1). Говорят, что число a, взаимно простое с модулем n, принадлежит показателю m, если m – такое наименьшее натуральное число, что выполняется сравнение

a^m º 1 modn.                                              (9.3)

Если а и n являются взаимно простыми, то существует, по крайней мере, одно число m=f(n), удовлетворяющее (9.3). Наименьшее из положительных чисел m, для которых выполняется (9.3), является длиной периода последовательности, генерируемой степенями а.

Справедливы следующие свойства.

Свойство 1. Числа a⁰, a¹,… ,a^m-1 попарно несравнимы по модулю n. Действительно, a^l ºa^kmodn, l> k Þ a^l-k º 1 modn, где l– kÎN, l– k< m.

Свойство   2.  a^g ºa^{g ’}modn Û gºg ’ modm. Разделим g, g ’ на m с остатками

g = mq + r, g ’ = mq’ + r’.  Тогда a^g ºa^{g ’} Û a^mq+r ºa^mq’+r’ Û a^r ºa^r’ Û r’=r. Отсюда вытекает следующее свойство.

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

Свойство 4. По любому простому модулю p существует первообразный корень. Первообразные корни существуют по модулям 2, 4, p^a, 2p^a, где p – нечетное простое, aÎ N.

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

         

Необходимость следует из того, что a^f(n) º 1 modn и сравнение не имеет места при меньших показателях степени. Обратно, допустим, что a не удовлетворяет ни одному из сравнений, и пусть a принадлежит показателю m < c. Тогда        m|c Þc=mn. Обозначим через q простой делитель u. Тогда легко получить противоречие:

a^c/q= a^mu/q =( a^m)^u/q º 1 mod n.

Если некоторая последовательность имеет длину f(n), тогда целое число а генерирует своими степенями множество всех ненулевых вычетов по модулю n. Такое целое число называют первообразным корнем числа а по модулю n. Количество их равно для числа n

f(n-1),                                                         (9.4)

где f- функция Эйлера.

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

a ⁸  º1(mod41),  a²⁰  º1(mod41).

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

Задание

Определить для числа n=97 все его первообразные корни и их количество.

Контрольные вопросы

1.   Дайте определение понятия первообразный корень.

2.  Назовите свойства первообразных корней.

3.  В чём смысл теоремы Эйлера?