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

Любое число класса будем называть вычетом по модулю m. Если класс вычетов по модулю m состоит из элементов сравнимых с числом a по модулю m, то этот класс обозначается через a¯. Поэтому в определении класса эквивалентных элементов (7.4) нужно заменить букву R на знак сравнимости ≡. Получим, что класс вычетов a¯ имеет вид

a¯ = {x Z | x ≡ a (mod m)}.

(7.6)

Итак, возможна другая формулировка определения класса вычетов по модулю m, которую мы будем чаще всего использовать.

ОПРЕДЕЛЕНИЕ 7.4. Классом вычетов a¯ по модулю m называется множество всех чисел, сравнимых с числом a по модулю m.

По признаку равенства классов эквивалентных элементов (7.5) непосредственно получаем следующий признак равенства классов вычетов.

	¯
ТЕОРЕМА 7.4 Два класса вычетов a¯ и b равны тогда и только
тогда, когда числа a и b сравнимы по модулю m
¯	a ≡ b (mod m).	(7.7)
a¯ = b

При делении целых чисел на m возможны остатки 0, 1, 2, . . . , m − 1. Рас-

смотрим классы
¯ ¯ ¯	(7.8)
0, 1, 2, . . . , m − 1.

ТЕОРЕМА 7.5 1) Если r – остаток от деления числа a на m, то класс a¯ совпадает с классом r¯.

2) Классы из (7.8) попарно различны и исчерпывают все классы по модулю m. Существует ровно m классов вычетов по модулю m.

Доказательство. 1) Пусть a¯ – произвольный класс по модулю m и r – остаток от деления a на m. Тогда a ≡ r (mod m). По признаку равенства классов вычетов (7.7) получаем a¯ = r¯.

2) Поскольку произвольный класс по модулю m совпадает с одним из классов в списке (7.8), то осталось проверить, что все элементы из этого списка попарно различны. Это следует из того, что остатки 0, 1, 2, . . . , m − 1 попарно не сравнимы по модулю m. Теорема доказана.

31

Лекция 8. Полная и приведенная системы вычетов.

ОПРЕДЕЛЕНИЕ 8.1. Полной системой вычетов по модулю m называется совокупность чисел, взятых по одному из каждого класса вычетов по модулю m.

ПРИМЕР. Совокупность чисел 5, 11, 4, 6 является полной системой вычетов по модулю 4. Действительно, по модулю m = 4 имеется ров-

¯ ¯ ¯ ¯					взяты по одному из
но четыре класса 0, 1, 2, 3. При этом числа 5, 11, 4, 6
каждого класса, а именно:
¯	¯	¯	11	¯
4 0,	5 1,	6 2,		3.

Числа 5, 1, 4, 6 не образуют полную систему вычетов по модулю 4, т.к.

и взяты из одного класса ¯.

5 1 1

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

ТЕОРЕМА 8.1 . Совокупность чисел x1, x2, . . . , xk образует полную систему вычетов по модулю m тогда и только тогда, когда выполнены следующие два условия :

1)k = m,

2)xi ≡/ xj (mod m) при i 6= j.

Доказательство необходимости. Пусть x1, x2, . . . , xk – полная система вычетов по модулю m. Проверим условия 1) и 2). Имеем совокупность чисел x1, x2, . . . , xk, взятых по одному элементу из каждого класса вычетов. Количество классов вычетов равно m. Поэтому k = m.

Пусть i 6= j. Тогда xi и xj классы взяты из разных классов. Поэтому xi ≡/ xj (mod m).

Достаточность. Пусть выполнены условия 1) и 2). Применим известное правило комбинаторики – принцип ящиков.

Пусть даны m ящиков и m предметов x1, x2, . . . , xm, взятых из этих ящиков. Предположим, что никакие два предмета xi и xj при i 6= j не содержатся в одном ящике. Тогда данные m предметов взяты ровно по одному из каждого ящика.

В нашем случае в качестве данных предметов выступают числа x1, x2, . . . , xk. При этом k = m по условию 1). В качестве данных ящи-

ков выступают классов вычетов ¯ ¯ ¯ − . m 0, 1, 2, . . . , m 1

32

Так как выполнено условие 2), то xi ≡/ xj (mod m) при i 6= j. Это означает, что числа xi и xj при i 6= j попадают в разные классы. По принципу ящиков числа x1, x2, . . . , xk взяты по одному из каждого клас-

¯ ¯ ¯			, x2, . . . , xk – полная система вычетов по
са 0, 1, 2, . . . , m − 1. Поэтому x1
модулю m. Теорема доказана.

