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

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

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

(12)

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

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

m = pα1 1 pα2 2 · · · pαk k ,

|{z} | {z }

ab

где (a, b) = 1. Тогда

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

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

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

Лекция 9. Кольцо классов вычетов.

Классы вычетов позволяют построить важные примеры колец и полей. Рас-

смотрим множество {¯ ¯ − }, состоящее из всех классов вычетов

K = 0, 1, . . . , m 1

по модулю m. Введем операции сложения и умножения классов. Пусть даны

	¯
				правилом x + y = a + b, т.е.
	классы x = a¯ и y = b. Определим сумму x + y
	¯			(1)
	a¯ + b = a + b.

Для того, чтобы считать + алгебраической операцией на множестве K необходимо чтобы для всех x, y K выполнялись два условия:

1)элемент x + y однозначно определен,

2)x + y K.

Условие 2), т.е. x+y K очевидно выполнено, так как x+y = a + b является классом вычетов.

Рассмотрим более сложное условие 1). Мы можем записать классы x и y в

виде отличном от и ¯. Для этого рассмотрим произвольные числа x = a¯ y = b

a1 x, b1 y. Тогда классы x и y представлены в другом виде x = a1 и y = b1. По правилу вычисления суммы x + y имеем одновременно

x + y = a + b, ,			(2)
			(3)
x + y = a1 + b1.

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

Если правые части из (2) и (3) различны, то неясно какой из элементов в правых частях считать в качестве x + y и сложение определено некорректно.

Поэтому нужно проверить, что a + b = a1 + b1. Так как a1 и a из одного класса вычетов, то a1 ≡ a (mod m). Аналогично, b1 ≡ b (mod m). Тогда a1 + b1 ≡ a + b (mod m). Отсюда a + b = a1 + b1, что и нужно.

¯			правилом
Определим теперь умножение классов x = a¯ и y = b
¯ ¯			(4)
ab = ab.

Самостоятельно проверить, что операция умножения также определена корректно.

ТЕОРЕМА 1 Множество классов вычетов по модулю m образует коммутативное кольцо с единицей относительно сложения и умножения.

Нужно проверить следующие аксиомы. 1) (x + y) + z = x + (y + z)

2) 0 K x K x + 0 = 0 + x = x

3) x K − x K − x + x = x + (−x) = 0

4)x + y = y + x.

5)(x + y)z = xz + yz, x(y + z) = xy + xz.

6)(xy)z = x(yz)

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

7) 1 x x · 1 = 1 · x = x

8) xy = yx

Заметим, что аксиомы 1)–6) — это аксиомы кольца. С учетом 7) получаем кольцо с единицей, а по 8) получаем коммутативное кольцо.

1) Проверим ассоциативность сложения. Пусть x, y, z K. Тогда x = a,¯ y =

¯ , где . Имеем b, z = c¯ a, b, c Z

¯

(x + y) + z = (¯a + b) + c¯ = (a + b) + c,

¯

x + (y + z) = a¯ + (b + c¯) = a + (b + c).

Правые части (a + b) + c и a + (b + c) равны, так как для целых чисел a, b, c

выполнено равенство (a + b) + c = a + (b + c).
Аналогично доказываются аксиомы 4), 5), 6), 8).
¯						¯
2). Установим, что 0 — ноль кольца. Для x = a¯					по правилу (1) имеем x+ 0 =
		¯
a + 0 = a¯ = x. Аналогично получаем 0 + x = x.
									¯
3). Пусть x = a¯. Рассмотрим −x = −a. Тогда −x + x = −a + a¯ = 0.
Аналогично получаем x + (−x).		¯				¯
Осталось проверить 7). Рассмотрим 1. Для x = a¯						имеем x1 = a1 = a¯ = x и

x1 = x.

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

Случай, когда m = p — простое число, имеет особое значение.

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

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

Доказательство. Поле — это коммутативное кольцо с единицей 1 6= 0, в котором каждый ненулевой элемент имеет обратный элемент относительно умножения. Поэтому осталось проверить, что

x K \ {0} x−1 x−1x = xx−1 = 1.
.	.
.	.

Имеем x = a¯. Так как x 6= 0, то a 6. p. Для простого числа p верно a . p или

.
.	¯
(a, p) = 1. Если a . p, то a ≡ 0 (mod p) и x = 0, что не так.

Поэтому НОД чисел a и b равен 1. Запишем его в линейной форме. Получим 1 = au + pv. Отсюда 1 ≡ au (mod p). Тогда x−1 = u¯. Действительно, xx−1 =

¯ и также −1 ¯. a¯u¯ = 1 x x = 1

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

Данная теорема дает конструкцию конечного поля, то есть поля, состоящего из конечного числа элементов.

Теория конечных полей находит применение в теории кодирования — дисциплине, которая изучает методы для обнаружения и исправления ошибок при передаче информации.

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

Лекция 10. Сравнения первой степени с одной переменной.
Расмотрим сравнение
a0xn + a1xn−1 + · · · + an ≡ 0 (mod m),	(1)

где a0, a1, . . . , an Z. Если a0 6... m, то данное сравнение называется сравнением n-ой степени.

Число a Z называется решением сравнения (1), если при замене в сравнении (1) переменной x, на ее значение a, получаем верное сравнение.

