RUDN-I

7.3. Кольцо и поле вычетов

131

Докажем 2).

a

c

= ab−1

cd−1 = adb−1d−1

bcb−1d−1 = (ad

bc)(bd)−1

=

ad ± bc

.

b ± d

±

±

±

ru

bd

Свойства 3), 4) доказываются аналогично (сделайте это самостоятельно).

7.3. Кольцо и поле вычетов	.
matematem
§ 1. Классы вычетов по модулю числа p

Теорема 1. (о делении с остатком)

Пусть m R, p > 0. Тогда существуют числа k Z (частное) и r [0, p) (остаток), такие что

m = pk + r.

(1)

Доказательство. При p > 0 отрезки вида [pk, p(k + 1)) заполняют всю числовую ось, т.е.

[pk, p(k + 1)) = R.

k Z

Значит, для любого m R найдется k Z, такое что m [pk, p(k + 1)), т.е. pk ≤ m < p(k + 1) (см. рис. 1).

				p								p
(	qz			}|			{pkqz					}|r		{ +q			1)	-	Рис. 1
			1)										(
						.							.
						..							..
						.							.
						.							.
p k	−										m		p k
Обозначим r = m − pk, тогда r [0, p) и верно равенство (1).
www
Следствие. Пусть.в условиях теоремы 1 m Z, p N, p > 1. Тогда в
(1) остаток r {0,			1,	. . . ,		p − 1}.

Действительно, в условиях следствия r = m−pk — целое число, r [0, p), т.е. r {0, 1, . . . , p − 1}.

Пусть p N, p > 1.

Определение 1. Числа m, n Z называются сравнимыми по модулю p, если при делении на p они дают одинаковые остатки, т.е. если m−n кратно p:

m − n = pk, k Z.

132	Тема 7. Кольца и поля
Обозначение: m ≡ n(mod p). Итак,
m ≡ n(mod p)	m − n = pk, k Z.
			ru
Лемма 1. Для m, n Z введем бинарное отношение R:
(m, n) R	m ≡ n(mod p).	.		(2)
matematemZp = {C0, C1, . . . , Cp−1}.				(4)

Это отношение R является отношением эквивалентности (т.е. оно рефлексивно, симметрично и транзитивно).

Упражнение. Доказать это утверждение (см. упражнение 7.4). Соответствующие классы эквивалентности объединяют целые числа, имеющие одинаковые остатки при делении на p. Эти классы эквивалентности имеют вид (см. следствие из теоремы 1)

Cr = {m = pk + r, k Z}, r = 0, 1, . . . , p − 1.

(3)

Итак, в Cr входят все числа m Z, остаток от деления которых на p равен r.

Определение 2. Классы эквивалентности C0, C1, . . . , Cp−1 вида (3) называются классами вычетов по модулю p.

Через Zp = Z | R обозначим фактор-множество множества Z по отношению эквивалентности R (2), т.е. совокупность всех классов эквивалентности. Таким образом,

1)Суммойwwwчисел m1, m2 Z по модулю числа p называется остаток от деления m1 + m2 на p.

2)Произведением чисел m1, m2 Z по модулю числа p называется.

остаток от деления m1m2 на p.

7.3. Кольцо и поле вычетов						133
p		p
Обозначения: m1 m2 ≡ m1 m2;		m1 m2 ≡ m1 m2.
Итак, если имеем представление
m1 + m2 = pk + r,	k Z, r {0,		1, . . . , p − 1},			(5)
то				.
опр.		(5)	− pk.			(6)
m1 m2	= r = m1 + m2
Числа 0, 1 играют рольmatematemнуля и единицы в этих операциях.
Аналогично, если	l Z,				ru	(7)
m1m2 = pl + s,		s {0, 1, . . . , p − 1},
то	опр.	(7)
m1 m2 = s = m1m2 − pl.						(8)

В ЭВМ особенно важную роль играют операции сложения и умножения чисел по модулю числа 2. Отметим, что

2 2 2

0 0 = 0; 0 1 = 1; 1 1 = 0;

2 2 2

0 0 = 0; 0 1 = 0; 1 1 = 1.

Лемма 2. Операции сложения и умножения целых чисел по модулю числа p N, p > 1 обладают свойствами коммутативности, ассоциативности и связаны законом дистрибутивности:

1) m1 m2 = m2 m1, m1 m2 = m2 m1, m1, m2 Z;			(9)
2) m1 (m2 m3) = (m1 m2) m3,		m1, m2, m3 Z;
m1 (m2 m3) = (m1 m2) m3,		m1, m2, m3 Z;	(10)
	.		(11)
3) (m1 m2) m3 = (m1 m3) (m2 m3), m1, m2, m3 Z.
www