ТЕОРЕМА 8.2. Пусть a, b Z и (a, m) = 1. Если числа x1, x2, . . . , xk образуют полную систему вычетов по модулю m, то числа

ax1 + b, ax2 + b, . . . , axk + b	(8.1)
также образуют полную систему вычетов по	модулю m.

Доказательство. Применим признак полной системой вычетов к совокупности чисел (8.1). Проверим выполнимость условий 1) и 2).

В списке (8.1) содержится k = m чисел, т.е. выполнено условие 1). Установим 2) методом от противного. Пусть axi + b ≡ axj + b (mod m)

при i 6= j. Тогда a(xi − xj) ≡ 0 (mod m). Разделим обе части сравнения на число a, взаимно простое с модулем m. Получим xi ≡ xj (mod m) при i 6= j. Противоречие с тем, что числа x1, x2, . . . , xk образуют полную систему вычетов. Теорема доказана.

Приведенная система вычетов. Введем понятие класса, взаимно простого с модулем. Пусть a и b два произвольных числа из некоторого класса вычетов по модулю m. Тогда a = mq + b для некоторого q Z. По пункту 2 леммы 2.2, стр. 8 выполнено равенство (a, m) = (b, m). Тем самым справедливо следующее утверждение.

ЛЕММА 8.1. Все числа фиксированного класса вычетов по модулю m имеют один и тот же НОД с модулем m.

Так как НОД (b, m) один и тот же у всех чисел b a¯, то верно1 ) или 2):

1)все числа из класса a¯ взаимно просты с модулем m,

2)все числа из класса a¯ не взаимно просты с модулем m.

Вслучае 1) класс a¯ называется классом, взаимно простым с модулем; в случае 2) класс a¯ называется классом, не взаимно простым с модулем.

ОПРЕДЕЛЕНИЕ 8.2 . Приведенной системой вычетов по модулю m называется совокупность чисел, взятых по одному из каждого класса вычетов, взаимно простого с модулем.

33

ПРИМЕР. Совокупность чисел 1, −1 является приведенной системой вычетов по модулю 4. Действительно, имеется четыре класса вычетов

¯ ¯ ¯ ¯	¯	¯	взаимно просты с моду-
0, 1, 2, 3 по модулю m = 4. При этом классы 1		и 3
¯	¯
лем, а классы 0	и 2 не взаимно просты с модулем.
		¯	¯
Числа 1 и −1 взяты по одному из классов 1			и 3, взаимно простых с

модулем. Поэтому 1, −1 – приведенная система вычетов по модулю 4. Аналогично получаем, что числа 1, 3, 5, 7 образуют приведенную си-

стему вычетов по модулю 8.

Итак, при m = 4 в приведенной системе вычетов содержится два числа, а при m = 8 содержится четыре числа. Сколько чисел в приведенной системе вычетов при произвольном модуле m? Для ответа на вопрос нужно найти число классов взаимно простых с модулем m.

ОПРЕДЕЛЕНИЕ 8.3. Функцией Эйлера ϕ(m) называется количество чисел из совокупности 0, 1, 2, . . . , m−1, взаимно простых с числом m.

ПРИМЕР 1. Найти значение функции Эйлера ϕ(m) при m = 6. Решение. Рассмотрим совокупности чисел 0, 1, 2, 3, 4, 5. Вычеркнем из

нее те числа, которые не взаимно просты с m = 6. Получим

0, 1, 2, 3, 4, 5.

Остались числа 1, 5, которые взаимно просты с m = 6. Поэтому ϕ(6) = 2. ПРИМЕР 2. Доказать, что если p – простое число, то ϕ(p) = p − 1. Решение. Составим ряд чисел 0, 1, 2, . . . , p − 1 и вычеркнем из него

числа a, которые не взаимно просты с p. Так как p – простое число, то (a, p) = 1 или a ... p. Среди чисел 0, 1, 2, . . . , p − 1 лишь число 0 делится на p. Остальные p − 1 чисел 1, 2, . . . , p − 1 взаимно просты с p. Поэтому

ϕ(p) = p − 1.

Число ϕ(m) по определению равно количеству чисел из совокупности 0, 1, 2, . . . , m − 1, взаимно простых с m. Так как (0, m) = 1 (m, m) = 1, то число 0 в определении ϕ(m) можно заменить на m. Получаем

ЗАМЕЧАНИЕ 8.1 Число ϕ(m) равно количеству чисел из совокупности 1, 2, . . . , m − 1, m, взаимно простых с m.

ТЕОРЕМА 8.3 Число классов вычетов по модулю m, взаимно простых с модулем, равно ϕ(m).

34

Доказательство. Выберем в качестве представителей классов

