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

Запишем многочлен f(x) в виде
f(x) = a(x − x0)	· · · (x − xn−1)+
+b(x − x1) · · · (x − xn−1)+
+c(x − x2) · · · (x − xn−1)+		(10)
	· · ·

+d(x − xn−1)+ +e,

где целые коэффициенты a, b, c, d, . . . , e подберем следующим образом. Приравняем коэффициенты при xn в левой и правой частях из в (10). Полу-

чим a = a0.

Затем подбираем число b. Для этого вычислим коэффициент при xn−1 в правой части. Он является суммой уже заданного коэффициента b1 при xn−1 в первой строке, и искомого числа b во второй строке. Приравняем эту сумму к a1. Получим a1 = b1 + b, откуда b = b1 − a1.

Аналогично находим c, d, . . . , e.

Покажем теперь, что все числа a, b, c, . . . , e делятся на p. Подставим в (10) вместо переменной x решение xn−1. В правой части получим e, а левой части получим число, сравнимое с 0. Поэтому e ≡ 0 (mod p) и число e можно заменить на 0 в сравнении (10).

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

С учетом этого, подставив x = xn−2, получим d(xn−2 − xn−1) ≡ 0 (mod p).

Тогда d(xn−2 − xn−1) ... p. Учтем что решения xn−2 и xn−1 различны, т.е. xn−2 6≡ xn−1 (mod p) и (xn−2 − xn−1) 6... p. Из d(xn−2 − xn−1) ... p получаем d ... p.

Поднимаясь выше получаем делимость на p коэффициентов e, d, . . . , c, b. На последнем шаге вместо x подставляем xn, и получаем a ... p.

Итак, все числа a, b, . . . , c, d делятся на p. Тогда все коэффициенты в правой части из (10) делятся на p. Поэтому коэффициенты a0, a1, . . . , an из левой части делятся на p.

Теорема доказана.

ТЕОРЕМА 1 (Д. Вильсон) Если p —простое число, то

(p − 1)! + 1 ≡ 0 (mod p).

(11)

Доказательство. Пусть p = 2. Тогда вместо (11) получаем верное сравнение 2 ≡ 0 (mod 2). Далее считаем, что p > 2. Рассмотрим сравнение

h i

f(x) = (x − 1)(x − 2) . . . (x − (p − 1)) − (xp−1 − 1) ≡ 0 (mod p). (12)

При вычитании члены xp−1 взаимно уничтожаются. Поэтому это сравнение имеет степень не выше p − 2. Очевидно, что числа 1, 2, 3, . . . , p − 1 является

решениями этого сравнения. Поэтому число решений сравнения больше его

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

степени. По предыдущей теореме все коэффициенты многочлена f(x) делятся на p.

В частности, свободный член многочлена f(x) делится на p. Из (12) получаем вид свободного члена

(−1)(−2) . . . (−(p − 1)) + 1 = (−1)p−1(p − 1)! + 1 = (p − 1)! + 1.

При этом учтено, что p > 2, т.е. p − 1 —четно и (−1)p−1 = 1. Получили (p − 1)! + 1 ... p, т.е. (p − 1)! + 1 ≡ 0 (mod p), что и нужно. Теорема доказана.

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

Лекция 13. Показатель числа. Свойства показателя.

Пусть задан некоторый модуль m и (a, m) = 1. Тогда существует натуральное число δ со свойством aδ ≡ 1 (mod m).

В качестве δ может выступать, например, ϕ(m), так как по теореме Эйлера aϕ(m) ≡ 1 (mod m). Также, очевидно, и числа 2ϕ(m), 2ϕ(m), . . . можно взять

в качестве δ.
ОПРЕДЕЛЕНИЕ 1 Наименьшее натуральное число δ с условием
aδ ≡ 1 (mod m)	(1)

называется показателем числа a по модулю m.

То же самое можно выразить в другом виде.

Натуральное число δ является показателем числа a по модулю m, если выполнены следующие два условия

1)aδ ≡ 1 (mod m),

2)ak 6≡1 (mod m) для всех k N, где k < δ.

Если показатель числа a по модулю m равен δ, то говорят, что a принадлежит показателю δ по модулю m.

ПРИМЕР. Найти показатель числа a = 2 по модулю m = 7.

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

По теореме Ферма имеем 26 ≡ 1 (mod 7). Может оказаться, что наряду с 26 ≡ 1 (mod 7), имеется сравнение 2δ ≡ 1 (mod 7) при δ < 6, δ N. Выясним такую возможность. Имеем

21 6≡1 (mod 7),

22 6≡1 (mod 7),

23 ≡ 1 (mod 7).

Поэтому 3 — наименьшее натуральное число n с условием 2δ ≡ 1 (mod 7) и показатель числа 2 по модулю 7 равен 3.

Свойства показателя

СВОЙСТВО 1 Если числа a и b сравнимы между по модулю m, то они имеют один и тот же показатель по модулю m.

Доказательство. Пусть a ≡ b (mod m). Тогда ak ≡ bk (mod m) для всех k N. Поэтому

ak ≡ 1 (mod m) bk ≡ 1 (mod m).

(2)

Обозначим A = {k N | ak ≡ 1 (mod m)} и B = {k N | bk ≡ 1 (mod m)}. По (2) A = B.

Показатель δ1 числа a — наименьшее число в A, показатель δ2 числа a —

наименьшее число в B. Так как A = B, то δ1 = δ2, что и нужно.

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

