группа обратимых элементов кольца вычетов

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

Сравнение по модулю натурального числа — отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются) после достижения определенного значения.

В дискретной математике, для сравнений по модулю используется также термин модульная (или модулярная) арифметика.

Содержание

Определения

Утверждение « a и b сравнимы по модулю n » записывается в виде:

Свойства

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: , однако, сократив на 2, мы получаем ошибочное сравнение: . Правила сокращения для сравнений следующие.

Нельзя также выполнять операции со сравнениями, если их модули не совпадают.

Классы вычетов

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается или .

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

[a]_n + [b]_n = [a + b]_n

Относительно этих операций множество является конечным кольцом, а если n простое — конечным полем.

Решение сравнений

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

В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:

Решение такого сравнения начинается с вычисления НОД(a, m)=d. При этом возможны 2 случая:

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: , эквивалентное двум решениям по модулю 22: .

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

Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.

История

В значительной степени теория делимости и вычетов была создана Эйлером. Сравнения по модулю впервые использовались Гауссом в его книге «Арифметические исследования», 1801 год. Он же предложил утвердившуюся в математике символику для сравнений.

Ссылки

Полезное

Смотреть что такое «Кольцо вычетов» в других словарях:

Кольцо (алгебра) — Кольцо это множество, на котором заданы две операции, «сложение» и «умножение», со свойствами, напоминающими сложение и умножение целых чисел. Содержание 1 Определения 2 Связанные определения 3 Простейшие свойства … Википедия

Кольцо (множество) — Кольцо это множество, на котором заданы две операции, «сложение» и «умножение», со свойствами, напоминающими сложение и умножение целых чисел. Содержание 1 Определения 2 Связанные определения 3 Простейшие свойства … Википедия

Кольцо (математика) — У этого термина существуют и другие значения, см. Кольцо. В абстрактной алгебре кольцо это один из наиболее часто встречающихся видов алгебраической структуры. Простейшими примерами колец являются алгебры чисел (целых, вещественных,… … Википедия

Кольцо алгебраическое — Кольцо алгебраическое, одно из основных понятий современной алгебры. Простейшими примерами К. могут служить указанные ниже системы (множества) чисел, рассматриваемые вместе с операциями сложения и умножения: 1) множество всех целых положительных … Большая советская энциклопедия

Кольцо — алгебраическое, одно из основных понятий современной алгебры. Простейшими примерами К. могут служить указанные ниже системы (множества) чисел, рассматриваемые вместе с операциями сложения и умножения: 1) множество всех целых положительных … Большая советская энциклопедия

Кольцо когомологий — Гомология одно из основных понятий алгебраической топологии. Замкнутая линия гомологична нулю, если она ограничивает кусок поверхности, который отделяется от неё, если мы произведём разрез по этой линии. Например, на сфере любая замкнутая линия… … Википедия

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

АНАЛИТИЧЕСКОЕ КОЛЬЦО — кольцо ростков аналитич. функций в точке аналитического пространства. Более точно: пусть kесть поле с нетривиальным абсолютным значением (обычно предполагаемое полным) и есть fc алгебра степенных рядов от с коэффициентами в k, сходящихся в нек… … Математическая энциклопедия

ЛОКАЛЬНОЕ КОЛЬЦО — коммутативное кольцо с единицей, имеющее единственный максимальный идеал. Если А Л. к. с максимальным идеалом то факторкольцо является полем и наз. полем вычетов Л. к. А. Примеры Л. к. Любое поле или кольцо нормирования является локальным.… … Математическая энциклопедия

ДИСКРЕТНОГО НОРМИРОВАНИЯ КОЛЬЦО — дискретно нормированное кольцо, кольцо с дискретным нормированием, т. е. область целостности с единицей, в к рой существует такой элемент я, что любой ненулевой идеал порождается нек рой степенью элемента я; такой элемент наз. униформизирующим и… … Математическая энциклопедия

Источник

Вычислить группу обратимых элементов кольца вычетов Z33. Обозначив за U(Z33) множество обратимых элементов кольца Z33, я выписал элементы, которые составляют его: это элементы, взаимно простые с 33. U(Z33)= <1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32>|U(Z33)| = 20 Вопрос состоит в том, как описать структуру группы обратимых элементов? Писать таблицу Кэли для 20 элементов вообще желания нет и тем более нет желания перебирать все 20 чисел и рассматривать их степени. В Википедии нашел информацию, что для определения структуры группы можно находить примитивный(первообразный) корень, используя функцию Эйлера. Проблема в том, что, во-первых, нам этого не давали, и использовать это будет не очень правильно, а, во-вторых, не очень понятно, как, найдя примитивный корень, определить структуру группы.

задан 16 Дек ’17 22:02

1 ответ

Элементы группы Вы нашли верно. Их будет ф(33)=ф(3)ф(11)=20 (функция Эйлера). Из китайской теоремы об остатках следует, что U(33) изоморфна прямому произведению U(3)xU(11). Это сводит вопрос о строении группы к двум более простым случаям.

