Первообразные корни и индексы

                         Министерство образования и науки    

                                             Российской Федерации

 

               Пензенский государственный педагогический университет

                                        имени В.Г.Белинского

 

 

 

 

 

 

Кафедра алгебры

 

 

 

 

                                                 Курсовая работа

                                                   

 

 

 

                          « Первообразные корни и индексы »

 

 

 

 

 

 

 

Выполнила:

студентка группы ИМ-31

3 курса очного  отделения

физико-математического  факультета

специальности: информатика-математика

Шобанова М.Е.

Проверила:

Тимербулатова В.Ф.

 

                                             Пенза 2011

 

 

 

 

Содержание

 

 

 

 

§1. Общие теоремы

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

§3. Разыскание первообразных корней по модулям   и  

§4. Индексы

§5. Индексы по любому составному модулю

§6. Примеры

Список литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                        §1.Общие теоремы

 

                       Определение. Класс[a],где (a,n)=1,называется первообразным корнем по модулю n, если показатель числа a по модулю n равен φ(n)- значению функции Эйлера для модуля n.

                       Известно, что любой показатель k числа a по модулю n делит φ(n). Поэтому, чтобы убедиться, что число a является первообразным корнем по модулю n, надо проверить, что для любого числа k делителя φ(n) ≠ 1 mod n.

 

                       Пример. Рассмотрим модуль n =54. Тогда

 

              φ(54) = φ(2×27) = φ(2×33) = (2-1)×33-1(3-1) = 18 = 2×3×3.

 

Делителями числа 18 являются числа 1, 2, 6, 9, 18. Рассмотрим число 5. Проверяем, будут ли числа 1, 2, 6, 9 показателями для числа 5 по модулю 54. Имеем :

 

 

 

Из приведенных вычислений ясно, что показатель, которому принадлежит число 5 по модулю 54, равен 18, т.е. значению φ(54). Отсюда следует, что класс [5] является первообразным корнем по модулю 54.

                     Заметим, что первообразных корней по модулю n может и не быть. Напомним, что для модуля n = 20, рассматривая все классы  взаимно простые с модулем, мы получили такие результаты:

 

                      для класса [1] показатель равен 1;

                      для классов [9], [11], [19] показатель равен 2;

                      для классов [3], [7], [13], [17] показатель равен 4.

 

Нет ни одного класса взаимно простого с модулем, у  которого показатель равен φ(20) = 8. Отсюда следует вывод, что для модуля 20 первообразный корень отсутствует.

 

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

 

 

               §2. Первообразные корни по модулям p^t и 2p^t

 

 

                       Теорема1. Пусть p – простое нечетное и t ≥ 1. Докажем существование первообразных корней по модулям p^t и 2p^t .

 

                       Теорема2.   Если x по модулю m принадлежит показателю ab, то x^a принадлежит показателю b.

                       Действительно, пусть x^a принадлежит показателю σ. Тогда (x^a)^σ ≡ 1( mod m), откуда x^aσ ≡ 1( mod m); следовательно a делится на ab, т.е. σ делится на b. С другой стороны, x^ab ≡ 1( mod m), откуда (x^a )^b ≡ 1( mod m); следовательно b делится на σ . Поэтому σ = b.

 

                       Теорема3. Если x по модулю m принадлежит показателю a, а y – показателю b, причем (a,b) = 1, то xy принадлежит показателю ab.

                       Действительно, пусть xy принадлежит показателю σ. Тогда (xy)^σ ≡ 1( mod m). Отсюда x^bσy^bσ ≡ 1( mod m) и x^bσ ≡ 1( mod m). Поэтому bσ делится на a, и ввиду (b,a) = 1, то и σ делится на a. Так же находим, что σ делится на b. Делясь же на a и на b, ввиду (a,b) = 1, σ делится и на ab. С другой стороны, из (xy)^ab ≡ 1(mod m) следует, что ab делится на σ. Поэтому σ = ab.

 

                       Теорема4. Существуют первообразные корни по модулю p.

                       Действительно, пусть τ – общее наименьшее кратное всех тех показателей

                                        σ₁, σ₂, …, σ_r,                                                (1)

 

