7.4: Модульна арифметика

Припустимо, як завжди,\(\sim\) це відношення еквівалентності на множині\(A\). \(a \sim b\)Письмо означає,\(a\) що «еквівалентно»\(b\). У цьому випадку ми можемо захотіти\(a\) думати про рівність\(b\). Але це було б неправильно, тому що\(a\) і\(b\) є (напевно) дві різні речі. Однак ми маємо наступну фундаментальну властивість класів еквівалентності:\[a \sim b \quad \text { iff } \quad[a]=[b] .\]

Таким чином, поставивши квадратні дужки навколо\(a\) і\(b\), ми можемо перетворити просту еквівалентність в справжню рівність. Саме це робить класи еквівалентності настільки важливими. Хорошим прикладом є конгруентність по модулю\(n\).

7.4A. Цілі числа по модулю 3.

Для будь-якого\(n \in \mathbb{Z}\), ми знаємо, що конгруентність по модулю\(n\) - це відношення еквівалентності (див. Вправа\(5.1.18\)). Як приклад розглянемо випадок де\(n = 3\). Щоб підкреслити той факт\(n = 3\), що, ми включимо індекс ₃ в позначення класу еквівалентності: пишемо\([k]_{3}\), замість\([k]\).

Ми всі знаємо, що коли ціле число ділиться на 3, залишок повинен бути або 0, 1 або 2, тому вправа\(5.1.22(1)\) говорить нам, що кожне ціле число є конгруентним (по модулю 3) або 0, 1 або 2. Таким чином,

• для кожного\(k \in \mathbb{Z}\) клас еквівалентності\([k]_{3}\) повинен бути або\([0]_{3}\)\([1]_{3}\), або\([2]_{3}\). З іншого боку, легко перевірити, що немає двох 0, 1 і 2 є конгруентними (по модулю 3), тому
• \([0]_{3}\),\([1]_{3}\), і\([2]_{3}\) є трьома різними класами еквівалентності.

Таким чином, ми бачимо, що існує рівно три класи еквівалентності, а саме\([0]_{3}\),\([1]_{3}\), і\([2]_{3}\). Множина цих класів еквівалентності називається цілими числами по модулю 3. Воно позначається\(\mathbb{Z}_{3}\).

Позначення\(7.4.1\).

Позначення\([k]_{3}\) (або навіть просто\([k]\)) досить громіздкі. Для зручності ми можемо написати\(\bar{k}\) для класу еквівалентності\(k\). Таким чином,\[\mathbb{Z}_{3}=\{\overline{0}, \overline{1}, \overline{2}\} .\]

Визначення\(7.4.2\).

Ми можемо робити арифметику (додавати, віднімати і множити) на цих класах еквівалентності, так само, як ми робимо для звичайних цілих чисел. Це називається арифметичним модулем 3. Правила такі:

• \(\left.[a]_{3}+[b]_{3}=[a+b]_{3} \quad \text { (or } \bar{a}+\bar{b}=\overline{a+b}\right),\)
• \(\left.[a]_{3}-[b]_{3}=[a-b]_{3} \quad \text { (or } \bar{a}-\bar{b}=\overline{a-b}\right) \text {, and }\)
• \([a]_{3} \times[b]_{3}=[a b]_{3} \quad(\text { or } \bar{a} \times \bar{b}=\overline{a b}) .\)

(Власне, ми повинні написати\(+_{3}\)\(−_{3}\), і\(\times_{3}\), щоб вказати, що арифметика робиться по модулю 3, але ми зазвичай не будемо морочитися.)

Приклад\(7.4.3\).

У нас є\([1]_{3}+[2]_{3}=[1+2]_{3}=[3]_{3}\). Однак, оскільки ми маємо\(3 \equiv 0(\bmod 3)\)\([3]_{3} = [0]_{3}\), тому вищевказане рівняння також можна записати як

Рішення

\([1]_{3}+[2]_{3}=[0]_{3}\). Рівнозначно,\(\overline{1}+\overline{2}=\overline{0}\).

