Проверка структуры группы

[gogoshik]

В задаче необходимо проверить, что множество $M = \{0, 1, 2, ..., n-1\} $ с бинарной операцией (обозначим $\otimes$) сложения по $\bmod(n)$ является группой.

Думаю, что не является, так как не выполняется аксиома ассоциативности.

Пример: $(0 \otimes 1) \otimes 2 = 2 \otimes 2 = 1$, $0 \otimes (1 \otimes 2) = 0 \otimes 0 = 0$ для $M^{*} = \{0, 1, 2\} $ со сложением по $\bmod(3)$ .

Проверьте, плиз, что-то может не так?

[gris]

$(0 \otimes 1) = 2 $ .

[gogoshik]

gris, спасибо. Видимо я плохо разобрался с этой темой. Обычно мне попадались операции сложения по $\bmod 2$. В таком случае $0 \oplus 1 = 1$ (это я зазубрил). Ну, поэтому я автоматом подумал, как это так, что по $\bmod (3)$ так же будет единица и написал глупость.

Может быть подскажите источник, где тема сложения по разным модулям (отличным от 2) хорошо объясняется?

[gris]

Это сравнения по модулю, арифметика остатков, кольца вычетов (к сложению прекрасно добавляется и умножение по тому же модулю) и другие синонимы. Там есть разные уровни и выходы в алгебру, теорию чисел, криптографию и прочие области.

[gogoshik]

Спасибо. В данной задаче можно рассмотреть какой-то один случай (пусть $n=3$) или её нужно решать в более общем случае?

[gris]

Это для опровержения хватило бы одного случая. А для доказательства придётся рассмотреть общий случай и проверить все аксиомы группы. Если интересует основательно, то посмотрите "Теорию чисел" Бухштаба. Он уж не отдаёт даже простые вопросы для самостоятельного доказательства.

[arseniiv]

gogoshik
Вам может помочь доказать сначала такие факты:
1. $((a + b)\bmod n + c)\bmod n = (a + b + c)\bmod n$.
2. $((a \cdot b)\bmod n \cdot c)\bmod n = (a \cdot b \cdot c)\bmod n$ ← это когда кольца будут.
3. $(a\bmod n)\bmod n = a\bmod n$ (авось и этот тривиальный мог быть забыт).

А группу $\mathbb Z_n$ можно представлять себе как «свёрнутую в рулон» (разного размера в зависимости от $n$) целочисленную прямую $\mathbb Z$. Да и её саму как «рулон» бесконечного радиуса (это находит отражение в терминологии: и $\mathbb Z_n$, и $\mathbb Z$ — и только их — зовут циклическими группами).

[Walker_XXI]

gogoshik в сообщении #1323768 писал(а):

Видимо я плохо разобрался с этой темой. Обычно мне попадались операции сложения по $\bmod 2$.

Может быть подскажите источник, где тема сложения по разным модулям (отличным от 2) хорошо объясняется?

Ну даже не знаю. По-моему, сложение целых чисел неплохо и в начальной школе объясняют. Сложение "по модулю $n$" - это обычное сложение за тем исключением, что результат "берется по модулю" - т.е. результатом сложения по модулю является остаток от деления обычной суммы (обычных целых чисел) на $n$. Примеры взятия модуля:

$$\begin{array}{rcl} 2\bmod 3&=&2 \\ 3\bmod 3&=&0 \\ 4\bmod 3&=&1 \\ \end{array} $$

и т.д.

А сложение по модулю, пока результат $<n$, - самое обычное (уже без дополнительных оговорок).

Как уже упоминали, визуально это можно представить, как закольцовывание цепочки целых чисел, когда $n$ отождествляется с $0$.
Кстати, со сложением по модулю 10 мы сталкиваемся с раннего детства, когда узнаём о десятичной системе записи чисел и учимся складывать в столбик: каждый разряд результата - это сумма соответствующих разрядов слагаемых по модулю 10 (нюансы с переносом в след. разряд тут не существенны).