1. Определение

Класс вычетов по модулю $n$:

• Два числа $a$ и $b$ принадлежат одному классу вычетов, если:

Кольцо вычетов по модулю $n$:

2. Операции в кольце

Сложение:

Умножение:

Все операции выполняются по модулю $n$.

3. Свойства кольца

1. Ассоциативность:

1. Коммутативность:

1. Нейтральные элементы:
   • Для сложения: $[0]$, т.е. $[a]+[0] = [a]$
   • Для умножения: $[1]$, т.е. $[a]\cdot[1] = [a]$
2. Обратные элементы:
   • По сложению: $[-a] = [n-a]$, так что $[a]+[-a] = [0]$
   • По умножению (если $n$ простое): для каждого $[a] \neq [0]$ существует $[b]$ такой, что $[a]\cdot[b] = [1]$
3. Дистрибутивность:

4. Особые случаи

1. $n$ простое:
   • $\mathbb{Z}_n$ — поле.
   • Каждое ненулевое $[a]$ имеет обратный по умножению.
2. $n$ составное:
   • Могут быть «делители нуля»: $[a]\cdot[b] = [0]$, но $[a]\neq[0], [b]\neq[0]$

5. Примеры

Пример 1: $\mathbb{Z}_5 = { [0],[1],[2],[3],[4] }$

• $[3]+[4] = [7] = [2]$
• $[2]\cdot[3] = [6] = [1]$

Пример 2: $\mathbb{Z}_6 = { [0],[1],[2],[3],[4],[5] }$

• $[2]\cdot[3] = [6] = [0]$ (делитель нуля!)

6. Использование

• Решение конгруэнций: $ax \equiv b \pmod{n}$
• Теория чисел: остатки, простые числа, делимость
• Криптография: RSA, шифры на основе модульной арифметики
• Алгебраические структуры: изучение колец и полей

Коротко в один абзац:

Кольцо вычетов $\mathbb{Z}_n$ — это мир чисел по модулю $n$, где остатки складываются и умножаются по кругу, есть ноль, единица, иногда обратные элементы, и всё это позволяет решать уравнения, изучать закономерности и строить алгебру на остатках.

Связь с системами счисления

Любая система счисления — это работа по модулю основания:

• Двоичная: 0 и 1 → модуль 2 → $\mathbb{Z}_2$
• Десятичная: 0…9 → модуль 10 → $\mathbb{Z}_{10}$
• Шестнадцатеричная: 0…F → модуль 16 → $\mathbb{Z}_{16}$

То есть, когда ты пишешь числа в любой системе счисления, ты на самом деле используешь кольцо вычетов без шума. Остатки при делении на основание — это и есть классы вычетов.

Пример: число 27 в двоичной системе:

1. Делим на 2, остаток 1 → младший разряд
2. Делим 13 на 2, остаток 1 → следующий
3. Делим 6 на 2, остаток 0 → следующий
4. Делим 3 на 2, остаток 1 → старший

Все эти остатки — это элементы $\mathbb{Z}_2$, с которыми ты складываешь, умножаешь и переносишь разряды.

очему кольцо вычетов удобно

• Цикличность: после $n$ чисел все остатки повторяются → прям как в часах, это помогает моделировать повторяющиеся процессы, счёт, календари, крипту.
• Математическая строгость: можно формально доказывать свойства сложения и умножения без хаоса.
• Обратимые элементы: позволяют решать уравнения, делить, строить поля, а значит, создавать шифры, коды и циклические структуры.

  Примеры применения с системами счисления

1. Калькулятор и перенос разрядов:
   • При сложении 9 + 8 в десятичной системе:
     $9 + 8 = 17 \equiv 7 \pmod{10}$ → переносим 1 в старший разряд.
2. Коды ошибок:
   • CRC, контрольные суммы → остатки по модулю 2 или 256 ($\mathbb{Z}2$ или $\mathbb{Z}{256}$)
3. Криптография:
   • RSA → работа с $\mathbb{Z}_n$, где $n$ — произведение простых чисел
   • Двоичная и шестнадцатеричная системы прямо используют кольца вычетов для битовых операций

     Пример задачи с кольцом вычетов

Задача:
Решить уравнение по модулю:

Решение:

1. Проверяем делимость и обратный элемент
   • Модуль $7$ простое → каждое ненулевое число имеет обратный по умножению.
   • Нужно найти $[3]^{-1}$ в $\mathbb{Z}_7$ (обратное к 3):

1. Подбираем обратный элемент вручную:
   • $3\cdot1 = 3 \neq 1$
   • $3\cdot2 = 6 \neq 1$
   • $3\cdot3 = 9 \equiv 2 \neq 1$
   • $3\cdot5 = 15 \equiv 1 \pmod{7}$ ✅

Значит, $[3]^{-1} = [5]$

1. Умножаем обе стороны уравнения на обратный элемент:

Ответ:

Комментарий:

• Проверка: $3 \cdot 6 = 18 \equiv 4 \pmod{7}$ — верно.
• Если бы модуль был составной, нужно было бы проверить, делится ли правая часть на $gcd(3,7)$ — в нашем случае $gcd(3,7)=1$, проблем нет.