каждому из которых по модулю p принадлежит хотя бы одно число ряда 1, 2, …, p – 1, пусть τ = q₁^a₁q₂^a₂…q_k^a_k – каноническое разложение числа τ; тогда при каждом s среди чисел (1) существует некоторое σ, делящееся на q_s^a_s и тем самым представимое в форме σ = a q_s^a_s . Если x – число, принадлежащее показателю σ, то, согласно b, x_s = x^a принадлежит показателю q_s^a_s. Сказанное относится к s = 1, 2, …, k; согласно с числом g = x₁x₂…x_k принадлежит показателю q₁^a₁q₂^a₂…q_k^a_k = τ.

                       Но поскольку показатели (1) суть  делители числа τ, то все  числа 1, 2, …, p – 1 удовлетворяют сравнению x^τ ≡ 1(mod p). Значит, p – 1 ≤ τ. Но τ – делитель числа p – 1,поэтому τ = p – 1, т.е. g – первообразный корень.

 

                       Теорема5. Пусть g – первообразный корень по модулю p. Можно указать f с условием, что и, определяемое равенством (g +pf)^{p – 1} = 1+pu, не делится на p. Соответствующее g +pf будет первообразным корнем по модулю p^a при любом a > 1.

                        Действительно, имеем 

 

         g^p-1 = 1+pT_0,                                                                                                                             (g +pf)^p-1 = 1+ p(T₀ – g^p-2t + pT) = 1+pu,                                                (2)

 

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

 

(g+pt)^p(p-1) = (1+pu)^p = 1+p²u₂ ,

(g+pt)^p2(p-1) = (1+p²u₂)^p = 1+p³u₃ ,                                                            (3)

………………………………….

 

где u₂ , u₃, ….  не делятся на p.

                  Пусть g+pt по модулю p^t принадлежит показателю σ. Тогда

 

                                       (g+pt)^σ ≡ 1(mod p^t).                                          (4)

 

Отсюда  (g+pt)^σ ≡ 1(mod p); следовательно σ кратно p-1, а так как σ делит φ(p^t) = p^t-1(p-1), то σ = p^r-1(p-1), где r- одно из чисел 1, 2, …, α. Заменяя левую часть сравнения (4) её выражением из соответствующего из равенств (2) и (3), получим (u = u₁)

 

1+p^ru_r ≡ 1(mod p^t), p^r ≡ 0(mod p^t), r = t, σ = φ(p^t), т.е. g+pt – первообразный корень по модулю p^t .

 

                         Теорема6. Пусть t ≥ 1 и g₁ – первообразный корень по модулю p^t. Нечетное из чисел g₁ и g₁+p^t будет первообразным корнем по модулю 2p^t.

                        Действительно, всякое нечетное x, удовлетворяющее одному из сравнений x^γ ≡ 1(mod p^t) и x^γ ≡ 1(mod 2p^t), очевидно, удовлетворяет и другому. Поэтому ввиду φ(p^t) = φ(2p^t)  всякое нечетное x, являющееся первообразным корнем по одному из модулей p^t и 2p^t, является первообразным корнем и по другому. Но из двух первообразных корней  g₁ и g₁+p^t по модулю p^t один – непременно нечетный; он, следовательно, будет первообразным корнем и по модулю 2p^t .

 

 

                           §3. Разыскание первообразных корней

                                           по модулям p^t и 2p^t  

 

Первообразные корни по модулям  p^t и 2p^t , где p – простое нечетное и t ≥ 1, можно разыскивать, пользуясь следующей общей теоремой:

                       Пусть c = φ(m)  и q₁, q₂, …, q_k – различные простые делители числа c. Для того чтобы число g , взаимно простое с m, было первообразным корнем по модулю m, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений

 

 g^c/q₁ ≡ 1(mod m), g^c/q₂ ≡ 1(mod m) , … g^c/q_k ≡ 1(mod m)                  (1)

 

                         Действительно, если g – первообразный корень, то тем самым оно принадлежит показателю c  и, следовательно, ни одному из сравнений (1) удовлетворять не может.

                         Обратно, допустим, что g не удовлетворяет ни одному из сравнений (1). Если бы показатель σ, которому принадлежит g, оказался меньше c, то, обозначая буквою q один из простых делителей c/σ, мы имели бы c/σ = qu, c/q = σu, g^c/q ≡ 1(mod p), что противоречит нашему допущению. Значит, σ = c и g – первообразный корень.

 

                        Примеры: 1) Пусть m = 41. Имеем φ(41) = 40 = 2³ * 5, 40/5 = 8, 40/2 = 20. Следовательно, для того чтобы g, не делящееся на 41, было первообразным корнем по модулю 41, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений

 

                      g⁸ ≡ 1(mod 41),  g²⁰ ≡ 1(mod41)                                     (2)

 

