Порядок числа и класса вычетов по модулю и их свойства

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

.                                           (1)

Обозначаем порядок числа a по модулю m через P_m (a). Порядок по модулю обладает следующими свойствами.

1⁰ Если (a, m) =1 то P_m (a) существует и P_m (a) £. j(a).

Доказательство. Так как (a, m) =1, то по теореме Эйлера . Тогда множество натуральных чисел a, удовлетворяющих условию (1) не пусто и среди них существует наименьшее число, обозначаемое P_m (a).ÿ

2⁰ Если (a, m) =1 и b º a (mod m), то P_m (b) = P_m (a).

Доказательство. Так как (a, m) =1 и b º a (mod m), то (b, m) =1. Если d = P_m (a), g = P_m (b), По свойству сравнений и определению порядка

Так как g = P_m (b) - наименьшее натуральное число, удовлетворяющее этому сравнению, то g £ d. Аналогично доказывается, что d £ g. Из этих неравенств следует, что d = g.ÿ

3⁰ Если d = P_m (a) и , то d|a.

Доказательство. Допустим, что dFa. Разделим a на d с остатком: a = dg + r, где g, d Î Z, 0 < r <d. Тогда получим

,

что противоречит тому, что порядок d = P_m (a) наименьшее натуральное число, удовлетворяющее этому сравнению. Следовательно, d|a.ÿ

4⁰ Если d = P_m (a), то d|j(m).

Доказательство. Так как (a, m) =1, то по теореме Эйлера . Отсюда по свойству 3⁰ d|j(m). ÿ

5⁰ Если (a, m) =1 и d = P_m (a), , то aºb(mod d).

Доказательство. Пусть . Можем предположить, что a ³ b. Так как (a, m) =1, то отсюда получаем . Тогда по свойству 3 d|(a - b), т.е. aºb(mod d). ÿ

6⁰ Если (a, m) =1 и d = P_m (a), то все степени попарно несравнимы по модулю m..

Доказательство. Это следует из свойства 5⁰, так как числа 0, 1, …, d-1 попарно несравнимы по модулю d.ÿ

Из свойства 2⁰ следует, что, если(a, m) =1, для любого числа b Î` a mod m, и то P<sub>m</sub> (b) = P<sub>m</sub> (a). Поэтому число P<sub>m</sub> (a) называют порядком класса вычетов ` a mod m и обозначается в виде P_m (` a). Так как множество Z <sub>m</sub> ´ примитивных классов вычетов образует группу порядка j(m), то порядок P<sub>m</sub> (` a) это порядок элементы ` a в группе Z <sub>m</sub> ´. Тогда из свойств порядка элементов в группе получаем, что порядок элемента P<sub>m</sub> (` a) делит порядок j(m) группы Z _m ´ (свойство 4⁰) и все степени попарно различны (свойство 6⁰).

Порядок P_m (a) числа a взаимно простого с m можно вычислить постепенно находя во множестве чисел 1, 2, …, j(m) -1, наименьшее число d, удовлетворяющее условию . При таком способе нужно сделать самое худшее j(m) -2, умножения.

Алгоритм нахождения показателя r = P_m (a).

Ввод: Проверяемое число a и модуль m..

m:=0; r:= b; a 1:= a;; b 1:= b;

d:= function НОД (a, m);

  if d >1 then s $:= «показатель P_m (a) не существует»      

  else P:=1; (q, r): = div (a, m);

while r   ¹ 1 do P:= P + 1; (q, r): = div (ra, m); end while;

s $:= «показатель P_m (a) равен»;

  end if

Вывод: s $и P.

Пример 1. Найти показатель числа 7 по модулю 15. Так как (7, 15) =1, то показатель существует. Так как

7T1(mod 15), 7² º 49 º 4 T1(mod 15), 7³ º 4×7º-2 T1(mod 15), 7⁴ º -2×7º1(mod 15),

то P ₁₅(7) = 4.

Так как по свойству 4⁰ порядок числа P_m (a) делит число j(m), то найдя каноническое разложение числа j(m) можно перебирать только делители числа j(m). Тогда алгоритм вычисления показателя принимает следующий вид.

Алгоритм нахождения показателя r = P_m (a).

Ввод: Проверяемое число a и модуль m..

m:=0; r:= b;a 1:= a;;b 1:= b;

d:= function НОД (a, m);

if d >1 then s $:= «показатель P_m (a) не существует»      

else

f: = function j(m)

procedure Факторизация(f; A, k);{A- матрица, имеющая две строки, в первой            строка матрицы, простые числа, делящие число m, вторая – соответствующие показатели этих простых чисел в каноническом разложении числа f, k – число различных простых множителей в каноническом разложении числа f }

d:=1; (q, r): = div (a, m);

for i:= 1 to k; B (i, 1):=1; B (i, 2):=0; end for; i:=1;         

while r   ¹ 1 do d:= d + 1; (q, r): = div (ra, m);

r:=0; {Перебор делителей числа j(m) до тех пор пока не будет r   = 1}

while r   = 0 do

  if B (i, 2) < A (i, 2) then

     B (i, 2):= B (i, 2) +1; p:= A (i, 2); v:= a;

     while p > 0 do

        (p, u):= div (p,2)

           if u = 1 then (q, B (i, 1)):= div (B (i, 1)* v, m); end if

        ( q, v):= div (v* v, m);

       end while;

     r:= B (i, 1);

     while i > 1 do i:=i- 1; B (i, 1):= r; B (i, 2):=0; end while;

    else

    i:=i+ 1;

end while;

end while;

P:=1;

for i:= 1 to k;

while B (i, 2)> 0 do   P:= P*A (i, 1); B (i, 2):= B (i, 2)-1; end while;

end for;

s $:= «показатель P_m (a) равен»; P;

end if.

Вывод: s $и r.

Пример 2. Найти показатель числа 7 по модулю 15. Так как (7, 15) =1, то показатель существует. Вычисляем j(15) = 2×4 = 8. Делители числа j(15);1, 2, 4, 8.

Так как 7T1(mod 15), 7² º 49 º 4 T1(mod 15), 7⁴ º 4² º1(mod 15), то P ₁₅(7) = 4.