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

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

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

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

ПРИМЕР. Совокупность чисел 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 в приведенной системе вычетов содежится 2 числа, а при m = 8 получено 4 числа. Сколько чисел в приведенной системе вычетов при произвольном модуле m? Для ответа на вопрос нужно найти число классов взаимно простых с модулем m.

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

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

ПРИМЕР. Найти ϕ(6). Составим ряд чисел 0, 1, 2, 3, 4, 5 и вычеркнем из него числа, не взаимно простые с 6. Получим

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

Остались числа 1, 5, которые взаимно простых с 6. Поэтому ϕ(6) = 2. Найдем теперь число классов вычетов по модулю m, взаимно простых с m

Для этого выпишем все имеющиеся классы по модулю ¯ ¯ ¯ − m 0, 1, 2, . . . , m 1.

Рассмотрим следующий выбор представителей в этих классах

¯	¯	¯	m¯ − 1.
0 0,	1 1,	2 2, . . . , m − 1

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

Итак, число классов, взаимно простых с модулем m равно ϕ(m).

П . Рассмотрим модуль . Тогда ровно четыре класса ¯ ¯ ¯ ¯

РИМЕР m = 8 1, 3, 5, 7

взаимно просто с модулем 8. Поэтому ϕ(8) = 4.

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

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

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

1)числа x1, x2, . . . , xk взаимно просты с модулем m,

2)k = ϕ(m),

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

Доказательство необходимости. Пусть x1, x2, . . . , xk — приведенная система вычетов по модулю m. Тогда числа x1, x2, . . . , xk взяты из классов взаимно простых с модулем m. Поэтому эти числа взаимно просты с модулем 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. Теорема доказана.

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

Доказательство. По признаку приведенной системы вычетов достаточно проверить, что выполнены следующие три условия:

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

2)k = ϕ(m),

3)axi ≡/ axj (mod m) при i 6= j.

Проверим 1). По условию x1, x2, . . . , xk — приведенная система вычетов по модулю m. Поэтому (xi, m) = 1 для всех i = 1, 2, . . . , k. С учетом (a, m) = 1 получаем (axi, m) = 1.

2) Число k — это количество чисел в приведенной системе вычетов x1, x2, . . . , xk по модулю m. Поэтому k = ϕ(m).

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

3) Условие axi ≡/ axj (mod m) при i 6= j докажем методом от противного. Пусть axi ≡ axj (mod m) при i 6= j. Сократив сравнение на число a, взаимно простое с модулем m, получим xi ≡ xj (mod m) при i 6= j. Это противоречит тому, что x1, x2, . . . , xk приведенная система вычетов по модулю m.

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

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

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

x1, x2, . . . , xϕ(m). (3) Умножим числа из (3) на число a. Получим совокупность чисел

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

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

каждого класса K1, K2, . . . , Kϕ(m).

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

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

Переходя к классам вычетов, получаем
ax1	≡ xi1	(mod m)
ax2	≡ xi2	(mod m)
	· · ·	(5)
axϕ(m)	≡ xiϕ(m)	(mod m),

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

xi1 · xi2 · . . . · xiϕ(m) = x1 · x2 · . . . · xϕ(m),

(6)

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

Умножим почленно сравнения из (5). Получим
aϕ(m)x1x2 xϕ(m)		xi1 xi2		xi1 xiϕ(m)	(mod m).	(7)
След Пред Стр· · ·Начало	Оглавление Обратно Меню Экран Выход
	≡		· · ·

Сократим это сравнение на число x1 ·x2 ·. . .·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), что верно.

Рассмотрим частный случай, когда m = p— простое число. Применим теорему Эйлера. Имеем ϕ(p) = p − 1. Получаем

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

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

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

Существует другая формулировка теоремы Ферма.

Пусть 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 ... p, т.е. ap ≡ 0 (mod p). Отсюда ap ≡ a (mod p).

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

Вычисление Функции Эйлера.

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

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

(8)

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

Доказательство. Функция Эйлера определена на множестве натуральных чисел и не равно тождественно нулю. Нужно проверить только условие (8) для ϕ(x), т.е. ϕ(a · b) = ϕ(a) · ϕ(b) для всех a, b N таких, что (a, b) = 1.

Пусть a, b N и (a, b) = 1. Для вычисления функции Эйлера ϕ(a · b) нужно найти количество чисел x из совокупности 0, 1, 2, . . . , ab − 1, таких, что x взаимно просто с числом ab. Справедливо утверждение

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

Поэтому вместо того, чтобы отбирать числа x из совокупности 0, 1, 2, . . . , ab−1

сусловием (x, ab) = 1, поступим иначе.

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

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

2) Cреди полученных чисел отберем те, для которых (x, b) = 1.

Для удобства рассуждений выпишем числа 0, 1, 2, . . . , ab − 1 в виде следую-

щей таблицы
0	1	. . .	x	. . .	a − 1
a	a + 1	. . .	x + a	. . .	2a − 1	(9)
. . .	. . .	. . .	. . .	. . .	. . .

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

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

Поэтому, следующий шаг — отбор чисел x, для которых (x, b) = 1, выполняем только в помеченных столбцах. Элементы из них имеют вид

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

(10)

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

Эти b чисел имеют вид y · a + x, где y пробегает полную систему вычетов 0, 1, 2, . . . , b − 1 по модулю b. Так как (a, b) = 1 взаимно просты, то по теореме (2) числа из (10) образуют полную систему вычетов по модулю b. В любой полной системе вычетов по модулю b имеется ровно ϕ(b) чисел y, для которых

(y, b) = 1.

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

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

ТЕОРЕМА 8 Если m = pα1 1 pα2 2 · · · pαk k —каноническое разложение, то

ϕ(m) = (p1α1 − p1α1−1)(p2α2 − p2α2−1) · · · (pkαk − pkαk−1).

(11)

Доказательство. Установим вначале частный случай: если m = pα, где p— простое число, то ϕ(m) = pα − pα−1.

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

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