¯ ¯ ¯	наименьшие неотрицательные вычеты. Получим пол-
0, 1, 2, . . . , m − 1

ную систему наименьших неотрицательных вычетов по модулю m

0, 1, 2, . . . , m − 1. (8.2)

Классами, взаимно простыми с модулем, будут те классы, чьи представители взаимно просты с модулем. Число таких представителей равно количеству чисел в ряде (8.2), взаимно простых с m, т.е. равно ϕ(m). Теорема доказана.

ПРИМЕР. Рассмотрим модуль m = 8. Тогда ϕ(8) = 4 и ровно четыре

¯ ¯ ¯ ¯	взаимно просты с модулем 8.
класса 1, 3, 5, 7

Ранее получен признак полной системы вычетов. Рассмотрим аналогичный результат – признак приведенной системой вычетов.

ТЕОРЕМА 8.4. Совокупность чисел x1, x2, . . . , xk образует приведенную систему вычетов по модулю m тогда и только тогда, ко-

гда выполнены следующие три условия :
1) числа x1, x2, . . . , xk взаимно просты с модулем m,
2) k = ϕ(m),	(8.3)
3) xi ≡/ xj (mod m)при i 6= j.

Доказательство необходимости. 1) Пусть x1, x2, . . . , xk – приведенная система вычетов по модулю m. Тогда эти вычеты взяты из классов, взаимно простых с модулем m. Поэтому числа x1, x2, . . . , xk взаимно просты с модулем m и верно условие 1).

Проверим 2). Число классов, взаимно простых с модулем m, равно ϕ(m), а числа x1, x2, . . . , xk взяты по одному из каждого такого класса. Поэтому k = ϕ(m).

Условие 3) следует из того, что числа x1, x2, . . . , xk взяты из разных классов.

Достаточность. Пусть выполнены условия 1) – 3). Из 1) получаем, что числа x1, x2, . . . , xk взяты из классов взаимно простых с модулем m. Количество классов, откуда берутся числа, равно ϕ(m) – столько же, сколько и самих чисел x1, x2, . . . , xk. По условию 3) числа xi и xj при i 6= j взяты из разных классов. По принципу ящиков эти числа взяты по одному из каждого класса взаимно простого с модулем m. Поэтому x1, x2, . . . , xk – приведенная система вычетов по модулю m. Теорема доказана.

35

ТЕОРЕМА 8.5 . Пусть (a, m) = 1 и числа x1, x2, . . . , xk образуют приведенную систему вычетов по модулю m. Тогда числа ax1, ax2, . . . , axk также образуют приведенную систему вычетов по модулю m.

Доказательство. Так как x1, x2, . . . , xk – приведенная система вычетов, то справедливы условия (8.3). Нужно проверить, что ax1, ax2, . . . , axk – приведенная система вычетов, т.е. выполнены условия

10 ) числа ax1, ax2, . . . , axk взаимно просты с модулем m,

20		) k = ϕ(m),									(8.4)
3	0	)	ax	/ ax	j	(mod	m	)	при i	6=	j.
				i ≡

Пункт 20 ) из (8.4) совпадает пунктом 2) в (8.3). Поэтому осталось проверить условия 10 ) и 30 ).

Установим 10 ). По пункту 1) в (8.3) имеем (xi, m) = 1 для всех i = 1, 2, . . . , k. Учитывая (a, m) = 1, получим (axi, m) = 1.

Проверим 30 ) методом от противного. Пусть axi ≡ axj (mod m) при i 6= j. Сократим сравнение на число a, взаимно простое с модулем m. Получим xi ≡ xj (mod m) при i 6= j, что противоречит пункту 3) в (8.3).

Теорема доказана.
Теоремы Эйлера и Ферма.
ТЕОРЕМА 8.6 ( Л. Эйлер.) Пусть (a, m) = 1. Тогда
aϕ(m) ≡ 1 (mod m).	(8.5)

Доказательство. Рассмотрим все классы вычетов K1, K2, . . . , Kϕ(m), взаимно простые с модулем m. Число этих классов равно ϕ(m). Возьмем по одному представителю из каждого класса. Получим приведенную систему вычетов по модулю m

x1, x2, . . . , xϕ(m). (8.6)

Умножим числа из (8.6) на число a. Получим совокупность чисел

ax1, ax2, . . . , axϕ(m). (8.7)

По предыдущей теореме эта совокупность является приведенной система вычетов по модулю m. Поэтому числа ax1, ax2, . . . , axϕ(m) взяты по одному из каждого класса K1, K2, . . . , Kϕ(m).

36

Рассмотрим следующую аналогию. Имеется ϕ(m) «домов»

