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

В настоящем пункте будем рассматривать число n, причем n—1= * - каноническое разложение на простые сомножители.

Теорема

O_n(a)=n—1 1) a^n—1≡1(mod n);

2) , 1(mod n).

Доказательство:

Пусть O_n(a)=n—1. Тогда (1) выполняется в силу определения порядка элемента в группе. Кроме того, , 1 ≤ < n—1= O_n(a), откуда в силу определения порядка элемента, выполняется (2).

Пусть теперь выполнены (1) и (2). Покажем, что O_n(a)=n—1.

В силу (1), O_n(a)\(n—1). В силу (2), O_n(a) не делит . Значит, O_n(a)=n—1.

□

Результатами только что доказанной теоремы можно пользоваться для нахождения порождающего элемента группы U_p, причем проверять стоит только второй пункт, так как первый для простого модуля выполняется автоматически согласно теореме Ферма. Кроме того, можно вывести правило: если a₁, a₂ не являются порождающими элементами группы U_p, то a₁a₂ также не является порождающим элементом U_p. Отсюда делаем вывод о том, что наименьший порождающий элемент группы U_p – простое число.

Пример

p=71. p—1=70=2·5·7.

Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a¹⁰ 1(mod n), a¹⁴ 1(mod n), a³⁵ 1(mod n).

Будем испытывать числа из U₇₁. Вместо a^b mod 71 для краткости будем писать a^b.

2: 2¹⁰ =30, 2¹⁴ =54, 2³⁵=1. 2 не является порождающим элементом.

3: 3¹⁰ =48, 3¹⁴ =54, 3³⁵=1. 3 не является порождающим элементом.

5: 5¹⁰ = 1. 5 не является порождающим элементом.

7: 7¹⁰ =45, 7¹⁴ =54, 7³⁵=70. 7 – порождающий элемент.

Итак, наименьший порождающий элемент группы U₇₁ (или первообразный корень по модулю 71) есть 7.