Но, испытывая  числа 2, 3, 4, …, находим (по модулю 41)

 

2⁸ ≡ 10,  3⁸ ≡ 1,  4⁸ ≡ 18,  5⁸ ≡ 18,   6⁸ ≡ 10,

2²⁰ ≡ 1,               4²⁰ ≡ 1,   5²⁰ ≡ 1,    6²⁰ ≡ 40.

 

Отсюда видим, что числа 2, 3, 4, 5 – не первообразные корни, так как каждое из них удовлетворяет, по крайней мере, одному из сравнений (2). Число 6 – первообразный корень, так как оно не удовлетворяет  ни одному из сравнений (2).

 

2) Пусть m = 1681 = 41².  Первообразный корень и здесь можно было бы найти, пользуясь общей теоремой. Но мы найдем его проще, применяя теорему 5, §2. Зная уже(пример 1), что первообразный корень по модулю 41 есть 6, находим

 

                              6⁴⁰ = 1+41(3+41i),

                    (6+41t)⁴⁰ = 1+41(3+41i-6³⁹t +41T) = 1+41u.

 

Чтобы u не делилось на 41, достаточно взять t =0. Поэтому в качестве первообразного корня по модулю 1681 можно взять число 6+41*0 = 6.

 

3) Пусть m = 3362 = 2*1681. Первообразный корень и здесь можно было бы найти, пользуясь общей теоремой. Но мы найдем его проще, применяя теорему 6, §2. Зная уже (пример 2), что первообразный корень по модулю 1681 есть 6, в качестве первообразного корня по модулю 3362 можно взять нечетное из чисел 6, 6+1681, т.е. число 1687.

 

                                                    

 

 

                                           §4.Индексы

 

                       Определение. Пусть числа a и b взаимно просты с n, т.е. ( a,n) = 1, (b,n) = 1. Число s называется индексом b по модулю n и основанию a, если 

 

                                        

 

При фиксированном  модуле n для индекса s принята такая форма записи

 

                                          

 

Для данной формы  из определения индекса получается следующее тождество

 

                                         

 

Заметим, что  если s индекс числа b по основанию a, т.е.

 

                                           

 

то s является индексом для любого числа β из класса [b] по любому основанию α из класса чисел [a]. Понятие индекса представляет собой аналогию понятия логарифма.

 

                      Пример. Пусть даны модуль n = 13 и основание a = 2. Тогда имеем

 

 

 

                           

                                  

     

 

Обратим внимание на два соотношения:

 

                             

 

которые показывают, что одно число может иметь  разные индексы.

 

                     Пример. Пусть даны модуль n = 21, основание a = 5. Тогда имеем

 

              

 

Обратим внимание, что для  модуля 21 не существует индекса для

числа 2 по основанию 5, т.е. значения  Действительно, не существует числа s, для которого сравнение

 

                                            

 

справедливо. На основании  приведенного примера возникает  вопрос – при каких условиях индекс b по основанию a существует для данного модуля n ?

Для решения этого вопроса  напомним, что если число g = φ(n), где φ(n) – значение функции Эйлера для модуля n, является наименьшим из всех чисел, при котором справедливо сравнение

 

                                            

 

то g называется первообразным корнем. В этом случае справедливо следующее утверждение.

 

                        Теорема. Пусть число g  есть любой первообразный корень по модулю n. Для каждого числа b, взаимно простого с модулем n существуют индексы по основанию g, т.е. найдутся такие числа s, что выполняется сравнение

 

                                        

 

Множество всех таких индексов s для данного фиксированного b совпадает с неотрицательными числами некоторого класса по модулю φ(n).

 

                         Теорема. Пусть g – первообразный корень по модулю n  и b – число взаимно простое с модулем n. Тогда сравнение

 

                                            

 

справедливо тогда  и только тогда, когда 

 

                                     

 

                         Теорема.  Пусть g – первообразный корень по модулю n, a и b – числа, взаимно простые с модулем n, т.е.

 

                                       

 

Тогда

 

                    

 

                         Теорема. Пусть g – первообразный корень по модулю n и a – число взаимно простое с модулем n, т.е.