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

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

Число классов с заданным показателем. Каждый класс, взаимно простой с модулем m, имеет свой порядок, который делит φ(m). Верно ли обратное, т. е. если d - натуральный делитель φ (m), то найдется ли класс, имеющий порядок d?Оказывается, это верно не
для любого модуля. Пусть d - натуральный делитель φ(m). Обозначим через ψ(d) количество классов, имеющих порядок d.

Например, если m=13, то ψ(l2)=4, ψ(6) = 2, ψ(4)= 2 (смотри примеры предыдущего параграфа). Для некоторых d может оказаться, что ψ(d) равно нулю. Очевидно, что если d₁,d₂,…,d_s - все натуральные делители φ(m), то ψ(d₁)+ψ(d₂)+…+ψ(d_s)=φ(m), так как всего φ(m) классов, взаимно простых с модулем. То есть =φ(m).

Лемма, Сумма значений функции Эйлера от всех делителей числа n (n N) равна n (то есть φ(d)=n).

Доказательство, Пусть n=p₁^α₁…p_s^α_sканоническое разложение числа n. Рассмотрим произведение P=(1+φ(p₁)+φ(p₁²)+…+φ(p₁^α₁))…(1+φ(p_s)+…+φ(p_s^α_s)). Если раскрыть скобки, то получим сумму всевозможных слагаемых вида φ(p₁^β₁)φ(p₂^β₂)…φ(p_s^β_s)=φ(p₁^β₁p₂^β₂…p_s^β_s) (используем мультипликативность функции Эйлера), где 0 β_i α_i,То есть получим сумму значений функции Эйлера φ(d) для всех делителей d числаn.Но1+ φ(p_i)+ φ(p_i²)+...+φ(p_i^α_i)=1+(p_i-1)+(p_i²-p_i)+…+(p_i^α₁-p_i^α₁^-1)=p_i^α₁и P=p₁^α₁p₂^α₂…p_s^α_s=n Следовательно, ∑φ(d)=n

Теорема 1. До простому модулю p если к делит φ(p), (k€N), то ψ(k)=φ(k).

Доказательство. Пусть k делит φ(p)=p-1. Может оказаться, что ψ(k)=0.Есда же найдётся элемент а, имеющий порядок k то будем искать часло классов, имеющих тот же порядок. Так как числа, имеющие порядок k удовлетворяют сравнению х^k≡ l(mod р) (l) то искомые классы находятся среди решений этого сравнения. Но все решения этого сравнения исчерпываются классами ā,ā²,…,ā^k (2)

Действительно, все эти классы 1) являются решениями (1), ибо (aⁱ)^k=(a^k)ⁱ≡1(modp); 2) классы различны, так как аⁱ и a^j не сравнимы по модулю p при i≠j(свойство 8 показателей) и 3) их число равно к, то есть максимально возможному количеству решений сравнения (]) (сравнение по простому модулю степени k не может иметь больше, чем k решений).Поэтому остаётся разыскать среди классов (2) те. которые имеют порядок к. Из свойств 6 и 7 показателей следует, что среди классов (2) āⁱ имеет тот же порядок, что и ā, тогда и только тогда, когда (k,i)= 1. А так как среди чисел 1,2,..,k содержится ровно φ(к) чисел, взаимно простых с к, то в ряду (2) φ(к) классов, имеющих порядок к. Следовательно, ψ(k)=φ(k).

Итак,ψ(k)=φ(k) или ψ(k)=0. Равенство (*) при m=р имеет вид ∑ψ(k)=p-1. По лемме ∑φ(к) =р -1. Поэтому
∑ψ(k)=∑φ(к) откуда легко видно, что ψ(к)= φ(к) для любого делителя k числа р -1. Действительно, если бы для некоторых k было бы ψ(к) = 0, то в правой части равенства остались бы лишние положительные слагаемые и равенство бы нарушилось.

2. Первообразные корни по простому модулю Определение. Пусть (g, m) = 1, m€N. Число g называют первообразным корнем по модулю m, если порядок числа g по модулю m равен φ(m). Так как P(g) = P(ḡ)то первообразным корнем можно называть и класс ḡ.

