Мультипликативная группа кольца вычетов

Мультипликативная группа кольца вычетов — это множество всех обратимых элементов кольца вычетов по модулю \(n\), образующих группу относительно операции умножения по модулю \(n\). Обозначается \( (\mathbb{Z}/n\mathbb{Z})^\times \), \( U_n \) или \( \mathbb{Z}_n^* \). Эта группа является фундаментальным объектом теории чисел, алгебраической и аналитической теории чисел, а также криптографии.

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

Пусть \( \mathbb{Z}/n\mathbb{Z} \) — кольцо классов вычетов по модулю \(n\) (где \(n\) — натуральное число, \(n \ge 1\)). Элемент \(a \in \mathbb{Z}/n\mathbb{Z}\) называется обратимым, если существует такой элемент \(b \in \mathbb{Z}/n\mathbb{Z}\), что \(a \cdot b \equiv 1 \pmod{n}\). Множество всех обратимых элементов образует группу относительно умножения, которая и называется мультипликативной группой кольца вычетов.

Критерий обратимости: Элемент \(a\) обратим по модулю \(n\) тогда и только тогда, когда \(\gcd(a, n) = 1\) (наибольший общий делитель \(a\) и \(n\) равен 1). Таким образом, \( (\mathbb{Z}/n\mathbb{Z})^\times \) состоит из всех классов вычетов, взаимно простых с \(n\).

Порядок группы: Число элементов мультипликативной группы равно значению функции Эйлера \(\varphi(n)\): \[ |(\mathbb{Z}/n\mathbb{Z})^\times| = \varphi(n). \]

Структура группы: Группа \( (\mathbb{Z}/n\mathbb{Z})^\times \) является конечной абелевой группой. Её строение зависит от разложения \(n\) на простые множители. В общем случае, по китайской теореме об остатках, если \(n = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}\) — каноническое разложение на простые числа, то: \[ (\mathbb{Z}/n\mathbb{Z})^\times \cong (\mathbb{Z}/p_1^{k_1}\mathbb{Z})^\times \times (\mathbb{Z}/p_2^{k_2}\mathbb{Z})^\times \times \dots \times (\mathbb{Z}/p_r^{k_r}\mathbb{Z})^\times. \] То есть группа является прямым произведением групп по модулям простых степеней.

Строение по модулям простых степеней

По модулю простого числа \(p\)

Для \(n = p\), где \(p\) — простое число, группа \( (\mathbb{Z}/p\mathbb{Z})^\times \) является циклической порядка \(p-1\). Это один из классических результатов теории чисел: существует первообразный корень по модулю \(p\) — элемент \(g\), такой, что его степени \(g^0, g^1, \dots, g^{p-2}\) дают все ненулевые вычеты по модулю \(p\). Таким образом, \( (\mathbb{Z}/p\mathbb{Z})^\times \cong C_{p-1}\) (циклическая группа порядка \(p-1\)).

По модулю \(p^k\) (степень простого нечётного числа)

Для нечётного простого \(p\) и \(k \ge 1\) группа \( (\mathbb{Z}/p^k\mathbb{Z})^\times \) также является циклической. Её порядок равен \(\varphi(p^k) = p^{k-1}(p-1)\). Существует первообразный корень по модулю \(p^k\), который можно получить из первообразного корня по модулю \(p\) с помощью определённой процедуры (например, если \(g\) — первообразный корень по модулю \(p\), то либо \(g\), либо \(g+p\) будет первообразным корнем по модулю \(p^k\)).

По модулю \(2^k\)

Случай степени двойки является исключением:

• Для \(n = 2\): \( (\mathbb{Z}/2\mathbb{Z})^\times \) состоит из одного элемента (класса 1) — тривиальная группа.
• Для \(n = 4\): \( (\mathbb{Z}/4\mathbb{Z})^\times = \{1, 3\} \) — циклическая группа порядка 2.
• Для \(n = 2^k\) при \(k \ge 3\): группа \( (\mathbb{Z}/2^k\mathbb{Z})^\times \) не является циклической. Она изоморфна прямому произведению циклических групп: \( C_2 \times C_{2^{k-2}} \). Например, для \(n=8\): \( (\mathbb{Z}/8\mathbb{Z})^\times = \{1,3,5,7\} \) — группа Клейна \(C_2 \times C_2\).

