Глава 17 Первообразные корни и индексы
Порядок числа по данному модулю
Пусть а и b - два взаимно простых числа, причем a EZ, т Є N. Порядком (показателем) числа апо модулю ///называется наименьшее
|
натуральное число к, такое, что: |
|
|
ак = l(mod т) |
(2.302) |
|
Обозначение: |
|
|
0 (a modm) |
(2.303) |
|
Если целые а и Z/сравнимы по mod т, т.е. |
|
|
b = a (mod т) |
(2.304) |
Таким образом, все элементы класса вычетов a mod т имеют порядок к. Число к называется порядком класса вычетов а по модулю т.
Например, найдем
0(2 mod 15)
Решение.
- 21 ? l(mod 15)
- 22 Ї l(mod 15)
- 23 ї l(mod 15)
- 24 ? l(mod 15)
Значит,
0(2 mod 15) = 4
Ответ: 4.
Первообразный корень по модулю m
Теорема 2.64
Если
0(amod m) = k, (2.304)
то числа а°, а1, а2,..., ап-1 попарно несравнимы по модулю т.
Доказательство. Допустим противное, т.е. пусть
as = af(mod т) (2.305)
0
Так как а и т взаимно просты, то ad и т также взаимно просты.
Разделим обе части сравнения (2.305) на cd:
|
as ad |
|
— = — (mod т) (2.306) а1 а1 |
|
as-t = l(mod т), (0 < s - t < к) (2.307) |
получили неверное сравнение.
Таким образом, если
к = 0(а mod m), (2.308)
то
а0, а1, а2, ...,ак-1
попарно несравнимы
Ч.т.д. Если
0(а mod т) = <р(т), (2.309)
то а называется первообразным корнем по модулю т.
Следствие 1. Если а - первообразный корень по модулю т, то
- приведенная система вычетов по модулю т. Действительно, числа
а0, а1, а2, ....аУ-1 попарно несравнимы по модулю т, кроме того, они взаимно просты т.
Следствие 2. Если а - первообразный корень по простому модулю р, то система
а0, а1, а2, ...,ар~2 образует приведенную систему вычетов по модулю р.
Теорема 2.65
Если
0(amodm) = к, ( 2.310)
ап = l(modrri), (2.311)
то п кратно к.
Доказательство. Произведем деление чисел п и к
n = kq + r, 0<г<к (2.312)
Докажем, что г = 0.
По условию
ап = 1 (mod m)
Тогда
akq+r = l(mod т) (2.313)
(ak)9 ? ar = 1 (mod m) (2.314)
Но если г Ф 0, to ar 1 (mod m).
Получили противоречие, следовательно, г = 0.
Ч.т.д.
Следствие 1. Пусть а Є Z, р Є N, тогда порядок числа а по модулю р является делителем <р(т).
Следствие 2. Порядок числа а по простому модулю р является делителем р — 1.
|
Теорема 2.66 Пусть |
Q(amodm) = к, |
(2.315) |
|
тогда сравнения |
||
|
akl = ak2(mod т) |
(2.316) |
|
|
эквивалентны. |
кг = k2(modk~) |
(2.317) |
|
Доказательство. Докажем, что если верно сравнение |
||
|
то верно и сравнение |
akl = ак2 (mod m), |
|
|
Пусть |
kt = k2(mod к). |
|
|
akl = ak2(mod т)(к± > k2}. |
(2.318) |
|
Так как ак2 и т взаимно просты, то
а**"*’ = і (mocj m) (2.319)
но так как если к = 6(amodm) и ат = 1 (modni), то п кратно к, получаем, что разность кг — к2 кратно к, то есть кг = k2(modk').
Обратно, пусть верно сравнение
fci = k2(mod к)
тогда верно, что
ki~ к2 = kq, q Е Z. (2.320)
Таким образом,
afci-k2 = aqk = (tzk)Q = 1 (mod m). (2.321)
Получим, что
afci-fc2 = і (mod m). (2.322)
Умножим это сравнение на ак2:
(ак1~к2>) ? ак2 = ak2(mod m) акі-к2+к2 = ак2 (mod т)
akl = ak2(modm). (2.323)
Ч.т.д.
Следствие. Если а - первообразный корень по простому модулю р, то сравнения
ак1 = ak2(mod р)
кг = k2(mod (р — 1)) (2.324)
эквивалентны между собой.
Заметим, что если т - составное число, то в большинстве случаев первообразных корней по модулю т не существует.