Доказательство. 1) Коммутативность сложения и умножения целых чисел по модулю p сразу следует из коммутативности обычных операций сложения и умножения чисел.

2) Остальные свойства доказываются по единой схеме. Мы проведем доказательство одного из них: ассоциативности умножения по модулю p. Обоснование двух других свойств предлагается провести самостоятельно (см. упражнение 7.6). Итак, докажем равенство (10). Согласно определению (см. (7), (8)) существует l1 Z, такое что

m1 m2 = m1m2 − pl1.

(12)

134		Тема 7. Кольца и поля
По той же причине, существует l2 Z, такое что
	(m1 m2) m3 = (m1 m2)m3	− pl2.			ru	(13)
Подставим (12) в (13) и получим
	(m1 m2) m3 = (m1m2)m3 − p(m3l1 + l2),
т.е.	matematem		l .	Z.		(14)
Аналогично,	(m1 m2) m3 = (m1m2)m3 − pl,
	m2 m3 = m2m3 − pk1, k1 Z					(15)
	m1 (m2 m3) = m1(m2m3) − pk,		k Z.

Поскольку обычное умножение чисел ассоциативно, то

(m1m2)m3 = m1(m2m3).

Поэтому, вычитая (15) из (14), получим

(m1 m2) m3 − m1 (m2 m3) = p(k − l), k, l Z.

Итак, левая и правая части (10) могут отличаться лишь на число, кратное числу p. Но обе они принадлежат множеству {0, 1, . . . , p − 1}. Следовательно, они совпадают. Равенство (10) доказано.

Замечание 1. Лемма 2 показывает, что операции сложения и умножения по модулю p наследуют обычные свойства сложения и умножения

чисел. Они обладают, однако, и некоторыми необычными свойствами.
Лемма 3. Пусть p. N, p > 1.		m, n N, то
1)	Если p — составное число: p = mn; m, n > 1,
	m n = 0.	(16)
2)	Если m {1, . . . , p − 1}, то число p − m {1, . . . , p − 1} является
"противоположным к m" , т.е.
	m (p − m) = 0.	(17)

Действительно,wwwобе формулы (16), (17) сразу следуют из определений (см. (7)—(8), (5)—(6)).

7.3. Кольцо и поле вычетов

135

Лемма 4. Пусть p N, p > 1 — простое число. Для каждого числа

r E ≡ {1, . . . , p − 1}			(18)
найдется (причем единственное) q E, такое что r q = 1.
		ru
Для доказательства леммы 4 нам потребуется следующий простой ре-
зультат о делимости целых чисел.	.
Утверждение.
1) Число n N делится на простое число p тогда и только тогда, когда

в его разложении на простые множители n = n1n2 . . . nk хотя бы один из множителей равен p.

2) Если r, q N и не делятся на простое число p, то и qr не делится на p.

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

1.Часть 1) очевидна, поскольку простое число p не может быть "составлено" из множителей, отличных от p и 1.

2.Выведем часть 2) из 1). Разложим r и q на простые множители:

r = r1r2 . . . ri, q = q1q2 . . . qj.

Поскольку r и q не делятся на p, то, согласно части 1) ни один из этих простых множителей не равен p. Для qr получаем разложение на простые множители

qr = q1q2 . . . qjr1r2 . . . ri,

в которое p не входит. Снова применим часть 1) утверждения и получим, что qr не делится на p.

Доказательство леммы 4. 1) Рассмотрим отображение f, заданное фор-
мулой (см. (18))	.	matematem
		f(q) = q r, q E.
Заранее ясно, что
www

f(q) {0} E = {0, 1, . . . , p − 1}.

Покажем, что f(q) ≠ 0, q E. Поскольку q, r E не делятся на p и p — простое число, то по лемме 1 qr не делится на p. Значит, q r ≠ 0,

т.е. f(q) ̸= 0, q E. Итак,
f : E → E; f(q) = q r, q E.	(19)

136	Тема 7. Кольца и поля
2) Покажем теперь, что отображение f	(19) инъективно. Равенство

f(q1) = f(q2) означает, что q1 r = q2 r, т.е. q1r и q2r имеют оди-

наковые остатки при делении на p. Допустим, что q1	̸= q2, например,
	ru

q2 > q1. Тогда q = q2 − q1 E, причем qr делится на p без остатка. Значит, f(q) = q r = 0, где q = q2 −q1 E. Это противоречит доказанному

на 1-ом шаге. Итак, допущение неверно, т.е. f(q1) = f(q2) q1 = q2.
Следовательно, f : E → E инъективно.	.
matematemm + n = p(k + l) + q + r,

