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

Last updated
Save as PDF

Page ID: 65560

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

У цьому розділі ми розглянемо певне сімейство співвідношень еквівалентності на цілих числах і досліджуємо спосіб взаємодії арифметики з ними.

Визначення 7.76. Для кожного$n\in \mathbb{N}$, визначте,$n\mathbb{Z}$ щоб бути множиною всіх цілих чисел, які діляться на$n$. У позначеннях set-builder ми маємо\[n\mathbb{Z} := \{m \in \mathbb{Z} \mid m = nk \text{ for some } k \in \mathbb{Z}\}.\]

Наприклад,$5\mathbb{Z} = \{ \ldots,-10,-5,0,5,10,\ldots\}$ і$2\mathbb{Z}$ є множиною парних цілих чисел.

Завдання 7.77. Розглянемо набори$3 \mathbb{Z}$,$5 \mathbb{Z}$,$15 \mathbb{Z}$, і$20 \mathbb{Z}$.

Перерахуйте щонайменше п'ять елементів у кожному з перерахованих вище наборів.
Зверніть увагу, що$3 \mathbb{Z} \cap5 \mathbb{Z} = n\mathbb{Z}$ для деяких$n\in \mathbb{N}$. Що таке$n$? $15\mathbb{Z}\cap 20 \mathbb{Z}$Опишіть аналогічним чином.
Намалюйте діаграму Венна, яка ілюструє, як$5\mathbb{Z}$ множини$3\mathbb{Z}$, і$15\mathbb{Z}$ перетинаються.
Намалюйте діаграму Венна, яка ілюструє, як$15\mathbb{Z}$ множини$5\mathbb{Z}$, і$20\mathbb{Z}$ перетинаються.

Теорема 7.78. Нехай$n\in \mathbb{N}$. Якщо$a,b \in n\mathbb{Z}$, то$-a$$a+b$, і$ab$ знаходяться також в$n\mathbb{Z}$.

Визначення 7.79. Для кожного$n\in \mathbb{N}$ визначте відношення$\equiv_n$ на$\mathbb{Z}$ via$a\equiv_n b$ if$a-b \in n\mathbb{Z}$. Ми читаємо$a\equiv_n b$ як «$a$є конгруентним по$b$ модулю»$n$.

Зверніть увагу, що$a-b \in n\mathbb{Z}$ якщо і тільки якщо$n$ ділить$a-b$, що означає, що$a\equiv_n b$ якщо і тільки якщо$n$ ділить$a-b$.

Приклад 7.80. Ми зіткнулися$\equiv_5$ в задачі 7.22 і виявили, що існує п'ять різних наборів родичів. Зокрема, ми маємо\[\begin{aligned} rel(0) & = \{\ldots, -10, -5, 0, 5, 10,\ldots\}\\ rel(1) & = \{\ldots, -9, -4, 1, 6, 11,\ldots\}\\ rel(2) & = \{\ldots, -8, -3, 2, 7, 12,\ldots\}\\ rel(3) & = \{\ldots, -7, -2, 3, 8, 13,\ldots\}\\ rel(4) & = \{\ldots, -6, -1, 4, 9, 14,\ldots\}.\end{aligned}\] Зауваження, що ця колекція утворює розділ$\mathbb{Z}$. За наслідком 7.74 відношення$\equiv_5$ повинно бути співвідношенням еквівалентності.

Попередній приклад узагальнює, як очікувалося. Ви можете довести наступну теорему, довівши, що$\equiv_n$ є рефлексивним, симетричним та перехідним, або використовуючи Слідство 7.74.

Теорема 7.81. Бо$n\in \mathbb{N}$, відношення$\equiv_n$ - це відношення еквівалентності на$\mathbb{Z}$.

У нас є спеціальні позначення та термінологія для класів еквівалентності, які відповідають$\equiv_n$.

Визначення 7.82. Для$n\in \mathbb{N}$, давайте$[a]_n$ позначимо клас еквівалентності по$a$ відношенню до$\equiv_n$ (див. Визначення 7.17 і 7.44). Клас еквівалентності$[a]_n$ називається класом конгруентності (або залишку) по$a$ модулю$n$. $\equiv_n$Позначається колекція всіх класів еквівалентності, що визначається$\mathbb{Z}/n\mathbb{Z}$, що читається «по$\mathbb{Z}$ модулю$n\mathbb{Z}$».