K1, K2, . . . , Kϕ(m). Пусть x1, x2, . . . , xϕ(m) – «жители» этих домов, взятые по одному из каждого дома. Совокупность ax1, ax2, . . . , axϕ(m) – другой

набор жителей из этих домов, также по одному из каждого дома. Тогда ax1 проживает в одном доме с некоторым xi1 , ax2 проживает в одном доме с некоторым xi2 и т.д.

В случае классов вычетов получаем

ax1 ≡ xi1 ax2 ≡ xi2

· · ·

axϕ(m) ≡ xiϕ(m)

(mod m) (mod m)

(8.8)

(mod m),

где xi1 , xi2 , . . . , xiϕ(m) те же числа, что и числа x1, x2, . . . , xϕ(m), но переставлены в другом порядке . Тогда имеем равенство произведений

xi1 xi2 . . . xiϕ(m) = x1x2 . . . xϕ(m),

(8.9)

поскольку произведение не зависит от порядка сомножителей. При этом произведение x1x2 . . . xϕ(m) взаимно просто с m, т.к. каждый его сомножитель взаимно прост с m.

Умножим почленно сравнения из (8.8). Получим

aϕ(m)x1x2sxϕ(m) ≡ xi1 xi2 sxiϕ(m) (mod m).

(8.10)

Сократим это сравнение на число x1x2 . . . xϕ(m) = xi1 xi2 . . . xiϕ(m) , взаимно простое с модулем m. Получим aϕ(m) ≡ 1 (mod m), что и нужно.

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

ПРИМЕР. Пусть a = 2, m = 7. Проверим, что aϕ(m) ≡ 1 (mod m). Имеем m = 7 – простое число. Поэтому ϕ(7) = 7 − 1 = 6. Нужно

проверить, что 26 ≡ 1 (mod 7), т.е. 64 ≡ 1 (mod 7), что верно.

Частным случаем теоремы Эйлера является следующее утверждение.

ТЕОРЕМА 8.7 (П. Ферма.) Пусть p – простое число и a 6... p. Тогда ap−1 ≡ 1 (mod p).

Доказательство. Так как a 6...p и p – простое число, то (a, p) = 1. По теореме Эйлера aϕ(p) ≡ 1 (mod p). Поскольку ϕ(p) = p − 1, то ap−1 ≡ 1 (mod p). Теорема доказана.

Возможна другая формулировка теоремы Ферма.

37

ТЕОРЕМА 8.8. Пусть p – простое число. Тогда для любого целого числа a справедливо сравнение ap ≡ a (mod p).

Доказательство. Если a 6... p, то ap−1 ≡ 1 (mod p). Умножив это сравнение на a, получим ap ≡ a (mod p). Если a ... p, то a ≡ 0 (mod p). Тогда ap ≡ 0 (mod p). Отсюда ap ≡ a (mod p). Теорема доказана.

Мультипликативные функции. Вычисление функции Эйлера.

ОПРЕДЕЛЕНИЕ 8.4. Функция f(x), определенная на множестве натуральных чисел и не равная тождественно нулю, называется мультипликативной, если

f(a · b) = f(a) · f(b) для всех a, b N таких, что (a, b) = 1. (8.11)

ТЕОРЕМА 8.9 . Функция Эйлера является мультипликативной функцией.

Доказательство. Функция Эйлера определена на множестве натуральных чисел и не равна тождественно нулю. Поэтому нужно проверить только условие мультипликативности

ϕ(ab) = ϕ(a)ϕ(b) для всех a, b N таких, что (a, b) = 1.

(8.12)

Пусть a, b N и (a, b) = 1. Вычислим число ϕ(ab). Для этого нужно отобрать числа x из совокупности

0, 1, 2, . . . , ab − 1,

(8.13)

которые взаимно просты с числом ab. Справедливо утверждение

(x, ab) = 1 (x, a) = 1 (x, b) = 1.

Поэтому отбор чисел x из совокупности (8.13) с условием (x, ab) = 1 выполним в два шага.

Шаг 1. Вначале найдем числа x с условием (x, a) = 1.

Шаг 2. Cреди полученных чисел отберем те, для которых (x, b) = 1. Для удобства рассуждений выпишем числа из совокупности (8.13) в

виде следующей таблицы из b строк и a столбцов
0	1	. . .	t	. . .	a − 1
a	a + 1	. . .	t + a	. . .	2a − 1	(8.14)
. . .	. . .	. . .	. . .	. . .	. . .

a(b − 1) a(b − 1) + 1 . . . t + (b − 1)a . . . ab − 1.

38

Рассмотрим произвольный столбец с элементом t в первой строке. Его элементы равны

