Материал: Михайленко Е.В. Математика. Ч. 1. Элементы общей алгебры

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

Пример. Совокупность чисел 5, 11, 4, 6 является полной системой вычетов по модулю 4. Тогда при a = 3 и b = 2 числа

3 ∙ 5 + 2 = 17,

3 ∙ 11 + 2 = 35,

3 ∙ 4 + 2 = 14,

3 ∙ 6 + 2 = 20

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

Приведенная система вычетов

Приведенной системой вычетов по модулю m называется совокупность чисел, взятых по одному из каждого класса вычетов, взаимно простого с модулем.

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

Действительно, имеется четыре класса вычетов 0, 1, 2, 3 по модулю 4. При этом классы 1 и 3 взаимно просты с модулем, а классы 0 и 2 не взаимно просты с модулем.

Числа 1 и −1 взяты по одному из классов 1 и 3, взаимно простых с модулем. Поэтому 1, −1 – приведенная система вычетов по модулю 4.

Аналогично получаем, что числа 1, 3, 5, 7 образуют приведенную систему вычетов по модулю 8.

Итак, при m = 4 в приведенной системе вычетов содержится два числа, а при m = 8 содержится четыре числа.

2.7. Взаимно простые числа Функция Эйлера

Функцией Эйлера ϕ(m) называется количество чисел из совокупности 0, 1, 2, ..., m−1, взаимно простых с числом m.

Пример. Найти значение функции Эйлера ϕ(m) при m = 6.

41

Рассмотрим совокупность чисел 0, 1, 2, 3, 4, 5. Вычеркнем из нее те числа, которые не взаимно просты с m = 6. Получим:

0, 1, 2, 3, 4, 5

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

модулем, равно ϕ(m).

Пример. Рассмотрим модуль m = 8. Тогда ϕ(8) = 4 и ровно четыре класса 1, 3, 5, 7 взаимно просты с модулем 8.

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

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

2)k = ϕ(m), (8.3)

3)xi ≡ xj (mod m) при i ≠ j.

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

Пример. Числа 1, 3, 5, 7 образуют приведенную систему вычетов по модулю 8. Тогда числа 11, 33, 55, 77 также образуют приведенную систему вычетов по модулю 8.

Теоремы Эйлера и Ферма

Теорема ( Л. Эйлер). Пусть (a, m) = 1. Тогда 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), что верно.

Теорема (П.Ферма) Пусть p – простое число и a не делится на p. Тогда ap−1 ≡ 1 (mod p)

Пример. Пусть a = 2, p = 7. Тогда 27−1 = 64, а 64 ≡ 1 (mod 7), что верно.

42

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

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

Пример. Покажем, что функция Эйлера является мультипликативной функцией.

Возьмем два взаимно простых числа 5 и 6.

Очевидно ϕ(5 6) = ϕ(30) = 8, а ϕ (5) ϕ (6) = 4 2 = 8.

Теорема. Пусть m = p1α1 p2α2 ... pkαk.– каноническое разложение числа m. Тогда функция Эйлера вычисляется по формуле:

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

Пример. Рассчитаем функцию Эйлера ϕ(600).

Каноническое разложение числа 600 = 23 3 52. Следовательно, ϕ(600) = (23 – 22)(31 – 30)(52 – 51) = 4 2 20 = 160.

2.8. Решение сравнений Определение сравнений n-й степени

Рассмотрим сравнение

f(x) ≡ 0 (mod m),

где f(x) = a0xn+a1xn−1 + +an – многочлен с целыми коэффициентами.

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

При n = 1 получаем сравнение первой степени ax ≡ b (mod m).

Пример. Решить сравнение

5x ≡ 1 (mod 7).

Решение. Это сравнение решим методом перебора. Проверим поочередно все классы 0, 1, 2, 3, 4, 5, 6 по модулю 7, и выясним, являются ли они

Таким образом, сравнение 5x ≡ 1 (mod 7) имеет единственное решение x = 3.

Пример. Решить сравнение

6x ≡ 1 (mod 14).

Решение. Можно перебрать все классы, и обнаружится, что решений нет. Однако отсутствие решений видно сразу. Если существует число a, удовлетворяющее сравнению, то 6a ≡ 1 (mod 14). Тогда

6a = 1 + 14q.

Получается, что слева в равенстве стоит четное выражение, а справа – нечетное, что противоречит здравому смыслу.

Таким образом, сравнение 6x ≡ 1 (mod 14) решений не имеет. Пример. Решить сравнение

6x ≡ 8 (mod 4).

Решение. Проверим поочередно все классы 0, 1, 2, 3 по модулю 4, и выясним, являются ли они решениями.

Таким образом, сравнение 6x ≡ 8 (mod 4) имеет два решение x1 = 0 и x2 = 2.

Решение сравнений 1-й степени

Опишем все возможные случаи, возникающие при решении сравнений первой степени.

1)Сравнение первой степени ax ≡ b (mod m), где (a, m) = 1, имеет

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

2)Сравнение первой степени ax ≡ b (mod m), где (a, m) = d и b не делится на d не имеет решений.

3)Сравнение первой степени ax ≡ b (mod m), где (a, m) = d и b делится на

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

44

Теорема. Пусть дано сравнение ax ≡ b (mod m), где (a, m) = 1. Тогда решение сравнения имеет вид

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

Пример. Решить сравнение 6x ≡ 8 (mod 5). Решение.

x = 6ϕ(5) − 1 ∙8 (mod 5) = 64 - 1 ∙ 8 (mod 5) = 1728 (mod 5) = 3.

45