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

Приведённая система вычетов — это в теории чисел и модульной арифметике подмножество полной системы вычетов по модулю \(m\), состоящее из всех чисел, взаимно простых с модулем \(m\). Классически она определяется как множество всех целых чисел от 0 до \(m-1\), которые не имеют общих делителей с \(m\), кроме 1. Приведённая система вычетов играет ключевую роль в теории сравнений, криптографии (например, в алгоритме RSA) и в доказательстве теоремы Эйлера.

Определение и основные свойства

Пусть \(m\) — натуральное число, большее 1. Приведённая система вычетов по модулю \(m\) состоит из всех чисел \(a\) из полной системы вычетов \(\{0, 1, 2, \dots, m-1\}\), для которых выполняется условие \(\gcd(a, m) = 1\) (наибольший общий делитель равен 1). Число элементов в такой системе равно значению функции Эйлера \(\varphi(m)\). Например, для \(m = 12\) полная система вычетов — \(\{0,1,2,3,4,5,6,7,8,9,10,11\}\). Из них взаимно просты с 12 числа: 1, 5, 7, 11. Таким образом, приведённая система вычетов по модулю 12 — \(\{1,5,7,11\}\), а \(\varphi(12) = 4\).

Ключевые свойства:

• Любое целое число, взаимно простое с \(m\), сравнимо ровно с одним элементом приведённой системы по модулю \(m\).
• Приведённая система вычетов замкнута относительно умножения по модулю \(m\): произведение любых двух её элементов, взятое по модулю \(m\), также принадлежит этой системе.
• Множество классов вычетов, взаимно простых с модулем, образует мультипликативную группу (группу обратимых элементов кольца вычетов \(\mathbb{Z}/m\mathbb{Z}\)).

История

Понятие приведённой системы вычетов восходит к работам Леонарда Эйлера, который в 1763 году ввёл функцию \(\varphi(n)\) для подсчёта количества чисел, меньших \(n\) и взаимно простых с ним. Впоследствии Карл Фридрих Гаусс в своём труде «Арифметические исследования» (1801) систематизировал теорию сравнений, включая свойства приведённых систем. Гаусс использовал их для доказательства малой теоремы Ферма и теоремы Эйлера.

Способы построения

Приведённую систему вычетов можно построить несколькими способами:

1. Выбор из полной системы

Из полной системы вычетов \(\{0,1,\dots,m-1\}\) отбираются все числа, для которых \(\gcd(a,m)=1\). Нуль исключается всегда, так как \(\gcd(0,m)=m > 1\) для \(m>1\).

2. По модулю простого числа

Если \(m = p\) — простое число, то все числа от 1 до \(p-1\) взаимно просты с \(p\). Следовательно, приведённая система вычетов по простому модулю — \(\{1,2,\dots,p-1\}\), а \(\varphi(p) = p-1\).

3. По модулю степени простого числа

Для \(m = p^k\) (где \(p\) — простое, \(k \ge 1\)) приведённая система состоит из всех чисел от 1 до \(p^k-1\), не кратных \(p\). Количество таких чисел равно \(\varphi(p^k) = p^k - p^{k-1}\). Например, для \(m=9\): \(\{1,2,4,5,7,8\}\).

4. Через мультипликативную группу

Приведённая система вычетов изоморфна мультипликативной группе кольца вычетов. Для составного модуля её можно построить, используя китайскую теорему об остатках: если \(m = m_1 m_2\) и \(\gcd(m_1,m_2)=1\), то приведённая система по модулю \(m\) состоит из всех чисел вида \(a_1 m_2 + a_2 m_1\) (по модулю \(m\)), где \(a_1\) пробегает приведённую систему по модулю \(m_1\), а \(a_2\) — по модулю \(m_2\).

Применение

Теорема Эйлера

Теорема Эйлера утверждает, что для любого целого числа \(a\), взаимно простого с \(m\), выполняется сравнение: \[ a^{\varphi(m)} \equiv 1 \pmod{m}. \] Доказательство опирается на то, что умножение всех элементов приведённой системы на \(a\) (по модулю \(m\)) даёт перестановку этой же системы, и произведение всех элементов системы равно \(a^{\varphi(m)}\) раз произведению тех же элементов.

Криптография

В алгоритме RSA (разработан в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлеманом) используется приведённая система вычетов по модулю \(n = p \cdot q\), где \(p\) и \(q\) — большие простые числа. Размерность группы обратимых элементов равна \(\varphi(n) = (p-1)(q-1)\). Выбор открытой экспоненты \(e\) и вычисление секретной экспоненты \(d\) происходит в этой группе, что обеспечивает однозначность расшифровки.

Теория чисел

Приведённые системы вычетов применяются для доказательства свойств квадратичных вычетов, решения диофантовых уравнений и исследования мультипликативных функций.

Примеры

Пример 1: модуль 15

Полная система: \(\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}\). Числа, взаимно простые с 15: 1, 2, 4, 7, 8, 11, 13, 14. \(\varphi(15)=8\). Приведённая система: \(\{1,2,4,7,8,11,13,14\}\).

Пример 2: модуль 8

Полная система: \(\{0,1,2,3,4,5,6,7\}\). Взаимно простые с 8: 1, 3, 5, 7. \(\varphi(8)=4\). Приведённая система: \(\{1,3,5,7\}\).

Пример 3: модуль 1

По определению, \(\varphi(1)=1\), и приведённая система вычетов по модулю 1 состоит из одного элемента — \(\{0\}\), так как \(\gcd(0,1)=1\).

Связь с другими понятиями

• Полная система вычетов — множество всех остатков по модулю \(m\), включая нуль. Приведённая система является её подмножеством.
• Функция Эйлера \(\varphi(m)\) — мощность приведённой системы.
• Мультипликативная группа \((\mathbb{Z}/m\mathbb{Z})^\times\) — группа обратимых элементов кольца, изоморфная приведённой системе вычетов.
• Китайская теорема об остатках — позволяет разложить приведённую систему по составному модулю на произведение систем по взаимно простым множителям.

Интересные факты

• Если модуль \(m\) является простым, приведённая система вычетов совпадает с полной системой без нуля.
• Приведённая система вычетов по модулю \(m\) является циклической группой тогда и только тогда, когда \(m\) равно 1, 2, 4, \(p^k\) или \(2p^k\), где \(p\) — нечётное простое число.
• В криптографии размер приведённой системы (значение \(\varphi(m)\)) определяет сложность взлома RSA: чем больше \(\varphi(m)\), тем выше стойкость алгоритма.

Источники

• Виноградов И. М. «Основы теории чисел». — М.: Наука, 1972.
• Гаусс К. Ф. «Арифметические исследования». — М.: Изд-во АН СССР, 1959.
• Бухштаб А. А. «Теория чисел». — М.: Просвещение, 1966.
• Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ». — М.: Вильямс, 2013.