Примеры. 1. Найдём первообразные корни по модулю 7. φ(7)= 6. Порядок любого числа а - делитель числа 6. Поэтому для нахождения порядка а достаточно рассмотреть а² и а³, так как а⁶ ≡ l(mod 7) по теореме Эйлера. Будем искать порядки представителей всех классов по модулю 7, взаимно простых с модулем. 1 имеет порядок 1. По модулю 7 имеем: 2²≡ 4, 2³≡1, Р(2) = 3, 2 - не первообразный корень. 3² =2, 3³ =-1 по модулю 7, следовательно, Р(3) = 6 и 3 - первообразный корень по модулю 7. По свойствам порядков тот же порядок имеет 3^k, где (к, 6) = 1, то есть ещё только 3⁵ = З³• 3²≡ -9≡5(mod7). Следовательно, первообразные корни по модулю 7 только 3 и 5. По модулю 13 первообразными корнями являются 2. 6, 7 и 11. Так как их порядок равен 12 = φ(13) (смотри примеры §1).

Теорема 2. По простому модулю р существует φ(р — ]) классов первообразных корней.

Доказательство. Порядок первообразного корня по модулю р равен р -1. Из теоремы 1 количество классов, имеющих порядок р -1, равно φ(р - l). Следовательно, количество первообразных корней по модулю р равно φ(р-1). Заметим, что первообразные корни существуют не по любому модулю, а только но модулям 2,4, р^α и 2р^α, гдер-простое нечётное число, а α>=1

Теорема 3. Если g - первообразный корень по модулю m. то числа образуют приведённую систему вычетов по модулю m.
Доказательство. Так как P_m(g)=φ(m), то по свойству 8 показателей и числа попарно не сравнимы по модулю m. Они взаимно просты с m так как (g,m)=1 и этих чисел φ(m). По признаку приведённой системы вычетов эти числа образуют приведению систему вычетов по модулиm. В частности, если g — первообразный корень по простому модулю р. То g,g²,...,g^φ(m)- приведённая система вычетов по модулю р, которую можно заменить также системой g° =1,g¹,...,g^p-2.

§3. Индексы чисел и классов по данному модулю

1. Индексы и их свойства

Свойства первообразных корней дают возможность ввести в теорию чисел важное понятие, которое аналогично понятию логарифма. По теореме 3 предыдущего параграфа, если g — первообразный корень по модулю m, то g,g²,...,g^φ(m)- приведённая система вычетов по модулю m. Отсюда вытекает', что для каждого числа а, взаимно простого с m, в этой системе найдется единственное число gⁱ, которое принадлежит тому же классу по модулю mчто и а, т.е. такое, что gⁱ = a(modm). Число i и называют индексом числа а по модулю m с основанием g.

Определение. Если g первообразный корень по модулю m и для а, взаимно простого с m, имеет место сравнение a ≡gⁱ(modm), где i>= 0, тоi называют индексом числа а по модулю m при основании g и обозначают символом ind_ga или (если нет опасности ошибиться или нет надобности подчеркивать основание) более кратко, через inda.

Из определения следует, чтоg^indga≡a(modm).

Заметим следующее. Если gⁱ ≡ a(modm) и a≡ b(modm), то gⁱ = b(modm), то есть все числа одного класса по модулю т имеют один и тот же индекс. Можно говорить об индексе класса.

Если t - другое число, такое, что g^t≡ a(modm) то gⁱ ≡g^t (mod m) По свойству 5 порядков это верно тогда и только тогда, когда i≡t(modP(g)), то есть i≡t(modφ(m)).

Итак, множество индексов одного и того же числа, взаимно простого с модулем, состоит из неотрицательных вычетов некоторого класса вычетов по модулю φ(m) a≡b(modm)ó inda≡indb(modφ(m)). В частности по простому модулю p a≡b(modp)óinda≡indb(mod(p-1)).

Индексы обладают следующими свойствами, которые аналогичны свойствам логарифмов.

1. Индексы произведения сравнимы по модулю φ(m) с суммой индексов сомножителей: Ind_g(a₁,a₂,…,a_n)≡ind_ga₁+ind_ga₂+…+ind_ga_n(modφ(m)). Действительно,g^inda₁^+inda₂^+…+inda_n=g^inda₁g^inda₂…g^inda_n≡a₁a₂…a_n(modm). Следовательно, ind_ga₁+ind_ga₂+…+ind_ga_n – один из индексов числа a₁,a₂,…,a_n, то есть Ind_g(a₁,a₂,…,a_n)≡ind_ga₁+ind_ga₂+…+ind_ga_n(modφ(m)). Если все множители равны, то имеем следующее.

2. Индекс степени (с натуральным показателем) сравним по модулю φ(m) с произведением показателя степени на индекс основания степени: indaⁿ≡ninda(modφ(m)).

Заметим, что пр любом простом pиндекс единицы сравним по модулю с нулём,а индекс основания- с еденицей. Ind1≡0(mod(p-1)),indg≡1(mod(p-1)). Это следует из того, что g⁰≡1(modp) и g¹≡g(modp).