Приклад 7.83. Давайте обчислимо$[2]_7$. Трасування назад через визначення, ми бачимо, що\[\begin{aligned} m \in [2]_7 & ⇐⇒ m \equiv_7 2\\ & ⇐⇒ m-2\in 7\mathbb{Z}\\ & ⇐⇒ m-2 = 7k \text{ for some $k\in \mathbb{Z}$}\\ & ⇐⇒ m = 7k+2 \text{ for some $k\in \mathbb{Z}$}.\end{aligned}\] Оскільки кратні$7$ є$7\mathbb{Z} = \{\ldots,-14,-7,0,7,14,\ldots\}$, ми можемо знайти,$[2]_7$ додавши$2$ до кожного елемента$7\mathbb{Z}$ отримати$[2]_7 = \{\ldots,-12,-5,2,9,16,\ldots\}$.

Завдання 7.84. Для кожного з наступних класів конгруентності знайдіть п'ять елементів у множині таким чином, щоб принаймні один був більшим,$70$ а один менше$70$.

$[4]_7$
$[-3]_7$
$[7]_7$

Проблема 7.85. Опишіть$[0]_3$$[1]_3$$[2]_3$,,$[4]_3$, і$[-2]_3$ як списки елементів, як у прикладі 7.83. Скільки різних класів конгруентності в$\mathbb{Z}/3\mathbb{Z}$? Теорема 7.43 може бути корисною.

Розглянемо використання теореми 7.42 для доведення наступної теореми.

Теорема 7.86. Для$n\in \mathbb{N}$ і$a,b\in \mathbb{Z}$,$[a]_n = [b]_n$ якщо і тільки, якщо$n$ ділить$a-b$.

Слідство 7.87. Для$n\in \mathbb{N}$ і$a\in \mathbb{Z}$,$[a]_n = [0]_n$ якщо і тільки, якщо$n$ ділить$a$.

Наступний результат дає корисну характеристику для того, коли два класи конгруентності рівні. Алгоритм поділу буде корисний при доведенні цієї теореми.

Теорема 7.88. Для$n\in \mathbb{N}$ і$a,b\in \mathbb{Z}$,$[a]_n = [b]_n$ якщо і тільки тоді$a$ і$b$ мають однаковий залишок при діленні на$n$.

При доведенні частини (а) наступної теореми скористайтеся теоремою 7.86. Для частини (b) зверніть увагу, що$a_1b_1-a_2b_2 = a_1b_1 -a_2b_1 + a_2b_1-a_2b_2$.

Теорема 7.89. Нехай$n\in \mathbb{N}$ і нехай$a_1,a_2,b_1,b_2 \in \mathbb{Z}$. Якщо$[a_1]_n = [a_2]_n$ і$[b_1]_n = [b_2]_n$, то

$[a_1+b_1]_n = [a_2+b_2]_n$, і
$[a_1\cdot b_1]_n = [a_2\cdot b_2]_n$.

Попередня теорема дозволяє визначити додавання і множення в$\mathbb{Z}/n\mathbb{Z}$.

Визначення 7.90. Нехай$n\in \mathbb{N}$. Визначено суму та добуток класів конгруентності у$\mathbb{Z}/n\mathbb{Z}$ via\[[a]_n + [b]_n:= [a+b]_n \quad \text{and} \quad [a]_n \cdot [b]_n:= [a\cdot b]_n.\]

Приклад 7.91. За визначенням 7.90,$[2]_7+[6]_7 = [2+6]_7 = [8]_7$. За теоремою 7.86$[8]_7 = [1]_7$, і так$[2]_7+[6]_7 = [1]_7$. Аналогічно,$[2]_7\cdot[6]_7 = [2\cdot6]_7 = [12]_7 = [5]_7$.

Додавання та множення для$\mathbb{Z}/n\mathbb{Z}$ має багато знайомих - і деякі не настільки знайомі - властивості. Наприклад, додавання і множення класів конгруентності бувають як асоціативними, так і комутативними. Однак це можливо$[a]_n\cdot[b]_n = [0]_n$ навіть тоді, коли$[a]_n \neq [0]_n$ і$[b]_n \neq [0]_n$.

Теорема 7.92. Якщо$n\in \mathbb{N}$, то додавання в$\mathbb{Z}/n\mathbb{Z}$ буває комутативним і асоціативним. Тобто, для всіх$[a]_n, [b]_n, [c]_n \in \mathbb{Z}/n\mathbb{Z}$, у нас є

$[a]_n + [b]_n = [b]_n + [a]_n$, і
[модульний додати доц$([a]_n + [b]_n) + [c]_n = [a]_n + ([b]_n + [c]_n)$.].

Теорема 7.93. Якщо$n\in \mathbb{N}$, то множення в$\mathbb{Z}/n\mathbb{Z}$ буває комутативним і асоціативним. Тобто, для всіх$[a]_n, [b]_n, [c]_n \in \mathbb{Z}/n\mathbb{Z}$, у нас є