Пусть a — решение сравнения, т.е. a0an + a1an−1 + · · · + an ≡ 0 (mod m). Если b ≡ a (mod m), то a0bn+a1bn−1+· · ·+an ≡ 0 (mod m), т.е. b также реше-

ние сравнения. Поэтому, числа сравнимые с a по модулю m числа, считаются одним и тем же решением. За решение сравнения принимается не отдельное число a, а весь класс вычетов a¯.

Рассмотрим случай n = 1. Получаем сравнение первой степени

ax ≡ b	(mod m),	(2)
.
.
где a 6. m.
ПРИМЕР 1. Решить сравнение
5x ≡ 1	(mod 7).

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

Решение. Это сравнение решим методом перебора. Мы просто испытаем все классы по модулю 7. Если класс не является решение, то перечеркиваем его. Получим

60, 61, 62, 3, 64, 65, 6

Ответ. Сравнение 5x ≡ 1 (mod 7) имеет единственное решение x = 3.

ПРИМЕР 2. Решить сравнение 6x ≡ 1 (mod 14).

Решение. Как и выше можно перебрать все классы, и обнаружится, что решений нет.

На самом деле отсутствие решений видно сразу: если решение x0 есть, то
.
.
получим 6x0 ≡ 1 (mod 14). Тогда 6x0 = 1 + 14q, откуда 1 . 2, противоречие.
Мы обнаружили две возможности для решения сравнения.
Опишем все возможные случаи при решении сравнений первой степени.
ТЕОРЕМА 1 Сравнение первой степени
ax ≡ b (mod m), где (a, m) = 1,	(3)

имеет единственное решение.

Доказательство. Рассмотрим все классы 0, 1, 2, · · · , m − 1 по модулю m и возьмем по одному числу из каждого класса. Получим полную систему вычетов

x0, x1, . . . , xm−1

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

по модулю m. Подставим каждое число xi из этих чисел в сравнение (3), и проверим является ли оно решением. Если xi — решение, то и весь класс xi

— решение сравнения.

То, что xi — решение сравнения (3), означает axi ≡ b (mod m), т.е. число axi содержится в одном классе вычетов с числом b. По теореме 2 из лекции 8 числа ax0, ax1, . . . , axm−1 образуют полную систему вычетов. Поэтому ровно одно число axi из этих чисел содержится в одном классе с числом b. Получили, что сравнение (3) имеет единственное решение.

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

ТЕОРЕМА 2 Сравнение первой степени
.
.	(4)
ax ≡ b (mod m), где (a, m) = d и b 6. d,

не имеет решений.

Доказательство методом от противного. Допустим, что некоторое число x0 Z—решение сравнения, т.е. ax0 ≡ b (mod m). Тогда ax0 = b + mq и b = ax0 − mq ... d—противоречие с условием. Поэтому сравнение не имеет решений.

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

ТЕОРЕМА 3 Сравнение первой степени
.
.	(5)
ax ≡ b (mod m), где (a, m) = d > 1 и b . d,

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

имеет ровно d решений.

Доказательство. Числа a, m, b делятся на d. Поэтому a = a1d, m = m1d, b = b1d. Перепишем исходное сравнение в виде a1dx ≡ b1d (mod m1d). Имеем a1dx ≡ b1d (mod m1d) a1x ≡ b1 (mod m1).

Поэтому вместо того, чтобы решать сравнение ax ≡ b (mod m), имеющее модуль m, решим сравнение a1x ≡ b1 (mod m1), имеющее модуль m1.

Числа a1 и m1, получены из чисел a = a1d и m = m1d сокращением на их НОД, равный d. Поэтому a1 и m1 взаимно просты.

С учетом (a1, m1) = 1, по теореме 1 сравнение a1x ≡ b1 (mod m1) имеет единственное решение. Поскольку получено единственное решение, то возникает вопрос, откуда получатся d решений исходного сравнения?

Исходное сравнение — это сравнение по модулю m, значит ответы должны быть представлены как классы по модулю m. Единственное решение сравнения a1x ≡ b1 (mod m1) – это единственный класс по модулю m1.

Покажем, что все числа, которые образуют один класс по модулю m1 разбиваются на d классов по модулю m. Запишем единственное решение сравнения a1x ≡ b1 (mod m1) в виде x = x0 + m1q, где q пробегает все целые числа.

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

Получим ряд чисел
. . . , x0, x0 + m1, x0 + 2m1, . . . , x0 + (d − 1)m1, x0 + dm1, . . .							(6)
|			{z			}
	d различных				m
		решений по модулю

Рассмотрим сначала значения q = 0, 1, . . . , d − 1. Получим числа x0, x0 + m1, x0 +2m1, . . . , x0 +(d−1)m1. Эти числа попарно не сравнимы по модулю m. Получили d решений исходного сравнения ax ≡ b (mod m), имеющего модуль m.

Следующее число x0 + dm1 = x0 + m получено при q = d. Оно сравнимо с x0 по модулю m, следующее сравнимо с x0 + m1, и т.д. Поэтому остальные числа сравнимы с первыми d числами по модулю m и не дают новых решений по модулю m. Получили ровно d решений сравнения ax ≡ b (mod m) по модулю m.

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

Приведем формулу для решение сравнения первой степени. Эта формула использует функцию Эйлера ϕ(m).

ТЕОРЕМА 4 Пусть дано сравнение ax ≡ b (mod m), где (a, m) = 1. Тогда

x ≡ aϕ(m)−1b (mod m).

(7)

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