Теорема 1 (Критерий Люка)

В группе Up , p – простое число, существуют порождающие элементы.

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

Действительно, пусть δ1, δ2, … , δr – все различные показатели, которым по модулю p принадлежат числа 1,2,…,p—1 (то есть порядки этих чисел в Up). Пусть τ=НОК(δ12,… ,δr), и τ= Теорема 1 (Критерий Люка) - student2.ru - каноническое разложение. Каждый множитель Теорема 1 (Критерий Люка) - student2.ru этого разложения делит хотя бы одно из чисел δ1,…,δr. Поэтому можем представить одно из таких чисел как δj=a Теорема 1 (Критерий Люка) - student2.ru . Пусть ξj – одно из чисел ряда 1, 2, … , p—1: Opj)=δj.

Тогда, согласно Лемме 1, Op(η)= Теорема 1 (Критерий Люка) - student2.ru , где η= Теорема 1 (Критерий Люка) - student2.ru .

Согласно Лемме 2, Op(g)=τ= Теорема 1 (Критерий Люка) - student2.ru , где g=η1η2…ηk.

Поэтому, согласно Теореме 3, п.1, τ\(p—1).

Но поскольку числа δ1, δ2, … , δr делят τ, то любое из чисел ряда 1, 2, … , p—1 является решением сравнения xτ≡1(mod p), согласно Теореме 2, п.1.

Пользуясь Теоремой 1, §4, п.4, получаем p—1≤τ. Но τ как порядок элемента g не может быть больше, чем p—1, поэтому p—1=τ, а значит g – первообразный корень, или порождающий элемент группы Up .

6.3. Первообразные корни по модулям pα, 2pα.

Теорема (о существовании первообразного корня по модулю pα)

Пусть g – первообразный корень по модулю p, тогда существуют такое число t, что u= Теорема 1 (Критерий Люка) - student2.ru не делится на p, и тогда g+pt – первообразный корень по модулю pα Теорема 1 (Критерий Люка) - student2.ru α>1.

Замечание

Число u, заданное условием, является целым в силу теоремы Ферма. Действительно, поскольку g Теорема 1 (Критерий Люка) - student2.ru Up, то (g,p)=1 Теорема 1 (Критерий Люка) - student2.ru (g+pt,p)=1 Теорема 1 (Критерий Люка) - student2.ru по теореме Ферма, (g+pt)p—1≡1(mod p) Теорема 1 (Критерий Люка) - student2.ru p\((g+pt)p—1 –1).

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

Имеем:

gp—1=1+pT0

(g+pt)p—1=1+p(T0—gp—2t+pT)=1+pu *

где если t пробегает Zp, то и u пробегает Zp (полную систему вычетов по модулю р). Поэтому существует такое t Теорема 1 (Критерий Люка) - student2.ru Zp, для которого u не делится на p. При таком t из (*) получаем:

(g+pt)p(p—1)=(1+pu)p=1+p2u2

Теорема 1 (Критерий Люка) - student2.ru

………………………… **

Теорема 1 (Критерий Люка) - student2.ru

где все ui, i=2,3,…α—1 не делятся на р.

Пусть Теорема 1 (Критерий Люка) - student2.ru . Тогда (g+pt)δ≡1(mod pα), откуда gδ≡1(mod p) Теорема 1 (Критерий Люка) - student2.ru (р—1)\δ , и δ\φ(рα)=рα—1(р—1) . Тогда δ имеет вид δ=рr—1(р—1), где 1≤ r ≤ α.

Но (*) и (**) показывают, что сравнение Теорема 1 (Критерий Люка) - student2.ru верно при r = α и неверно при r < α, то согласно Теореме 3 п.1., δ=рα—1(р—1) =φ(рα), и (g+pt) – первообразный корень по модулю рα.

Теорема 2.

Пусть g – первообразный корень по модулю рα, α≥1. Нечетное g0 из чисел g, g+рα будет первообразным корнем по модулю 2рα .

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

Заметим, что g+рα будет являться первообразным корнем по модулю рα, а также φ(рα)=φ(2рα)=с. Нетрудно проверить, что сравнения g0r≡1(mod рα) и g0r≡1(mod 2рα) могут выполняться лишь одновременно. Первое сравнение выполняется при r=c и не выполняется при r<c (так как g0 – первообразный корень по модулю рα), следовательно второе сравнение верно при r=c и неверно при r<c. Значит g0 – первообразный корень по модулю 2рα.

Доказанные теоремы вкупе с теоремой о существовании первообразных корней по модулю p позволяют сделать следующий

Вывод: Существуют первообразные корни по модулям рα, 2рα для всех α. Если известен первообразный корень по модулю р, то, пользуясь Теоремами 1 и 2 настоящего пункта, можно найти первообразный корень по модулям рα, 2рα.

Пример.

p=71, наименьший первообразный корень по модулю 71 есть 7.

Найти первообразный корень по модулю 71α и 2·71α для всех α.

Согласно Теореме 1, нужно найти такое t, чтобы (g+pt)p1—1 Теорема 1 (Критерий Люка) - student2.ru 0(modp2).

Будем перебирать t:

t=0. g+pt=g=7.

770—1 mod 5041 = (710)7 –1 mod 5041 = 28147—1 mod 5041 =

= (28142)3 ·2814—1 mod 5041 = 42262·4226·2814—1 mod 5041=

= 3854·4226·2814 –1 mod 5041 = 1562 ≠ 0.

Итак, 7 – первообразный корень по модулю 71α для всех α.

Поскольку 7 – нечетное число, то, согласно Теореме 2, 7 - первообразный корень по модулю 2·71α для всех α.

Вообще говоря, нам повезло, первое же испытанное число t подошло. В другом случае, возможно, пришлось бы перебирать несколько t, прежде чем отыскали бы первообразный корень.

Разумеется, мы не отыскали все первообразные корни по данному модулю. Алгоритмы нахождения их весьма трудоемки, особенно тогда, когда требуется найти все или несколько первообразных корней.

Наши рекомендации