Арифметика остатков

[Mathdream]

Начал разбираться с арифметикой остатков (читаю книгу по криптографии) и загнал себя в угол. Не пойму, верны ли тезисы:

1. Сумма остатков от деления чисел $a$ и $b$ на число $n$ равна остатку от деления суммы чисел $a$ и $b$ на число $n$.

Ниже простой пример, показывающий, что это неверно.

Пример:
$103 \mod 5 + 63 \mod 5 = 3 +3 =6$
$(103+63) \mod 5 = 1$
Следовательно,
$a \mod n + b \mod n \ne (a+b) \mod n$
Причем похоже, что:
$(a\mod n + b\mod n)\mod n = (a+b) \mod n$

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

2. Произведение остатков от деления чисел $a$ и $b$ на число $n$ равна остатку от деления произведения чисел $a$ и $b$ на число $n$.

Опять опровержение:
$(5 \mod 3) * (11 \mod 3) = 2 * 2 = 4$
$(5 * 11) \mod 3 = 55 \mod 3 = 1$
Итог:
$(a \mod n) * (b \mod n) \ne (a*b) \mod n$

Прошу помочь разобраться или посоветовать какой-то "эффективный способ мышления" об остатках, за что зацепиться, с чего начать. Просто в прошлый раз с ними сталкивался в начальной школе...

[Профессор Снэйп]

Mathdream в сообщении #400053 писал(а):

1. Сумма остатков от деления чисел a и b на число n равна остатку от деления суммы чисел a и b на число n.

Это неточно. Точно будет так: остаток от деления на $n$ суммы остатков от деления чисел $a$ и $b$ на число $n$ равен остатку от деления суммы чисел $a$ и $b$ на число $n$. Другими словами, остаток суммы остатков равен остатку суммы исходных чисел. Или, формульно,

$$ (a \mod n + b \mod n) \mod n = (a + b) \mod n $$

-- Пт янв 14, 2011 23:19:36 --

Mathdream в сообщении #400053 писал(а):

2. Произведение остатков от деления чисел a и b на число n равна остатку от деления произведения чисел a и b на число n.

То же самое:

$$ ((a \mod n) \cdot (b \mod n)) \mod n = (a \cdot b) \mod n $$

-- Пт янв 14, 2011 23:21:00 --

Mathdream в сообщении #400053 писал(а):

Прошу помочь разобраться или посоветовать какой-то "эффективный способ мышления" об остатках, за что зацепиться, с чего начать. Просто в прошлый раз с ними сталкивался в начальной школе...

Главный и единственный совет: узнать, что такое кольцо $\mathbb{Z}_n$.

-- Пт янв 14, 2011 23:28:13 --

Если слово "кольцо" вдруг пугает, представьте себе круглый циферблат часов, размеченный числами $0,1,\ldots,n-1$ через равномерные промежутки (классический циферблат --- для $n = 12$, только $12$ надо заменить на $0$). Кроме того, к циферблату приделана часовая стрелка, которая проходит одно деление в час. Теперь если мы выставим часовую стрелку часовую стрелку на $0$ и подождём $a$ часов, то она укажет на $a \mod n$...

(Оффтоп)

Кстати, слышал, что термин "кольцо" происходит как раз от этого циферблата

-- Пт янв 14, 2011 23:37:29 --

Ну, или в конце концов...

На множестве остатков $\{ 0, 1, \ldots, n-1 \}$ рассмотрите две операции: "сумму" $a \oplus b = (a + b) \mod n$ и "произведение" $a \otimes b = (a \cdot b) \mod n$. Эти операции подчиняются всем известным законам арифметики целых чисел, которые учат в школе: $a \oplus b = b \oplus a$, $a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$ и и. д. То, что Вы пытались понять, суть следующее: $(a \mod n) \oplus (b \mod n) = (a + b) \mod n$, $(a \mod n) \otimes (b \mod n) = (a \cdot b) \mod n$. В тех отрывках из учебника, которые Вы цитируете, происходит некоторая подмена понятий. Например:

Mathdream в сообщении #400053 писал(а):

Сумма остатков от деления чисел $a$ и $b$ на число $n$ равна остатку от деления суммы чисел $a$ и $b$ на число $n$.

Синее слово "сумма" указывает на операцию $\oplus$, красное --- на обычный $+$. Автору учебника это очевидно, а вот Вы запутались

С произведением то же самое.