Це приклад наступного загального принципу:\[\text { If } r \text { is the remainder when } a+b \text { is divided by } 3 \text {, then } \bar{a}+{ }_{3} \bar{b}=\bar{r} \text {. }\]

Приклад\(7.4.4\).

Ось таблиця, яка показує результати додавання по модулю 3:

Рішення

\ [\ begin {масив} {c||c|c|c}
+_ {3} &\ overline {0} &\ overline {1} &
\ overline {2}\\ hline\ hline\ overline {0} &\ overline {1} &\ overline {2}
\ hline\ overline {1} 1} &\ оверлайн {2} &\ оверлайн {0}\\
\ hline\ overline {2} &\ overline {2} &\ overline {0} &\ overline {1}
\ end {масив}\]

Вправа\(7.4.5\).

Складіть таблицю, в якій наведені результати:

1. віднімання по модулю 3
2. множення по модулю 3

(Запишіть кожен із записів вашої таблиці як\(\overline{0}, \overline{1}\) або\(\overline{2}\).)

7.4Б. Цілі числа по модулю\(n\).

Попереднє обговорення можна узагальнити, щоб застосувати\(n\) будь-яке ціле число замість 3. Це призводить до модульної арифметики.

Визначення\(7.4.6\).

Виправте деякі ненульові натуральне число\(n \in \mathbb{N}^{+}\).

1. Для будь-якого цілого числа\(k\) ми використовуємо\([k]_{n}\) для позначення класу еквівалентності\(k\) під модулем конгруентності\(n\). Коли\(n\) зрозуміло з контексту, ми можемо написати\(\overline{k}\) замість\([k]_{n}\).
2. Множина цих класів еквівалентності називається цілими числами по модулю\(n\). Воно позначається\(\mathbb{Z}_{n}\).
3. Додавання, віднімання та множення за модулем\(n\) визначаються:
   • \(\bar{a}+{ }_{n} \bar{b}=\overline{a+b}\),
   • \(\bar{a}-{ }_{n} \bar{b}=\overline{a-b}\), і
   • \(\bar{a} \times_{n} \bar{b}=\overline{a b}\).

(Коли\(n\) зрозуміло з контексту, ми зазвичай пишемо\(+\)\(−\), і\(\times\), а не\(+_{n}\)\(−_{n}\), і\(\times_{n}\).)

Зауважте, що\(\# \mathbb{Z}_{n}=n\). Точніше:

Пропозиція\(7.4.7\).

Для будь-якого\(n \in \mathbb{N}^{+}\), у нас є\[\mathbb{Z}_{n}=\{\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\}\]

і\(\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\) всі різні.

Приклад\(\PageIndex{1}\)

Спростити\((\overline{17}-\overline{5}) \times(\overline{21}+\overline{11})\) в\(\mathbb{Z}_{7}\).

Рішення

У нас є\ [\ begin {вирівняний}
(\ overline {17} -\ overline {5})\ раз (\ overline {21} +\ overline {11}) & =(\ overline {3} -\ overline {5})\ times (\ overline {0} +\ overline {4}) =( 3-5)\ раз (\ overline {0+4})\
&=\ overline {-2}\ раз\ overline {4} =\ overline {5}\ times\ overline {4} =\ overline {5\ times 4 } =\ оверлайн {20} =\ оверлайн {6}.
\ end {вирівняний}\]

Вправа\(7.4.9\).

1. Спростити\((\overline{17}-\overline{5}) \times(\overline{21}+\overline{11})\) в\(\mathbb{Z}_{5}\).
2. Спростити\(\overline{32}+(\overline{23} \times \overline{16})\) в\(\mathbb{Z}_{9}\).
3. Спростити\((\overline{25} \times \overline{35})+(\overline{18}-\overline{12})\) в\(\mathbb{Z}_{12}\).
4. Складіть таблиці, які показують результати:
   1. додавання по модулю 4.
   2. віднімання по модулю 5.
   3. множення по модулю 6.
5. Знайти\(x, y \in \mathbb{Z}_{12}\), такий що\(x \neq \overline{0}\) і\(y \neq \overline{0}\), але\(x y=\overline{0}\).