Группа U(3) состоит из двух элементов (1 и 2 по модулю 3). С ней всё ясно: она циклична порядка 2. Другая группа, U(11), тоже циклична (порядка 10). Это следует из общего факта о первообразных корнях. Раз он не изучался, мы можем подбором найти образующий этой группы, чего будет достаточно.

Начиная с 1 (нулевая степень), каждое число удваиваем и заменяем на остаток от деления на 11. Получается 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1. Процесс завершён: степени элемента 2 исчерпали всю группу U(11) из ненулевых остатков.

Итого U(33) изоморфна Z(2)xZ(10), что полностью описывает структуру группы. Она же изоморфна Z(2)xZ(2)xZ(5), если мы указываем примарное разложение.

Источник

Группа обратимых элементов кольца вычетов

3. Кольца и поля

Кольцом называется (непустое) множество K, на котором определены две операции (сложение и умножение), обладающие следующими свойствами:

1) множество K относительно сложения образует коммутативную группу;

2) умножение ассоциативно: для любых а, b, с ∈ K

3) сложение и умножение подчиняются дистрибутивному закону:

для любых а, b, с ∈ K.

При этом множество K, рассматриваемое лишь относительно операции сложения, называется аддитивной группой кольца.

Приведем некоторые примеры колец.

Читателю предлагается проверить выполнимость аксиом кольца в каждом из примеров. Остановимся подробнее на примере 3.

Поскольку операции над классами вычетов сводятся к операциям над числами из этих классов, то свойства ассоциативности и коммутативности этих операций вытекают из аналогичных свойств числового сложения и умножения. То же замечание относится к свойству дистрибутивности. Роль нулевого элемента при сложении играет класс 0‾. Противоположным элементом для класса вычетов r‾ ≠ 0‾ является класс n-r‾. Из определения сложения классов следует, что

В общем определении кольца не содержится требование коммутативности умножения. В том случае, если умножение обладает этим дополнительным свойством, кольцо называется коммутативным. В примерах 1-3 мы имеем как раз коммутативные кольца, а позднее (в приложении 5) познакомимся с важным примером некоммутативного кольца.

Рассмотрим таблицы умножения ненулевых элементов в кольцах вычетов Z₄ и Z₅.

Таблица 19

Таблица 20

Таблица 19 показывает, что в кольце могут существовать ненулевые элементы, произведение которых равно нулю: в Z₄ 2‾ · 2‾ = 0‾. Из этой же таблицы видно, что класс 2‾ необратим. Вообще, можно доказать, что ненулевые элементы, произведение которых равно нулю (называемые делителями нуля), всегда необратимы. С другой стороны, таблица 20 показывает, что в кольце Z₅ всякий ненулевой элемент обратим. Кольца с этим свойством имеют особое значение. Примем такое определение.

Коммутативное кольцо с единицей, в котором всякий ненулевой элемент обратим, называется полем.

Множество ненулевых элементов поля относительно умножения образует в силу определения поля коммутативную группу, которая называется мультипликативной группой поля.

Простейшими примерами числовых полей являются поле рациональных чисел Q и поле действительных чисел R (разумеется, относительно операций сложения и умножения чисел). Полем, как ясно из предыдущего, является и кольцо Z₅. Вообще, можно доказать, что при любом простом р (и только в этом случае) кольцо вычетов Z_p является полем. Оно называется полем вычетов по модулю р. В таблице 21 указаны элементы, обратные к ненулевым элементам поля вычетов Z₇.

Таблица 21

Конечные поля часто называют полями Галуа (их обозначают GF(g)); важное их свойство, используемое, в частности, и в теории кодирования, состоит в следующем:

Мультипликативная группа поля Галуа является циклической группой порядка q-1.

Образующий элемент мультипликативной группы поля Галуа называют примитивным элементом. Так, в поле Z₇ примитивным элементом является класс вычетов 3‾. Действительно, его степени

исчерпывают все ненулевые элементы поля.

Заметим, что класс 2 не является примитивным элементом в Z₇, так как среди его степеней нет, например, класса В. В то же время имеется очень много простых чисел р, для которых элемент ‾2 примитивен в Z_р. Так обстоит дело в полях Z₃, Z₅, Z₁₁ и т. д. В теории чисел известна следующая до сих пор не решенная задача:

Бесконечно ли множество тех простых чисел р, для которых ‾2 является примитивным элементом в Z_p?

Интересно, что с ответом на этот вопрос связано решение некоторых проблем теории кодирования.

Подмножество I кольца K называется его (двусторонним) идеалом, если оно само является кольцом относительно операций на K и если для любых элементов а ∈ K и b ∈ I оба произведения аb и bа принадлежат I.

Так, множество четных чисел есть идеал кольца Z. Читатель легко проверит, что и вообще всякое множество чисел, кратных какому-нибудь числу k, является идеалом кольца Z.

Рекомендуем читателю найти идеалы колец вычетов Z₅, Z₆, Z₈ и кольца многочленов R[X].

Источник