Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2020-07-07 | 549 |
5.00
из
|
Заказать работу |
|
|
Определение 1. Пусть (a, m) =1. Порядком или показателем числа a по модулю m называется такое наименьшее натуральное число a, что
. (1)
Обозначаем порядок числа a по модулю m через Pm (a). Порядок по модулю обладает следующими свойствами.
10 Если (a, m) =1 то Pm (a) существует и Pm (a) £. j(a).
Доказательство. Так как (a, m) =1, то по теореме Эйлера . Тогда множество натуральных чисел a, удовлетворяющих условию (1) не пусто и среди них существует наименьшее число, обозначаемое Pm (a).ÿ
20 Если (a, m) =1 и b º a (mod m), то Pm (b) = Pm (a).
Доказательство. Так как (a, m) =1 и b º a (mod m), то (b, m) =1. Если d = Pm (a), g = Pm (b), По свойству сравнений и определению порядка
Так как g = Pm (b) - наименьшее натуральное число, удовлетворяющее этому сравнению, то g £ d. Аналогично доказывается, что d £ g. Из этих неравенств следует, что d = g.ÿ
30 Если d = Pm (a) и , то d|a.
Доказательство. Допустим, что dFa. Разделим a на d с остатком: a = dg + r, где g, d Î Z, 0 < r <d. Тогда получим
,
что противоречит тому, что порядок d = Pm (a) наименьшее натуральное число, удовлетворяющее этому сравнению. Следовательно, d|a.ÿ
40 Если d = Pm (a), то d|j(m).
Доказательство. Так как (a, m) =1, то по теореме Эйлера . Отсюда по свойству 30 d|j(m). ÿ
50 Если (a, m) =1 и d = Pm (a), , то aºb(mod d).
Доказательство. Пусть . Можем предположить, что a ³ b. Так как (a, m) =1, то отсюда получаем . Тогда по свойству 3 d|(a - b), т.е. aºb(mod d). ÿ
60 Если (a, m) =1 и d = Pm (a), то все степени попарно несравнимы по модулю m..
Доказательство. Это следует из свойства 50, так как числа 0, 1, …, d-1 попарно несравнимы по модулю d.ÿ
Из свойства 20 следует, что, если(a, m) =1, для любого числа b Î` a mod m, и то Pm (b) = Pm (a). Поэтому число Pm (a) называют порядком класса вычетов ` a mod m и обозначается в виде Pm (` a). Так как множество Z m ´ примитивных классов вычетов образует группу порядка j(m), то порядок Pm (` a) это порядок элементы ` a в группе Z m ´. Тогда из свойств порядка элементов в группе получаем, что порядок элемента Pm (` a) делит порядок j(m) группы Z m ´ (свойство 40) и все степени попарно различны (свойство 60).
|
Порядок Pm (a) числа a взаимно простого с m можно вычислить постепенно находя во множестве чисел 1, 2, …, j(m) -1, наименьшее число d, удовлетворяющее условию . При таком способе нужно сделать самое худшее j(m) -2, умножения.
Алгоритм нахождения показателя r = Pm (a).
Ввод: Проверяемое число a и модуль m..
m:=0; r:= b; a 1:= a;; b 1:= b;
d:= function НОД (a, m);
if d >1 then s $:= «показатель Pm (a) не существует»
else P:=1; (q, r): = div (a, m);
while r ¹ 1 do P:= P + 1; (q, r): = div (ra, m); end while;
s $:= «показатель Pm (a) равен»;
end if
Вывод: s $и P.
Пример 1. Найти показатель числа 7 по модулю 15. Так как (7, 15) =1, то показатель существует. Так как
7T1(mod 15), 72 º 49 º 4 T1(mod 15), 73 º 4×7º-2 T1(mod 15), 74 º -2×7º1(mod 15),
то P 15(7) = 4.
Так как по свойству 40 порядок числа Pm (a) делит число j(m), то найдя каноническое разложение числа j(m) можно перебирать только делители числа j(m). Тогда алгоритм вычисления показателя принимает следующий вид.
Алгоритм нахождения показателя r = Pm (a).
Ввод: Проверяемое число a и модуль m..
m:=0; r:= b;a 1:= a;;b 1:= b;
d:= function НОД (a, m);
if d >1 then s $:= «показатель Pm (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 $:= «показатель Pm (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), 72 º 49 º 4 T1(mod 15), 74 º 42 º1(mod 15), то P 15(7) = 4.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!