Учебник по теории чисел Ильиных АП

Мы не обнаружили числа a с показателем 4. Поэтому не существует первооб-
разного корни по модулю 8.
Возникает следующий вопрос. Для какого модуля m существует первооб-
разный корень?
ТЕОРЕМА 1 Пусть m = p —простое число. Тогда существует перво-
образный корень по модулю m.
Доказательство. Рассмотрим числа 1, 2, . . . , p − 1, образующие приведенную
систему вычетов по модулю m = p. Под каждым из этих чисел выпишем его
показатель по модулю p. Получим
1	2	· · ·	p − 1
n1 n2 · · ·			np−1
Рассмотрим наименьшее общее кратное чисел n1, . . . , np−1
n = [n1, n2, . . . , np − 1].
По свойствам показателя показатели чисел по модулю p являются делите-
лями ϕ(p) = p − 1. Поэтому p − 1 кратно каждому из чисел n1, n.2, . . . , np−1. По
			.
свойству НОК число p − 1 кратно n = [n1, . . . , np−1], т. е. p − 1 . n.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход

		.
		.
Так как p−1 . n, то 1) p−1 = n или 2) p−1 > n. Покажем, что второй случай
невозможен. Предположим противное, т.е. p − 1 > n. Рассмотрим уравнение
xn ≡ 1 (mod p).
Любое из чисел i {1, 2 . . . , p − 1} удовлетворяет этому сравнению. Дей-
	ni				.	n		ni		t
ствительно, i		≡ 1 (mod p)			.		= (i		)		≡ 1 (mod p).
			и n . ni, т.е. n = nit. Тогда i
Получили p − 1 решений сравнения xn ≡ 1 (mod p), где p − 1 > n. Тогда
				n							.
все коэффициенты f(x) = x											.
					− 1 должны делиться на p. Однако, −1 6. p,
противоречие.
Итак,
		n = [n1, n2, . . . , np−1] = p − 1.
Запишем каждое из чисел n1, n2, . . . , np−1 в каноническом виде.
Применим правило вычисления НОК по каноническому разложению. Если
				a = p1α1 p2α2 · · · pkαk ,
то				b = p1β1 p2β2 · · · pkβk ,
		[a, b] = p1max(α1,β1)p2max(α2,β2) · · · pkmax(αk,βk).
											(1)
Поэтому, если [a, b] = · · · paαi			· · · , то piαi было множителем в каноническом раз-
ложении для a или в каноническом разложении для b. То же самое верно для
		След Пред Стр Начало Оглавление Обратно Меню Экран Выход

НОК нескольких чисел.

α1

α2

αk

и возьмем

сомножитель

αi. Тогда

αi было со-

Обозначим n = p1

p2

· · · pk

αi

pi

pi

множителем в некотором nj, то есть nj

= pi

t. Показателем числа j является

nj = piαit. Тогда показателем числа jt

по свойству 6 из предыдущей лекции

является число pαi.

i

разложения

α1

α2

αk мы нашли число,

Итак, для канонического

αi

n = p1

p2

· · · pk

показатель которого равен в точности pi

. Поэтому существуют числа a1 с по-

казателем p1α1 , a2 с показателем p2α2 , . . . , ak с показателем pkαk . По свойству 5

показателем числа a = a1 · · · ak будет число p1α1 p2α2 · · · pkαk

= n.

Итак, мы нашли число a с показателем n = p−1. Поэтому число a является

первообразным коренем по модулю p. Теорема доказана.

ТЕОРЕМА 2 Первообразный корень по модулю m существует тогда

и только тогда, когда выполнен один из случаев

m = pα,

где

p—нечетное простое число;

m = 2pα,

где

p—нечетное простое число;

m = 4.

Доказательство опускается.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

ТЕОРЕМА 3 Пусть γ —первообразный корень по модулю p. Тогда чис-
ла
γ0, γ1, γ2, . . . , γp−2.	(2)
образуют приведенную систему вычетов по модулю p.
Доказательство. Так как γ — первообразный корень по модулю p, то (γ, p) =
1. Отсюда (γi, p) = 1 и p − 1 чисел из (2) взаимно просты с p. Поэтому, они
взяты из p − 1 классов, взаимно простых с модулем p.
По свойству показателей p − 1 чисел из (2) попарно несравнимы по моду-
лю p и, следовательно, взяты из разных классов. Так как существует ровно
p − 1 классов, взаимно простых с модулем p, то числа из (2) взяты по одно-
му из каждого класса, взаимно простого с модулем p. Поэтому они образуют
приведенную систему вычетов по модулю p.
Теорема доказана.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 15. Индексы. Свойства индексов.

Введем понятие индекса, во многом аналогичное понятию логарифма. Рассмотрим модуль m = p, где p — простое число. По теореме (1) существует первообразный корень γ по модулю p. Тогда показатель числа γ равен p − 1.

Рассмотрим p − 1 чисел

γ0, γ1, γ2, . . . , γp−2. (1)

По теореме 3 из предыдущей лекции они образуют приведенную систему вычетов по модулю p.

Пусть a Z и a не делится на p. Тогда a взаимно просто с p и содержится в некотором классе взаимно простом с модулем m. В этом же классе содержится ровно одно число из приведенной системы вычетов (1). Поэтому существует такое число k, что a ≡ γk (mod p). Будем называть далее число γ основанием системы индексов.

ОПРЕДЕЛЕНИЕ 1 Если

