1.4: Цілі числа по модулю m
- Page ID
- 63404
У цьому розділі ми постараємося відповісти на питання:
- Що таке відносини еквівалентності?
- Що таке конгруентність по модулю\(m\text{?}\)
- Як арифметика в\(\mathbb{Z}_m\) порівнянні з арифметикою в\(\mathbb{Z}\text{?}\)
Фундамент для нашого дослідження абстрактної алгебри майже завершений. Нам потрібні основи ще однієї «системи числення», щоб оцінити абстрактний підхід, розроблений в наступних розділах. Для побудови цієї системи числення потрібен короткий огляд відносин та рівнозначності. Нагадаємо, що задані\(T\text{,}\) множини\(S\) і декартовий добуток\(S\) з\(T\text{,}\) позначається\(S\times T\) (\(T\)«\(S\)хрест»), є множиною всіх можливих впорядкованих пар, перший елемент яких від,\(S\) а другий елемент - від\(T\text{.}\) Символічно,
\ begin {рівняння*} S\ раз T =\ {(s, t): s\ in S,\ t\ in T\}. \ end {рівняння*}
\(S\)Дозволяти бути непорожнім набором. \(R\)Відношення на\(S\) є підмножиною\(S\times S\text{.}\) Якщо\(x,y\in S\) такі, що\((x,y)\in R\text{,}\) ми зазвичай пишемо\(xRy\) і говоримо, що\(x\) і\(y\) пов'язані під \(R\).
Поняття відношення, представлене вище, надзвичайно відкрите. Будь-яка підмножина впорядкованих пар\(S\times S\) описує відношення на множині\(S\text{.}\) Звичайно, деякі відносини є більш значущими, ніж інші; галузь математики, відома як теорія порядку вивчає відносини порядку (наприклад, знайомі\(\lt\)). Наша увага буде зосереджена на рівнозначності відносин, які виділяють важливі риси\(=\text{.}\)
\(S\)Дозволяти бути непорожнім набором. Ми говоримо, що відношення\(\sim\) на\(S\) це відношення еквівалентності, якщо наступні властивості мають:
- \(\sim\)є рефлексивним: якщо\(a\in S\text{,}\) тоді\(a\sim a\text{.}\)
- \(\sim\)симетрична: якщо\(a,b\in S\) з\(a\sim b\text{,}\) то\(b\sim a\text{.}\)
- \(\sim\)є перехідним: якщо\(a,b,c\in S\) з\(a\sim b\) і\(b\sim c\text{,}\) потім\(a\sim c\text{.}\)
З огляду\(x\in S\text{,}\) на набір
\ begin {рівняння*}\ оверлайн {x} =\ {y\ in S: x\ sim y\}\ end {рівняння*}
називається класом еквівалентності \(x\). Будь-який елемент\(z\in \overline{x}\) називається представником класу еквівалентності.
Доведіть, що «має той же день народження, як» є відношення еквівалентності на\(P\) безлічі всіх людей.
Які ще відносини ви можете придумати? Запишіть один приклад і один неприклад співвідношення еквівалентності.
Доведіть, що\(\le\) це не еквівалентність відношення на\(\mathbb{Z}\text{.}\)
Для наших цілей особливо важливим співвідношенням еквівалентності є конгруентність по модулю\(m\) на множині цілих чисел.
Нехай\(a,b\in \mathbb{Z}\) і\(m \in \mathbb{N}\text{,}\)\(m > 1\text{.}\) Ми говоримо, \(a\)що конгруентний по \(b\)модулю, \(m\)якщо\(m\mid a-b\text{.}\) ми пишемо\(a \equiv b\mod m\text{.}\)
Обґрунтуйте наступні конгруенції.
- \(\displaystyle 18 \equiv 6\mod 12\)
- \(\displaystyle 47 \equiv 8\mod 13\)
- \(\displaystyle 71 \equiv 1\mod 5\)
- \(\displaystyle 21 \equiv -1 \mod 11\)
- \(\displaystyle 24 \equiv 0\mod 6\)
Задана ціла\(m > 1\text{,}\) конгруентність по модулю\(m\) є співвідношенням еквівалентності на\(\mathbb{Z}\text{.}\)
Знайти всі класи еквівалентності\(\mathbb{Z}_5\) та\(\mathbb{Z}_7\text{.}\)
Нехай\(a,b, c,d\in \mathbb{Z}\) і\(m > 1\) такі, що\(a\equiv c\mod m\) і\(b\equiv d\mod m\text{.}\) тоді\(a+b \equiv c + d \mod m\text{.}\)
Нехай\(a,b, c,d\in \mathbb{Z}\) і\(m > 1\) такі, що\(a\equiv c\mod m\) і\(b\equiv d\mod m\text{.}\) тоді\(ab \equiv c d\mod m\text{.}\)
\(S\)Дозволяти множина і відношення\(\sim\) еквівалентності на\(S\text{.}\) Тоді твердження\(P\) про класи еквівалентності\(S\) добре визначено, якщо представник класу еквівалентності не має значення. Тобто, коли\(\overline{x} = \overline{y}\text{,}\)\(P(\overline{x}) = P(\overline{y})\text{.}\)
Попередні вправи виправдовують наступні визначення.
Нехай\(m > 1\) і\(a,b\in \mathbb{Z}_m\text{.}\) Тоді наведені нижче чітко визначені операції над класами еквівалентності:
- Додавання по модулю\(m\):\(\overline{a} + \overline{b} := \overline{a+b}\text{.}\)
- Множення по модулю\(m\):\(\overline{a}\cdot \overline{b} := \overline{a\cdot b}\text{.}\)
Більшість елементарних пропозицій про\(\mathbb{Z}_m\) можна переробити як твердження про\(\mathbb{Z}\text{.}\) Наприклад, доводячи Theorem Template:index ви, швидше за все, довели, що if\(m|a-c\) і\(m|b-d\) що\(m|(a+b)-(c+d)\text{.}\) Однак, коли твердження стають більш складними, багаторазово переформувати заяви про\(Z_m\) як заяви про\(\mathbb{Z}\) стає громіздким і некорисним. Замість цього вам рекомендується стати зручним робити арифметику по модулю\(m\) або, по-іншому, арифметику з класами еквівалентності,\(\mathbb{Z}_m\) як визначено в Definition: Modulo.
Не переходячи назад,\(\mathbb{Z}\text{,}\) знайти найменший невід'ємний цілий представник результуючих класів еквівалентності.
- \(\overline{5}+\overline{11}\)в\(\mathbb{Z}_{9}\)
- \(\overline{-3}+\overline{-3}\)в\(\mathbb{Z}_{6}\)
- \(\overline{8}\cdot\overline{3}\)в\(\mathbb{Z}_{19}\)
- \(\overline{-1}\cdot(\overline{3}+\overline{8})\)в\(\mathbb{Z}_{7}\)
- \(\overline{3}\cdot(\overline{5}^2+\overline{3}^3)\)в\(\mathbb{Z}_{20}\)
В решті частини цього розділу досліджено фундаментальні властивості арифметики в\(\mathbb{Z}_m\text{.}\)
Нехай\(\overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m\) з\(\overline{c}\ne\overline{0}\) і\(m > 1\text{.}\) Якщо\(\overline{a}\cdot \overline{c} = \overline{b}\cdot \overline{c}\text{,}\) це правда, що\(\overline{a} = \overline{b}\text{?}\) Якщо так, довести це. Якщо ні, знайдіть приклад того, коли оператор не вдається провести.
\(a,b,c\text{,}\)\(m\)Дозволяти і бути цілими числами з\(m > 1\) і\(\gcd(c,m)=1\text{.}\) тоді є деякі\(x\in \mathbb{Z}\) такі, що\(\overline{c} \overline{x} = \overline{1}\text{.}\)
Зробіть висновок, що якщо\(\overline{a} \cdot\overline{c} = \overline{b}\cdot\overline{c}\) в\(\mathbb{Z}_m\) цьому\(\overline{a} = \overline{b}\text{.}\)
Нехай\(p\in \mathbb{N}\) просте і\(\overline{a},\overline{b},\overline{c}\in \mathbb{Z}_p\) таке, що\(\overline{c}\ne \overline{0}\text{.}\) тоді
- є\(\overline{x}\in \mathbb{Z}_p\) такі, що\(\overline{c}\cdot \overline{x} = \overline{1}\text{;}\) і,
- якщо\(\overline{a} \cdot\overline{c} = \overline{b}\cdot\overline{c}\text{,}\)\(\overline{a} = \overline{b}\text{.}\)