$[a]_n \cdot [b]_n = [b]_n \cdot [a]_n$, і
[модульний мульт доц]$([a]_n \cdot [b]_n) \cdot [c]_n = [a]_n \cdot ([b]_n \cdot [c]_n)$.

Одним з наслідків теорем 7.92 (b) та 7.93 (b) є те, що дужки не потрібні при додаванні або множенні класів конгруентності. Наступна теорема випливає з визначення 7.90 разом з теоремами 7.92 (b) та 7.93 (b) та індукцією на$k$.

Теорема 7.94. Нехай$n\in \mathbb{N}$. Для всіх$k\in \mathbb{N}$, якщо$[a_1]_n,[a_2]_n,\ldots, [a_k]_n \in \mathbb{Z}/n\mathbb{Z}$, то

$[a_1]_n+[a_2]_n+\cdots+ [a_k]_n = [a_1 + a_2 +\cdots+ a_k]_n$, і
$[a_1]_n [a_2]_n \cdots [a_k]_n = [a_1 a_2 \cdots a_k]_n$.

Наступним результатом є окремий випадок теореми 7.94 (b).

Слідство 7.95. Нехай$n\in \mathbb{N}$. Якщо$a\in\mathbb{Z}$ і$k\in \mathbb{N}$, то$([a]_n)^k = [a^k]_n$

Приклад 7.96. Давайте обчислимо$[8^{179}]_7$. Ми бачимо, що\[\begin{aligned} _7 & = ([8]_7)^{179} & (\text{Corollary 7.95})\\ & = ([1]_7)^{179} & (\text{Theorem 7.86})\\ & = [1^{179}]_7 & (\text{Corollary 7.95})\\ & = [1]_7.\end{aligned}\]

Для частини (а) в наступній задачі використовуйте той факт, що$[6]_7 = [-1]_7$. Для частини (b) використовуйте той факт, що$[2^3]_7 = [1]_7$.

Проблема 7.97. Для кожного з наступних знайдіть число$a$ з$0\le a \le 6$ таким, щоб задана величина дорівнювала$[a]_7$.

$[6^{179}]_7$
$[2^{300}]_7$
$[2^{301} +5]_7$

Проблема 7.98. Знайти$a$ і$b$ таке, що$[a]_6\cdot[b]_6 = [0]_6$ але$[a]_6 \neq [0]_6$ і$[b]_6 \neq [0]_6$.

Теорема 7.99. Якщо$n\in \mathbb{N}$ таке, що не$n$ є простим, то існує$[a]_n, [b]_n \in \mathbb{Z}/n\mathbb{Z}$ таке, що$[a]_n\cdot[b]_n = [0]_n$ поки$[a]_n \neq [0]_n$ і$[b]_n \neq [0]_n$.

Теорема 7.100. Зверніть увагу, що не$2x = 1$ має рішення в$\mathbb{Z}$. Показати, що$[2]_7[x]_7 = [1]_7$ є рішення з$x$ в$\mathbb{Z}$. А як щодо$[14]_7[x]_7 = [1]_7$?

Теорема 7.101. Скористайтеся теоремою 7.94, наслідком 7.95 та теоремою 7.86, щоб довести наступну теорему.

Якщо$m\in \mathbb{N}$ такі, що\[m=a_k10^k + a_{k-1}10^{k-1} + \cdots + a_110 + a_0,\] де$a_k, a_{k-1}, \ldots, a_1, a_0\in \{0,1,\ldots, 9\}$ (тобто$a_k, a_{k-1}, \ldots, a_1, a_0$ цифри$m$), то\[[m]_3 = [a_k + a_{k-1} + \cdots + a_1 + a_0]_3.\]

Ви, швидше за все, розпізнаєте наступний результат. Його доказ швидко випливає з Слідство 7.87 разом з попередньою теоремою.

Теорема 7.102. Ціле число ділиться на$3$ якщо і тільки тоді, коли сума його цифр ділиться на$3$.

Давайте повернемося до теореми 7.21, яку ми спочатку довели індукцією.

Завдання 7.103. Використовуйте Слідство 7.87, щоб довести, що для всіх цілих чисел$n \ge 0$$3^{2n}-1$ ділиться на$8$. Вам потрібно буде обробляти справу за участю$n=0$ окремо.

Закриваємо цю главу цікавою проблемою.

Завдання 7.104. Доведіть або надайте контрприклад: Немає цілого числа не$n$ існує такого, що$4n+3$ є ідеальним квадратом.