Поскольку все числа одного класса сравнимы между собой по модулю m, то у них один и тот же показатель δ. Считаем это число δ также и показателем данного класса.

СВОЙСТВО 2 Пусть показатель числа a по модулю m равен δ. Тогда

числа

a0, a1, . . . , aδ−1

попарно несравнимы по модулю m.

Доказательство. Предположим противное. Тогда ai ≡ aj (mod m), где 0 6 i < j 6 δ − 1. Учитывая (ai, m) = 1, разделим сравнение на число ai. Тогда aj−i ≡ 1 (mod m). Обозначив j − i = k, имеем

ak ≡ 1 (mod m), где k N и k < δ.

Это противоречит пункту 2) в определении показателя.

СВОЙСТВО 3 Пусть a принадлежит показателю δ по модулю m. Тогда

ai ≡ aj (mod m) i ≡ j (mod δ).

(3)

Доказательство. Пусть i ≡ j (mod δ). Тогда i = j + δt, где t Z. Отсюда

ai = aj+δt = aj(aδ)t ≡ aj1t = aj (mod m).

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

Обратно, пусть ai ≡ aj (mod m). Докажем, что i ≡ j (mod δ). Нужно проверить, что i и j имеют одинаковые остатки от деления на δ. Обозначив эти остатки через r1 и r2, получим

i = δq1 + r1, где 0 6 r1 6 δ − 1 и j = δq2 + r2, где 0 6 r2 6 δ − 1.

Тогда

ai = aδq1			+r1	= (aδ)q1 ar1	≡ ar1	(mod m),
aj = aδq2			+r2	= (aδ)q2 ar2	≡ ar2	(mod m).
Отсюда с учетом ai ≡ aj	(mod m) имеем ar1 ≡ ar2 (mod m), где r1 и r2 взяты
из 0, 1, . . . , δ − 1. По свойству 1 r1 = r2. Получили i ≡ j (mod δ).
СВОЙСТВО 4 Пусть показатель числа a по модулю m равен δ. Тогда
	k					.
a		≡ 1 (mod m)				.
						k . δ.

В частности, δ числа a является делителем числа ϕ(m).

Доказательство. По предыдущему свойству ak ≡ a0 (mod m) k ≡ 0 (mod δ),

			k			.
т.е. a				≡ 1 (mod m)		.
						k . δ.
	По теореме Эйлера aϕ(m). ≡ 1 (mod m), т.е. aϕ(m) ≡ a0 (mod m). Тогда
ϕ	m					.
		)		≡ 0	(mod δ) т.е. ϕ(m) . δ.
(					След Пред Стр Начало Оглавление Обратно Меню Экран Выход

СВОЙСТВО 5 Если число a принадлежит показателю δ1 по модулю m, число b принадлежит показателю δ2 по модулю m, причем (δ1, δ2) = 1, то число ab принадлежит показателю δ1δ2.

Доказательство. Нужно проверить два условия

1)(ab)δ1δ2 ≡ 1 (mod m),

2)(ab)k 6≡1 (mod m) для k = 1, 2, . . . , δ1δ2 − 1.

Проверим 1). Имеем

(ab)δ1δ2 = aδ1δ2 bδ1δ2 = (aδ1 )δ2 (bδ2 )δ1 ≡ 1δ2 1δ1 = 1 (mod m).

Установим 2) методом от противного. Допустим (ab)k ≡ 1 (mod m), где k

N и k < δ1δ2.	≡ 1
Возведя сравнение (ab)k ≡ 1 (mod m) в степень δ1, получим akδ1 bkδ1
(mod m). С учетом aδ1 ≡ 1 (mod m) имеем bkδ1 ≡ 1 (mod m).
.
.
По свойству (4) kδ1 . δ2. Так как (δ1, δ2) = 1, то
.
.	(4)
k . δ2.
Аналогично, возведя в степень δ2 сравнение (ab)k ≡ 1 (mod m), получим
.
.	(5)
k . δ1.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Из (4) и (5) с учетом (δ1, δ2) = 1, получаем k ... δ1δ2. Поэтому k > δ1δ2. Однако, у нас k < δ1δ2, противоречие. Значит верно 2).

СВОЙСТВО 6 Пусть число a принадлежит показателю kl. Тогда показатель числа ak равен l.

Доказательство самостоятельно.

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

Лекция 14. Первообразные корни.
ОПРЕДЕЛЕНИЕ 1 Число a называется первообразным корнем по мо-
дулю m, если его показатель по модулю m равен ϕ(m).
ПРИМЕР. Пусть m = 7. Рассмотрим числа a = 1, 2, 3, 4, 5, 6. Какие из дан-
ных чисел являются первообразными корнями по модулю 7?
Показатель числа a будем обозначать P (a). Вычислим показатели чисел
1, 2, 3, 4, 5, 6 и занесем их во вторую строку следующей таблицы.
a	1	2	3	4	5	6
P (a) 1 3 6 3					6	2
Ответ. Существует ровно два первообразных корня a = 3 и a = 5 по модулю
7.
Рассмотрим теперь m = 8 и попробуем найти первообразные корни по мо-
дулю 8. Имеем ϕ(m) = ϕ(8) = ϕ(23) = 23 − 22 = 4. Нужно рассмотреть
a {0, 1, . . . , 7} с условием (a, 8) = 1. Получим {1, 3, 5, 7}. Укажем показатели
этих чисел в следующей таблице.
a		1	3	5	7
P (a) 1 2 2					2
След Пред Стр Начало Оглавление Обратно Меню Экран Выход