a ≡ γk (mod p),

(2)

где k > 0, то число k называется индексом числа a по модулю p при основании γ.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Таким образом индекс числа — это показатель степени, в которую нужно возвести основание, чтобы получить число, сравнимое с данным. Обозначение индекса — indγ a или просто ind a, если ясно, о каком основании идет речь. Поэтому

γind γ a ≡ a (mod p).

(3)

Аналогично определяется индекс по модулю m в случае когда m = pα, m = 2pα, где p > 2 –простое ; или m = 4. Однако мы ограничимся далее случаем простого модуля.

Определение индекса аналогично определению логарифма, однако индекс определен неоднозначно. Допустим, что для некоторого числа k имется запись k = indγ a. Это означает a ≡ γk (mod p). Рассмотрим возможность другой записи a ≡ γk1 (mod p). Имеем

γk ≡ γk1 (mod p) k ≡ k1 (mod p − 1).

Поэтому любое число k1 > 0, сравнимое с индексом по модулю p − 1, также индекс данного числа a. Обычно, в качестве индекса будем указывать число

0, 1, 2, . . . , p − 2.

ПРИМЕР. Пусть m = 7. В качестве основания γ можно взять γ = 3 или γ = 5. Пусть основание γ = 5. Найдем индекс числа 5 при основании γ.

Вычислим число x с условием 5x ≡ 4 (mod 7)). Получим x = 2.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Ответ ind 54 = 2.

Укажем следующие свойства индексов.

ТЕОРЕМА 1 Пусть γ —первообразный корень по модулю m. Тогда выполнены следующие утверждения

1)	indγ (a1a2 · · · ak) ≡ indγ a1 + indγ a2 + · · · + indγ ak (mod p − 1),
2)	indγ ak ≡ k · indγ a (mod p − 1).

Аналогичное свойство справедливо для логарифма: логарифм от произведения равен сумме логарифмов, показатель степени выносится за знак логарифма. В нашем случае знак равенства « = » заменяется на знак сравнимости

« ≡ ».

Доказательство. Проверим вначале свойство 1). По определению индекса

имеем.	≡ a1
γind γ a1		(mod p)
γind γ a2	≡ a2	(mod p)	(4)
· · ·
γind γ ak ≡ ak		(mod p)
Умножимв почленно данные сравнения, получим
γind γ a1+ind γ a2+···+ind γ ak ≡ a1a2 · · · ak (mod p).			(5)
След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Это сравнение означает, что indγ a1 + indγ a2 + · · · + indγ ak есть индекс числа a1a2 · · · ak по основанию γ, что и утверждается в пункте 1).

Свойство 2) непосредственно следует из 1). Возьмем

a1 = a, a2 = a, . . . , ak = a.

Получим indγ ak ≡ k · indγ a (mod p − 1). Теорема доказана.

Ввиду того, что индексы находят применение в решении сравнений, имеются таблицы индексов для определенных значений p. Впервые таблицы индексов для всех простых модулей p 6 200 составил в 1837 г. академик М.В. Остроградский.

Найдем таблицу индексов по модулю p = 13 при основании γ = 2. Для этого возводим основании γ = 2 в степень с показателем 0, 1, . . . , 11. Получаем

20 ≡ 1 (mod 13), 21 ≡ 2 (mod 13), 22 ≡ 4 (mod 13), 23 ≡ 8 (mod 13), 24 ≡ 3 (mod 13), 25 ≡ 6 (mod 13), 26 ≡ 12 (mod 13), 27 ≡ 11 (mod 13), 28 ≡ 9 (mod 13), 29 ≡ 5 (mod 13), 210 ≡ 10 (mod 13), 211 ≡ 7 (mod 13).

После этого заполняем таблицу индексов по модулю 13

N	0	1	2	3	4	5	6	7	8	9
0		0	1	4	2	9	5	11	3	8
1	10	7	6

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Чтобы найти, например, индекс числа 12, рассматриваем строку 1 и столбец 2. На пересечении находим индекс, равный 6.

Если известен индекс числа, то само число можно найти по следующей таблице

I	0	1	2	3	4	5	6	7	8	9
0	1	2	4	8	3	6	12	11	9	5
1	10	7

Эта таблица по индексу восстанавливает число. Допустим, индекс некоторого числа x равен 7. По таблице находим x = 11.

Решение сравнений с помощью таблицы индексов.

Рассмотрим три вида сранений, которые можно решить с помощью таблицы индексов.

ПРИМЕР 1. Решить сравнение

5x ≡ 2 (mod 13).

(6)

Числа 5x и 2 сравнимы по модулю 13 тогда и только тогда, когда их индексы сравнимы по модулю 12.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Поэтому приравниваем индексы от 5x и 2.

ind (5x) ≡ ind 2	(mod 12),
ind 5 + ind x ≡ ind 2	(mod 12).

Подставляя значения индексов из таблицы индексов, получим

9 + indγ x ≡ 1	(mod 12),
ind x ≡ −8	(mod 12),
ind x ≡ 4	(mod 12).

По полученному индексу 4 находим x. Ответ x ≡ 3 (mod 13).

Данное сравнение можно было решить и другими методами, однако два сле-

дующих сравнения мы сможем решить только с помощью индексов.
ПРИМЕР 2. Решить сравнение
5x7 ≡ 1 (mod 13).	(7)

След Пред Стр Начало Оглавление Обратно Меню Экран Выход