t, t + a, t + 2a, . . . t + (b − 1)a,

(8.15)

т.е. имеют вид t + x · a, где x пробегает полную систему вычетов 0, 1, 2, . . . , b − 1 по модулю b. Так как (a, b) = 1, то по теореме (8.2) числа из (8.15) образуют полную систему вычетов по модулю b. Итак, каждый столбец таблицы – полная система вычетов по модулю b.

Выполним шаг 1 – найдем числа x с условием (x, a) = 1. В первой строке имеется ровно ϕ(a) таких чисел. Действительно, мы выбираем в списке 0, 1, . . . , a − 1числа, взаимно простые с a. По определению функции Эйлера их количество равно ϕ(a). Рассмотрим произвольный элемент t из данных ϕ(a) чисел, и отметим весь столбец, где расположен этот элемент.

Число отмеченных столбцов равно ϕ(a). Рассмотрим один из них с элементом t в первой строке. Все числа в этом столбце сравнимы с t по модулю a, и, поэтому, содержатся в одном классе вычетов по модулю a. Поэтому все они взаимно просты с числом a. С другой стороны, все числа в непомеченных столбцах не взаимно просты с a.

Поэтому, в шаге 2 отбор чисел x, для которых (x, b) = 1, выполняем только в помеченных столбцах. Как отмечено выше, столбцы – это полные системы вычетов по модулю b. В любой полной системе вычетов по модулю b имеется ровно ϕ(b) чисел y, для которых (y, b) = 1.

Итак, мы проверяли ϕ(a) столбцов, и обнаружили в каждом из них ϕ(b) чисел y с условием (y, b) = 1. Поэтому имеется ϕ(a)ϕ(b) чисел взаимно простых как с числом a, так и с числом b. Получили ϕ(ab) = ϕ(a)ϕ(b), что и нужно. Теорема доказана.

Приведем формулу для функции Эйлера.

ТЕОРЕМА 8.10. Пусть m = pα1 1 pα2 2 . . . pαk k – каноническое разло-

жение числа m. Тогда
ϕ(m) = (p1α1 − p1α1−1)(p2α2 − p2α2−1) . . . (pkαk − pkαk−1).	(8.16)

Доказательство. Установим вначале частный случай при k = 1. Пусть m = pα, где p – простое число и α > 0. Проверим, что

ϕ(m) = pα − pα−1.

39

Для вычисления ϕ(m) выпишем числа 1, 2, . . . , pα и найдем количество чисел из этой совокупности, взаимно простых с pα. Для этого удалим из совокупности 1, 2, . . . , pα числа, не взаимно простые с pα.

Самостоятельно проверить, что удаляемые числа – это в точности чис- " ла из множества 1, 2, . . . , pα, делящиеся на p. Итак, имеем ряд чисел

1, 2, . . . , 1p , . . . , 2p , . . . , pα−1p,

(8.17)

где особо выделены числа кратные p. Этих чисел pα−1, а остальные числа взаимно просты с pα. Поэтому ϕ(m) = pα − pα−1.

Рассмотрим теперь общий случай. Имеем

m = p1α1	p2α2 · · · pkαk ,
|{z}	|		{z		}

ab

где a = pα1 1 , b = pα2 2 · · · pαk k и (a, b) = 1. Применяя мультипликативность функции Эйлера, получаем

ϕ(ab) = (pα1 1 − pα1 1−1)ϕ(b).

Повторим рассуждение для b и т.д. Получим формулу (8.16). Теорема доказана.

ЗАМЕЧАНИЕ. Формулу для ϕ(m) иногда удобнее использовать в другом виде. Пусть m = pα1 1 pα2 2 . . . pαk k – каноническое разложение числа m. Тогда

ϕ(m) = m 1 −

1

1

1

. . . 1

1

.

(8.18)

−

−

p1

p2

pk

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

1

1

1

m 1 −

1 −

. . . 1 −

=

p1

p2

pk

= (p

α1 p

α2

. . . p

αk )

·

p1 − 1

·

p2 − 1

·

. . .

·

pk − 1

=

h

1

2

k

p1

p2

α

1

pk

i

α

1

α

1

ih

−

= p1α1−1p2

α2−1

. . . pk

αk

−1

(p1

i

1)(p2 − 1) . . . (pk − 1)

=

h

α1

α1 1

ih2

α2

1

αk

h

αk

1

i

= p1 1

− (p1

− 1) p2 2−

(p2 − 1) . . . pk k

−

(pk − 1) =

= (p1 − p1

− )(p2

− p2

− ) . . . (pk − pk

− ) = ϕ(m),

α

что и нужно

40