Учебник + задачник АП Ильиных

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

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

Подставив x = xn−2, получим d(xn−2 − xn−1) ≡ 0 (mod p). Тогда d(xn−2 − xn−1) ... p. При этом (xn−2 − xn−1) 6... p, так как решения xn−2 и xn−1 различны, Тогда d ... p.

Поднимаясь выше, получим, что b(x0 − x1) ... p, т.е. b ... p. На последнем шаге вместо x подставим xn. Получим a ... p.

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

a0, a1, . . . , an из левой части делятся на p. Теорема доказана.
ТЕОРЕМА 12.2 (Д. Вильсон) Если p – простое число, то
(p − 1)! + 1 ≡ 0 (mod p).	(12.11)

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

h i

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

При вычитании члены xp−1 взаимно уничтожаются. Поэтому это сравнение имеет степень не выше p − 2. Нетрудно проверить, что числа " 1, 2, 3, . . . , p − 1 является решениями данного сравнения. Поэтому число решений сравнения больше его степени. По предыдущей теореме все коэффициенты многочлена f(x) делятся на p.

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

(−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), что и нужно. Теорема доказана.

61

Решение сравнений по произвольному модулю. Пусть f(x) – многочлен с целыми коэффициентами. Рассмотрим сравнение

f(x) ≡ 0 (mod m).

(12.12)

Представим модуль m в виде произведения m = m1m2 . . . mk попарно взаимно простых сомножителей. Поэтому (mi, mj) = 1 при i 6= j.

ТЕОРЕМА 12.3. Сравнение (12.12) равносильно системе сравнений

f(x) ≡		0	(mod m2)	(12.13)
	f(x)	0	(mod m1)
	. . .≡
f(x) ≡ 0			(mod mk).

Доказательство. Пусть x0 – произвольное решение сравнения (12.12).

Тогда f(x0) ≡ 0 (mod m). Имеем m ... mi для всех i = 1, 2, . . . , k. Поэтому f(x0) ≡ 0 (mod mi) и x0 – решение системы сравнений (12.13).

Обратно, пусть x0 – решение системы (12.13). Тогда f(x0) ≡ 0 (mod mi) для всех i = 1, 2, . . . , k. Обобщая свойство сравнений 6, получим: если выполняются сравнения a ≡ b (mod mi) по взаимно простым модулям m1, m2, . . . , mk, то верно сравнение a ≡ b (mod m) для m = m1m2 . . . mk. Следовательно, верно сравнение f(x0) ≡ 0 (mod m). Теорема доказана.

Приведем способ решения сравнения (12.12). Вначале найдем каноническое разложение модуля m. Получим m = pα1 1 pα2 2 . . . pαk k . По предыдущей теореме вместо сравнения (12.12) запишем систему сравнений

f(x)		0	(mod p1α1 )
f(x)	≡	0	(mod p2α2 )		(12.14)
. . .	≡
		0	αk	).
f(x) ≡			(mod pk

Решим каждое из сравнений в (12.14) и получим системы вида

x	x1	(mod p1α1 )
x	≡ x2	(mod p1α2 )		(12.15)
	≡. . .
		αk	).
