Шпаргалки / Математика / Школа / Дискретная математика

Кольцо вычетов

Шпора: Кольцо вычетов \(\mathbb{Z}_n\)

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

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

\[ [a]_n = \{ a + kn \mid k \in \mathbb{Z} \} \]
  • Два числа \(a\) и \(b\) принадлежат одному классу вычетов, если:
\[ a \equiv b \pmod{n} \quad \Leftrightarrow \quad n \mid (a-b) \]

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

\[ \mathbb{Z}_n = \{ [0], [1], [2], \dots, [n-1] \} \]

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

Сложение:

\[ [a] + [b] = [a+b] \]

Умножение:

\[ [a] \cdot [b] = [a \cdot b] \]

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

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

  1. Ассоциативность:
\[ [a]+([b]+[c]) = ([a]+[b])+[c], \quad [a]\cdot([b]\cdot[c]) = ([a]\cdot[b])\cdot[c] \]
  1. Коммутативность:
\[ [a]+[b] = [b]+[a], \quad [a]\cdot[b] = [b]\cdot[a] \]
  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. Дистрибутивность:
\[ [a]\cdot([b]+[c]) = [a]\cdot[b] + [a]\cdot[c] \]

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\) — произведение простых чисел
    • Двоичная и шестнадцатеричная системы прямо используют кольца вычетов для битовых операций

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

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

\[ 3x \equiv 4 \pmod{7} \]

Решение:

  1. Проверяем делимость и обратный элемент
    • Модуль \(7\) простое → каждое ненулевое число имеет обратный по умножению.
    • Нужно найти \([3]^{-1}\) в \(\mathbb{Z}_7\) (обратное к 3):
\[ 3 \cdot y \equiv 1 \pmod{7} \]
  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. Умножаем обе стороны уравнения на обратный элемент:
\[ x \equiv 5 \cdot 4 \pmod{7} \]
\[ x \equiv 20 \equiv 6 \pmod{7} \]

Ответ:

\[ \boxed{x \equiv 6 \pmod{7}} \]

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

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