Значения · Наука и познание

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

существительное

Коротко о главном

Что такое приведённая система вычетов

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

Концептуальная иллюстрация модульной арифметики с выделенными взаимно простыми вычетами на круговой диаграмме.
Концептуальная иллюстрация модульной арифметики с выделенными взаимно простыми вычетами на круговой диаграмме.
01

Минимальная полная система взаимно простых вычетов

Набор целых чисел, который содержит по одному представителю каждого класса вычетов, взаимно простых с модулем m. Количество элементов в такой системе равно значению функции Эйлера φ(m). Любые два числа из набора имеют разный остаток при делении на m, и ни одно из них не имеет общих делителей с m (кроме 1).

Близкие слова

  • полная система взаимно простых вычетов
  • приведённый класс вычетов

Для модуля 5 приведённая система вычетов может состоять из чисел {1, 2, 3, 4}, так как все они взаимно просты с 5 и дают разные остатки.

Для модуля 8 приведённая система вычетов включает числа {1, 3, 5, 7}; четные числа исключаются, так как не являются взаимно простыми с 8.

Отличие от полной системы вычетов

Полная система вычетов по модулю m содержит ровно m чисел, представляющих все возможные остатки от деления на m (обычно от 0 до m-1). Приведённая система является её подмножеством. Из полной системы удаляются все числа, которые не являются взаимно простыми с модулем m.

Например, полная система вычетов по модулю 6: {0, 1, 2, 3, 4, 5}. Числа 0, 2, 3, 4 имеют общие делители с 6 (кроме 1). Следовательно, приведённая система будет состоять только из {1, 5}, так как φ(6) = 2. Важно понимать, что 'приведённая' здесь означает не арифметическое упрощение выражений, а сужение множества до взаимно простых представителей.

Свойства и применение

Ключевое свойство приведённой системы связано с теоремой Эйлера. Если a — любое целое число, взаимно простое с m, то произведение всех элементов приведённой системы на a также образует приведённую систему (возможно, в другом порядке). Это используется для доказательства того, что a^φ(m) ≡ 1 (mod m).

В отличие от полной системы, где сумма вычетов имеет определенные свойства деления на m, в приведённой системе сумма всех элементов также кратна m при m > 2. Например, для модуля 5 сумма 1+2+3+4=10 делится на 5.

Контекстные синонимы и ограничения замены

Термин 'приведённая система вычетов' строго математический. В разговорной речи его не заменяют другими словами без потери смысла. Иногда в литературе встречается термин 'группа обратимых элементов кольца Z/mZ', что является более абстрактным алгебраическим описанием той же структуры, но требует знания теории групп.

Нельзя называть приведённой системой просто набор взаимно простых чисел, если они не представляют все возможные классы вычетов или содержат лишние элементы, сравнимые друг с другом по модулю. Например, набор {1, 6} для модуля 5 является неправильным примером приведённой системы, так как 1 и 6 дают одинаковый остаток (1), а система должна содержать представителей всех классов взаимно простых вычетов.