x ≡ xk		(mod p1

Способ решения системы сравнений первой степени уже рассмотрен.

62

Следовательно, мы свели задачу о решении сравнения (12.12) к решению более простого сравнения вида

f(x) ≡ 0 (mod pα).

(12.16)

Решение данного сравнения сведем к решению сравнения по простому модулю

f(x) ≡ 0 (mod p).

(12.17)

Ясно, что произвольное решение сравнения (12.16) является решение сравнения (12.17). Предположим, что каким-либо способом (например, подбором) найдено решение x¯0 сравнения (12.17). Тогда числа x класса x¯0 имеют вид

x = x0 + pt

(12.18)

и являются решениями сравнения (12.17) при любом t Z. Будем подбирать число t так, чтобы выполнялись сравнения f(x) ≡ 0 (mod p2), затем f(x) ≡ 0 (mod p3), . . . , и, наконец, f(x) ≡ 0 (mod pα).

Разложим многочлен f(x) по степеням x − x0 с целыми коэффициентами по схеме Горнера или по формуле Тейлора

f(x) = f(x0) +	f0	(x0)		(x − x0) + · · · +	f(n)(x0)		(x − x0)n.	(12.19)
		1!			n!

Подставим в это разложение x − x0 = pt. Мы рассматриваем сравнение f(x) ≡ 0 (mod p2) по модулю p2. Поэтому третий и последующие числа в правой части (12.19), кратные p2, можно заменить на 0. Получим

f(x0) + ptf0(x0) ≡ 0 (mod p2).

(12.20)

Ограничимся далее случаем, когда число k = f0(x0) не делится на p. Так как f(x0) ... p, то f(x0) = pb, где b Z. Сократив (12.20) на p, получим сравнение первой степени b + tk ≡ 0 (mod p) с единственным решением t1. Тогда t = t1 + pt2 для любого t2 Z. Подставив в (12.18), получим x = x0 + pt = x0 + p(t1 + pt2) = x1 + p2t2 для некоторого x1 Z и любого t2 Z.

Добьемся затем условия f(x) ≡ 0 (mod p3). Для этого снова разложим многочлен f(x) по степеням x−x1 по формуле Тейлора, найдем ограничение на число t2 и т.д.

В итоге получим решение сравнения (12.16).

63

Пример. Решить сравнение
x4 + 5x3 + 2x2 − 3x − 8	≡ 0 (mod 27).	(12.21)
Решение. Имеем сравнение вида f(x)	≡ 0 (mod p3), где p	= 3 и

f(x) = x4 + 5x3 + 2x2 − 3x − 8. Вначале подбором решим сравнение

f(x) ≡ 0 (mod 3).

(12.22)

Подставим в это сравнение числа x из полной системы вычетов 0, 1, −1 по модулю 3. Получим

f(0)	= −8	6≡0	(mod 3),
f(1)	= −3	≡ 0	(mod 3),
f(−1)	= −7	6≡0	(mod 3).

Итак, сравнение (12.22) имеет единственное решение ¯. x0 = 1

Все числа, удовлетворяющие этому сравнению имеют вид x = 1 + 3t, где t Z. Найдем значения параметра t, для которых f(x) ≡ 0 (mod 9). Разложим f(x) по степеням x − x0 = x − 1 по формуле Тейлора (12.19), возьмем два первых члена, а остальную часть обозначим 9k. Получим

f(x) = f(1) +	f0(1)	(x − 1) + 9k ≡ 0 (mod 9).
	1!

Имеем

f(1) = −3, f0(1) = 20, x − 1 = 3t.

Получим −3 + 20 · 3t ≡ 0 (mod 9), 20 · 3t ≡ 3 (mod 9). Разделив на 3, получим 20 · t ≡ 1 (mod 3). Отсюда t ≡ −1 (mod 3), т.е. t = −1 + 3t1 для любого t1 Z. Тогда x = 1 + 3t = 1 + 3(−1 + 3t1) = −2 + 9t1.

Найдем значения параметра t1, для которого f(x) ≡ 0 (mod 27). Как и выше, разложим f(x) по степеням x − x1 = x + 2. Получим

f(x) = f(	−	2) +	f0(−2)	(x + 2) + 27m	≡	0 (mod 27).
		1!

Имеем

f(−2) = −18, f0(−2) = 17, x + 2 = 9t1.

Получаем −18 + 17 · 9t1 ≡ 0 (mod 27) и 17 · 9t1 ≡ 18 (mod 27). Разделив на 9, получим 17 · t1 ≡ 2 (mod 3). Отсюда t1 = 1 + 3t2 для любого t2 Z. Тогда x = −2 + 9t1 = −2 + 9(1 + 3t2) = 7 + 27t2, где t2 Z.

Ответ. Сравнение имеет единственное решение ¯. x = 7

64

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

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

ОПРЕДЕЛЕНИЕ 13.1. Наименьшее натуральное число δ с услови-

ем

aδ ≡ 1 (mod m)

(13.1)

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

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

1)	aδ ≡ 1	(mod m),	(13.2)
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) при 0 < δ < 6. Выясним такую возможность. Имеем

21 6≡1 (mod 7),

22 6≡1 (mod 7),

23 ≡ 1 (mod 7).

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

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

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

65

Доказательство. Обозначим
A = {k N | ak ≡ 1	(mod m)},
B = {k N | bk ≡ 1	(mod m)}.

По условию a ≡ b (mod m). Тогда ak ≡ bk (mod m) и, следовательно,

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

Поэтому A = B. Показатель δ1 числа a – наименьшее число в A, показатель δ2 числа b – наименьшее число в 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) из определения показателя в (13.2).

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

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

(13.3)

Доказательство. Пусть i ≡ j (mod δ). Переставляя i и j, можно считать i > j. Тогда i = j + δt, где t > 0. Отсюда

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.

66

Тогда
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. По свойству 2 получаем 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). Поэтому ϕ(m) . δ.

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

Доказательство. По определению показателя (13.2) нужно проверить

два условия
1)	(ab)δ1δ2	≡ 1	(mod m),
2)	(ab)k 6≡1		(mod m) для 0 < k < δ1δ2.
Проверим 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),

где 0 < k < δ1δ2.
Возведя сравнение (ab)k ≡	1 (mod m) в степень δ1, получим
akδ1 bkδ1 ≡ 1 (mod m). При этом akδ1	≡ (aδ1 )k ≡ 1k ≡ 1 (mod m).

67

	kδ1		.
Отсюда b		≡ 1 (mod m). Тогда по свойству (4) имеем kδ1	.	. Так как
			. δ2
(δ1, δ2) = 1, то		.
		.		(13.4)
		k . δ2.

Аналогично, возведя в степень δ2 сравнение (ab)k ≡ 1 (mod m), получим