Примеры

• n = 5: \( (\mathbb{Z}/5\mathbb{Z})^\times = \{1,2,3,4\} \). Порядок 4. Циклическая группа. Первообразный корень: 2 (так как \(2^1=2, 2^2=4, 2^3=3, 2^4=1\)).
• n = 8: \( (\mathbb{Z}/8\mathbb{Z})^\times = \{1,3,5,7\} \). Порядок 4. Нециклическая: \(3^2 \equiv 1 \pmod{8}\), \(5^2 \equiv 1 \pmod{8}\), \(7^2 \equiv 1 \pmod{8}\). Каждый нетривиальный элемент имеет порядок 2. Группа изоморфна \(C_2 \times C_2\).
• n = 9: \( (\mathbb{Z}/9\mathbb{Z})^\times = \{1,2,4,5,7,8\} \). Порядок 6. Циклическая. Первообразный корень: 2 (степени: 2,4,8,7,5,1).
• n = 12: \( (\mathbb{Z}/12\mathbb{Z})^\times = \{1,5,7,11\} \). Порядок 4. Нециклическая (аналогично \(n=8\)).

Применение

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

Мультипликативная группа кольца вычетов лежит в основе многих криптографических систем с открытым ключом:

• RSA: Безопасность основана на трудности факторизации больших чисел и вычисления дискретного логарифма в группе \( (\mathbb{Z}/n\mathbb{Z})^\times \), где \(n\) — произведение двух больших простых чисел.
• Диффи-Хеллман: Обмен ключами выполняется в циклической подгруппе \( (\mathbb{Z}/p\mathbb{Z})^\times \) для большого простого \(p\).
• Эль-Гамаль: Шифрование и цифровая подпись также используют циклические группы по модулю простого числа.

Теория чисел

• Теорема Эйлера: Для любого \(a\), взаимно простого с \(n\), \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Это прямое следствие теоремы Лагранжа для конечных групп, применённой к \( (\mathbb{Z}/n\mathbb{Z})^\times \).
• Малая теорема Ферма: Частный случай для \(n=p\) (простого): \(a^{p-1} \equiv 1 \pmod{p}\).
• Проверка простоты: Тест Миллера — Рабина основан на свойствах группы \( (\mathbb{Z}/n\mathbb{Z})^\times \).

Алгебра

• Изучение строения конечных абелевых групп. Группы \( (\mathbb{Z}/n\mathbb{Z})^\times \) являются классическими примерами, иллюстрирующими теорему о классификации конечных абелевых групп.
• Построение полей Галуа: Для простого \(p\) поле \( \mathbb{F}_p \) изоморфно \( \mathbb{Z}/p\mathbb{Z} \), а его мультипликативная группа — циклическая.

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

• Первообразные корни: Существуют только для модулей \(n = 1, 2, 4, p^k, 2p^k\), где \(p\) — нечётное простое число, \(k \ge 1\). Для всех остальных \(n\) группа не является циклической.
• Порядок элементов: Порядок любого элемента \(a \in (\mathbb{Z}/n\mathbb{Z})^\times\) делит \(\varphi(n)\). Наименьшее положительное \(d\), такое, что \(a^d \equiv 1 \pmod{n}\), называется порядком \(a\) по модулю \(n\).
• Группа автоморфизмов: Мультипликативная группа кольца вычетов изоморфна группе автоморфизмов аддитивной группы \( \mathbb{Z}/n\mathbb{Z} \).

Источники

• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.
• Ленг С. Алгебра. — М.: Мир, 1968.
• Кострикин А. И. Введение в алгебру. Часть I. Основы алгебры. — М.: Физматлит, 2004.