3) Согласно результату упражнения 2.5 инъективное отображение f конечного множества E в себя является биекцией, т.е. обладает также свойством сюръективности: f(E) = E. Значит, существует, причем единственное число q E, такое что f(q) = 1 E, т.е. q r = 1.

§ 3. Кольцо и поле вычетов

Теперь мы можем можем определить операции сложения и умножения для классов вычетов по модулю числа p N, p > 1 (см. (3)—(4)). Чтобы обосновать корректность этого определения нам потребуется следующий результат.

Лемма 5. Пусть p N, p > 1, q, r {1, . . . , p − 1}. Для любых чисел m Cq, n Cr (см. (3)—(4)) справедливы включения

	m + n Cq r,	mn Cq r,	(20)
где q r, q r — сложение и умножение по модулю числа p.
Доказательство. Для m Cq, n Cr найдутся k, l Z, такие что
	m = pk + q,	n = pl + r.
Тогда,	.

m + n Cq r. Аналогично,

т.е. m +wwwn ≡ (q + r)(mod p). Значит, m + n и q + r имеют один и тот же остаток при делении на p, равный q r (см. определение 3). Поэтому

mn = (pk + q)(pl + r) = p(pkl + lq + kr) + qr,

т.е. mn ≡ qr(mod p). Значит, mn и qr имеют один и тот же остаток при делении на p, равный q r. Поэтому mn Cq r.

Доказанное предложение делает естественным следующее определение суммы и произведения классов вычетов.

7.3. Кольцо и поле вычетов

137

Определение 4. Пусть p N, p > 1, q, r {1, . . . , p − 1}. Сумму и произведение классов вычетов Cq и Cr введем по формулам

опр.	опр.	(21)
Cq + Cr = Cq r;	Cq · Cr = Cq r

Замечание 2. Естественность этого определения подтверждается тем, что суммы любых чисел m Cq и n Cr попадают в класс Cq r, а произведения — в класс Cq r (см. лемму 5).

2) Ассоциативность и коммутативностьmatematemумножения классов сразу следу-
Теорема 2. Множество Zp = {C0, C1, . . . , Cp−1} классовru	вычетов по
модулю числа p с введенными операциями суммы и произведения.		классов

вычетов образует коммутативное кольцо с единицей. Роль нуля в нем играет класс C0, роль единицы — класс C1.

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

1) Ассоциативность и коммутативность сложения классов сразу следуют из соответствующих свойств сложения чисел по модулю p. Например, при q, r, s {0, 1, . . . , p − 1}

(21)	(21)	=
Cq + (Cr + Cs) = Cq + Cr s	= Cq (r s)
	(21)	(21)
= C(q r) s = Cq r + Cs = (Cq + Cr) + Cs.
Далее,
(21)	= Cq, q {1, . . . , p − 1},
Cq + C0 = Cq 0

т.е. C0 играет роль нуля. Наконец, для любого q {1, . . . , p − 1} имеем, согласно (21) и (17)

(21)	(17)
Cq + Cp−q = Cq (p−q) = C0		,

так что Cp−q — противоположный класс для Cq. Итак, Zp есть абелева
группа относительно сложения (выполнена аксиома K1◦).
ет из соответствующих.	свойств умножения чисел по модулю p; например
(21)	(21)
Cq · (Cr · Cs) = Cq · (Cr s) = Cq (r s) =
	(21)	(21)
	= C(q r) s = Cq r · Cs	= (Cq · Cr) · Cs.

3) Закон дистрибутивности также выполнен, поскольку он выполнен для операций сложения и умножения чисел по модулю p:

(21)	(21)
Cq · (Cr + Cs) = Cq · Cr s = Cq (r s) =
www	(21)	(21)
	= C(q r) (q s) = Cq r + Cq s = Cq · Cr + Cq · Cs,

138	Тема 7. Кольца и поля
что и требовалось.
Итак, Zp есть коммутативное кольцо. При этом
C1 · Cq = Cq · C1 = Cq 1 = Cq, q {0, 1, . . . , p − 1},
т.е. C1 играет роль единицы в кольце Zp.
Замечание 3. Если p — составное число, т.е. p = mn, где m,				n
N; m, n > 1, то классы Cm и Cn являются делителями нуляruв Zp, посколь-
		.	(21)
			= Cm n	= C0
ку, согласно части 1 леммы 3, тогда m n = 0 и Cm · Cn
matematem

—нулевой элемент кольца, хотя m, n {2, . . . , p−1}, т.е. Cm ≠ C0, Cn ≠

C0.

Вывод. Кольцо Zp при составном p N содержит делители нуля и, следовательно, не является полем.

Теорема 3. Пусть p N — простое число. Тогда Zp является полем (его называют полем вычетов по простому модулю p).