.
.	(13.5)
k . δ1.

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

Из данного свойства непосредственно следует более общее свойство.

СВОЙСТВО 6 . Если по модулю m числа a1, a2, . . . , ak принадлежат соответственно показателям δ1, δ2, . . . , δk, причем показатели δ1, δ2, . . . , δk попарно взаимно просты, то число a = a1a2 . . . ak принадлежит показателю δ1δ2 . . . δk по модулю m.

Тем самым, показателем произведения a = a1a2 . . . ak является произведение показателей сомножителей.

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

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

1) (ak)l ≡ 1 (mod m),

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

По условию показатель числа a по модулю m равен kl. Поэтому имеем akl ≡ 1 (mod m). Отсюда получаем условие 1).

Условие 2) проверим методом от противного. Пусть

(ak)l1 ≡ 1 (mod m) для некоторого l1 N, где l1 < l.

Тогда akl1 ≡ 1 (mod m), т.е. at ≡ 1 (mod m) при t = kl1 N. Из неравенства l1 < l имеем kl1 < kl, т.е. t < kl. Итак, имеем сравнение

at ≡ 1 (mod m) при t N и t < kl.

По условию показатель числа a по модулю m равен kl. По второму пункту из определения показателя сравнение at ≡ 1 (mod m) при t < kl невозможно, противоречие. Потому условие 2) выполнено.

68

Лекция 14. Первообразные корни.

ОПРЕДЕЛЕНИЕ 14.1. Пусть a Z и (a, m) = 1. Число a называется первообразным корнем по модулю m, если его показатель по модулю m равен ϕ(m).

ПРИМЕР. Пусть m = 7. Рассмотрим числа 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

Ответ. Среди чисел 1, 2, 3, 4, 5, 6 ровно два числа являются первообразным корнем по модулю 7. Это числа a = 3 и a = 5.

По свойству показателей сравнимые числа имеют одинаковый показатель. Поэтому при нахождении первообразного корня по модулю m можно испытывать только по одному числу из класса вычетов, а сравнимые первообразные корни считать одним и тем же первообразным корнем. При этом проверяются числа только из классов, взаимно простых с модулем. Взяв в этих классах по одному числу, мы получим приведенную систему вычетов по модулю m. Установив, какие числа из нее являются первообразными корнями, мы найдем все первообразные корни по модулю m. Если m = 7, то можно испытать числа приведенной системы вычетов 1, 2, 3, 4, 5, 6, что мы уже сделали. Итак, по модулю m = 7 существует ровно два первообразных корня a = 3 и a = 5.

Рассмотрим теперь m = 8. Найдем первообразные корни по модулю 8. Имеем ϕ(m) = ϕ(23) = 23 − 22 = 4. Рассмотрим числа из приведенной системы вычетов 1, 3, 5, 7 по модулю 8. Укажем показатели этих чисел в следующей таблице

a	1	3	5	7
P (a)	1	2	2	2

Мы не обнаружили числа a с показателем ϕ(8) = 4. Поэтому не существует первообразного корни по модулю 8.

Возникает следующий вопрос. Для какого числа m существует первообразный корень по модулю m?

69

ТЕОРЕМА 14.1. Пусть m = p – простое число. Тогда существует первообразный корень по модулю m.

Доказательство. Рассмотрим числа 1, 2, . . . , p−1. Под каждым числом i выпишем его показатель ni по модулю p. Получим таблицу из двух строк

1 2	. . . p − 1	(14.1)
n1 n2	. . . np−1

Далее доказательство разбивается на несколько шагов.

Шаг 1. Рассмотрим n = [n1, n2, . . . , np−1] – наименьшее общее кратное чисел из второй строки таблицы. Покажем, что

1) n = p − 1 или 2) n < p − 1.

Любой показатель по свойству показателей 4 является делителем числа ϕ(p) = p − 1. Поэтому

.	.	.
.	.	.
p − 1 .	n1, p − 1 .	n2, . . . , p − 1 . np−1.

По свойству НОК число p − 1 делится на НОК чисел n1, n2, . . . , np−1, т.е.

p − 1 ... n.

Так как p − 1 ... n, то n 6 p − 1. Тогда n = p − 1 или n < p − 1, что и нужно.

Шаг 2. Покажем, что n = p − 1.

Для этого проверим, что второй случай, где n < p − 1, невозможен. Предположим противное, т.е. n < p − 1. Рассмотрим сравнение

xn ≡ 1 (mod p),

и подставим вместо x число i {1, 2, . . . , p − 1}. По свойству показателей 4 справедливо сравнение in ≡ 1 (mod p), поскольку число n делится на показатель ni числа i.

Итак, мы имеем p − 1 различных решений сравнения xn ≡ 1 (mod p). При этом p − 1 > n. По теореме 12.1 все коэффициенты многочлена f(x) = xn − 1 должны делиться на p. Однако −1 6... p, противоречие.

Итак, предположение n < p − 1 неверно, т.е. n = p − 1.

70