Доказательство. Поскольку по теореме 2 Zp — коммутативное кольцо с единицей, достаточно проверить обратимость всех его ненулевых эле-

ментов, т.е. показать, что при r {1, . . . , p − 1} для класса Cr найдется обратный Cq, q {1, . . . , p − 1}, т.е. такой что Cr · Cq = C1

(единица кольца). Согласно лемме 4 для данного r найдется (причем единственное) число q {1, . . . , p − 1}, для которого r q = 1. Тогда

(21)

Cr · Cq = Cr q = C1, что и требовалось.

Замечание 4. Свойства поля Zp не похожи на свойства известных нам полей Q рациональных чисел или R — вещественных чисел. Например, в Zp сумма p единиц равна нулю:

C1 + C1			+ . . . + C1	= C	1					= C0.
	.					1	. . .		1
Говорят, что поле							p	}
	Z	p	имеет характеристику p.
					|		{z

7.4.wwwТеоретические упражнения к теме 7

7.1. В примерах из упражнения 6.1 с двумя операциями (сложения и умножения) разобрать вопросы о выполнении аксиом кольца (поля).

7.2. Пусть K — кольцо с единицей. Показать, что

1) если элемент кольца обратим, то обратный к нему единственный;

7.4. Теоретические упражнения к теме 7

139

2) нулевой элемент кольца необратим;

3) делители нуля в кольце необратимы;

4) множество G(K) всех обратимых элементов кольца образует мультипликативную группу.

7.3. 1) Рассмотреть пример кольца K = P (V ) всех подмножеств данного непустого множества V с операциями сложения и умножения множеств, определенными правилами:

A B = A B, A B = A ∩ B .

ru

(симметрическая разностьmatematemи пересечение множеств).

2) Показать, что P (V ) не образует кольца, если ввести в нем сложение множеств по правилу A B = A B (объединение множеств).

7.4. Пусть p N, p > 1. На множестве целых чисел введем бинарное отношение R сравнения чисел по модулю числа p:

(m, n) R m = n(mod p).

Показать, что R есть отношение эквивалентности (т.е. оно рефлексивно, симметрично и транзитивно).

7.5.На множестве K4 = {0, 1, 2, 3} введем операции сложения и умножения целых чисел по модулю числа 4. Проверить выполнение аксиом кольца, составить таблицы сложения и умножения (по модулю 4), для каждого числа найти противоположное, указать делители нуля. Для обратимых элементов кольца указать обратные элементы.

7.6.Показать, что операции сложения и умножения целых чисел по мо-

дулю числа p N, p > 1 обладает свойствами коммутативности, ассоциативности и связаны.законом дистрибутивности.0 1 p−1

www
Zp, если p — простое число) справедливо равенство
	p−1
	∑q	+ . . . + Cp−1
	Cq = C1		= C0.
	=1

x2 + 1 = 0

140

Тема 8. Поле комплексных чисел

Введение		ru
Комплексные числа и комплексные функции широко применяются в на-
	.

сложения и умноженияmatematemчисел. Таким образом, расширение концепции

стоящее время в физике, радиотехнике, теории электрических цепей, в теории колебаний и т.д. Первоначально они возникли в алгебре при решении алгебраических уравнений степени выше 1. Из элементарного курса алгебры известно, как шло расширение понятия числа. Потребности счета требовали не ограничиваться конкретным набором чисел, например 1, 2, . . . , 10, а допускать сколь угодно большие числа. Так была развита концепция множества натуральных чисел N = {1, 2, 3, . . .}, замкнутого относительно операций сложения и умножения чисел. Введение операции вычитания потребовало расширить N до множества целых чисел Z = {0, ±1, ±2, ±3, . . .}. Введение операции деления потребовало расширения множества Z до множества Q всех рациональных чисел, т.е.

дробей вида mn , m, n Z. Наконец, решение задач измерения отрезков оказалось связано с проблемой неполноты множества Q, т.е. существова-

ния несоизмеримых отрезков. Это потребовало развития концепции иррациональных чисел и привело к созданию понятия множества R всех

вещественных чисел, включающего в себя все рациональные и ирраци-

ональные числа. Эта концепция позволила решить упомянутые выше проблемы. При этом цепочка расширений N Z Q R строилась

так, что операции сложения и умножения, определенные на более широ-

ком множестве чисел, были согласованы с уже известными операциями
www	соответствия: новая теория расширяет об-
числа отвечало принципу.

ласть применимости старой теории и не противоречит ей там, где старая теория была применима. Множество R вещественных чисел образует поле, оно замкнуто относительно всех арифметических операций.

Концепция вещественного числа не позволяла, однако, решать даже самые простые алгебраические уравнения степени выше 1. Например, уравнение

(1)

не имеет решений в поле вещественных чисел.