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

Last updated
Save as PDF

Page ID: 64108

$ \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}}$

Модульна арифметика використовує лише фіксовану кількість можливих результатів у всіх своїх обчисленнях. Наприклад, на циферблаті годинника всього 12 годин. Якщо час зараз 7 годин, 20 годин пізніше буде 3 години; і ми не говоримо 27 годин! Цей приклад пояснює, чому модульну арифметику деякі називають арифметикою годинника.

Приклад$\PageIndex{1}\label{eg:modarith-01}$

Припустімо, що поточний час - 14:00. Напишіть це як 14:00. Через шістдесят п'ять годин, це буде 79:00. Так як\[79 = 24\cdot3+7, \nonumber\] це буде 7:00 або 7 ранку.

практичні вправи$\PageIndex{1}\label{he:modarith-01}$

Позначте неділю, понеділок, вівторок,..., суботу як День 0, 1, 2,..., 6. Якщо сьогодні понеділок, то це День 1. Який день тижня буде через два роки? Припустимо, що в році 365 днів.

У прикладі годин ми по суті розглядаємо 27 годин так само, як і 3 години. Вони ключовими є, нас цікавить лише залишок, коли значення ділиться на 12.

Визначення: конгруентний по модулю

$n\geq2$Дозволяти бути фіксованим цілим числом. Ми говоримо, що два цілі числа$m_1$ і$m_2$ є конгруентними по модулю, позначається\[m_1 \equiv m_2 \pmod{n} \nonumber\] якщо і тільки якщо$n\mid (m_1-m_2)$. Ціле число$n$ називається модулем конгруентності.

Яке відношення має це поняття конгруентності до залишків? Наступний результат описує їх з'єднання.

Теорема$\PageIndex{1}\label{thm:samer}$

$n\geq2$Дозволяти бути фіксованим цілим числом. Для будь-яких двох цілих чисел$m_1$ і$m_2$,\[m_1\equiv m_2 \mbox{ (mod~$n$)} \quad\Leftrightarrow\quad m_1\bmod n = m_2\bmod n. \nonumber\]

Зауваження

Не плутайте два позначення. Позначення «(мод$n$)» після$m_1\equiv m_2$ вказує на співвідношення конгруентності, при якому «мод$n$» укладені парою дужок, а позначення ставляться в кінці конгруентності. На відміну від цього, «мод» між$m_1$ і$n$, без дужок, є двійковою операцією, яка дає залишок при$m_1$ діленні на$n$.

Доказ

($\Rightarrow$) Припустимо$m_1\equiv m_2$ (мод$n$). Визначення конгруентності має на увазі, що ми маємо$n\mid(m_1-m_2)$. Отже,\[m_1-m_2 = nq \nonumber\] для деякого цілого числа$q$. Нехай$m_1=nq_1+r_1$ і$m_2=nq_2+r_2$ для деяких цілих чисел$q_1, q_2, r_1, r_2$, такі, що$0\leq r_1,r_2<n$. Тоді\[nq = m_1-m_2 = n(q_1-q_2)+r_1-r_2. \nonumber\] з тих пір$r_1-r_2=n(q-q_1+q_2)$, ми робимо висновок, що$n\mid r_1-r_2$. Однак це$0\leq r_1,r_2<n$ означає$|r_1-r_2|<n$. Тому ми повинні мати$r_1-r_2=0$, або$r_1=r_2$. Звідси випливає, що$m_1\bmod n = m_2\bmod n$.

($\Leftarrow$) Припустимо$m_1\bmod n = m_2\bmod n$. Відповідно до Алгоритму поділу, залишок у цілочисельному діленні є унікальним. Таким чином,$m_1=nq_1+r$ і$m_2=nq_2+r$ для деяких цілих чисел$q_1, q_2, r$ такі, що$0\leq r<n$. Тоді\[m_1-m_2 = (nq_1+r)-(nq_2+r) = n(q_1-q_2). \nonumber\] Тому,$n\mid(m_1-m_2)$.

Слідство$\PageIndex{2}\label{cor:mod0div}$

$n\geq2$Дозволяти бути фіксованим цілим числом. Тоді\[a\equiv0 \pmod{n} \quad\Leftrightarrow\quad n\mid a. \nonumber\]

Теорема 5.7.1 говорить нам$m_1\equiv m_2$ (мод$n$) тоді і тільки тоді, коли$m_1$ і$m_2$ поділяють один і той же залишок, коли вони діляться на$n$. Задано будь-яке ціле число$m$,\[m\bmod n \in\{0,1,2,\ldots,n-1\}. \nonumber\] ми називаємо ці значення залишками по модулю. У модульній арифметиці, коли ми говоримо «зменшений по модулю», ми маємо на увазі будь-який результат, який ми отримуємо, ми ділимо його на$n$ і повідомляємо лише про найменший можливий ненегативний залишок.

Наступна теорема є фундаментальною для модульної арифметики.

Теорема$\PageIndex{3}\label{thm:modthm}$

$n\geq2$Дозволяти бути фіксованим цілим числом. Якщо$a\equiv b$ (мод$n$) і$c\equiv d$ (мод$n$), то\[\begin{array}{rcll} a+c &\equiv& b+d & \pmod{n}, \\ ac &\equiv& bd & \pmod{n}. \end{array} \nonumber\]

Доказ: Припустимо$a\equiv b$ (мод$n$) і$c\equiv d$ (мод$n$). Потім$n\mid (a-b)$ і$n\mid(c-d)$. Ми можемо написати\[a-b = ns, \qquad\mbox{and}\qquad c-d = nt \nonumber\] для деяких цілих чисел$s$ і$t$. Отже,\[(a+c)-(b+d) = (a-b)+(c-d) = ns+nt = n(s+t), \nonumber\] де$s+t$ - ціле число. Це доводить, що$a+c\equiv b+d$ (мод$n$). У нас також$bt+sd+nst$ є\[ac-bd = (b+ns)(d+nt)-bd = bnt+nsd+n^2st = n(bt+sd+nst), \nonumber\] де ціле число. Таким чином$n\mid (ac-bd)$, що означає$ac\equiv bd$ (мод$n$).

Через теорему 5.7.3, ми можемо додати або помножити ціле число в обидві сторони конгруентності, не змінюючи конгруенції.

Приклад$\PageIndex{2}\label{eg:modarith-02}$

Ми можемо використовувати віднімання для зменшення 2370 по модулю 11. Будь-яке кратне 11 є конгруентним до 0 по модулю 11. Таким чином, ми маємо, наприклад,\[2370\equiv 2370 \pmod{11}, \qquad\mbox{and}\qquad 0\equiv-2200 \pmod{11}. \nonumber\] застосовуючи теорему 5.7.3, ми отримуємо\[2370 \equiv 2370-2200 = 170 \pmod{11}. \nonumber\] Що це означає: ми можемо продовжувати віднімати відповідні кратні$n$ від,$m$ поки відповідь не буде між 0 і$n-1$, включно. Не має значення, який кратний 11 ви використовуєте. Справа в тому, виберіть той, який ви можете придумати швидко, і продовжуйте повторювати процес. Продовжуючи в цьому моді, ми знаходимо\[170 \equiv 170-110 = 60 \pmod{11}. \nonumber\] Оскільки$60-55=5$, ми визначаємо, що$2370\equiv5$ (мод 11).

практичні вправи$\PageIndex{2}\label{he:modarith-02}$

Зменшити 12457 до найменшого ненегативного залишку по модулю 17.

Приклад$\PageIndex{3}\label{eg:modarith-03}$

Аналогічним чином, якщо$m$ негативний, ми можемо продовжувати додавати кратні$n$ до нього, поки відповідь не буде позитивною. Наприклад,\[-278 \equiv -278+300 = 52 \pmod{11}. \nonumber\] очевидно, що$52\equiv52-44=8$ (мод 11). Таким чином,$-278\equiv8$ (мод 11).

практичні вправи$\PageIndex{3}\label{he:modarith-03}$

Оцінити$-3275\bmod11$. Це те ж саме, що зменшення$-3275$ до найменшого ненегативного залишку по модулю 11.

У складному обчисленні зменшуйте результат від кожного проміжного кроку, перш ніж продовжувати наступний крок. Це значно спростить обчислення. Щоб ще більше прискорити обчислення, ми можемо використовувати негативні значення на проміжному кроці. Тим не менш, остаточна відповідь повинна бути між 0 і$n-1$.

Приклад$\PageIndex{4}\label{eg:modarith-04}$

Зменшити по$37^2\cdot41-53\cdot2$ модулю 7.

Рішення: Зверніть увагу, що\[\begin{array}{lclcr} 37 &\equiv& 37-35 &=& 2 \pmod{7}, \\ 41 &\equiv& 41-42 &=& -1 \pmod{7}, \\ 53 &\equiv& 53-49 &=& 4 \pmod{7}. \end{array} \nonumber\] Тому\[37^2\cdot41-53\cdot2 \equiv 2^2\cdot(-1)-4\cdot2 = -12 \pmod{7}. \nonumber\] ми визначаємо, що$37^2\cdot41-53\cdot2 \equiv 2$ (мод 7).

практичні вправи$\PageIndex{4}\label{he:modarith-04}$

Оцініть$56^3\cdot22\cdot17-35\cdot481$ (мод 9).

Нудні обчислення можуть стати досить простими при модульній арифметиці.

Приклад$\PageIndex{5}\label{eg:modarith-05}$

Показати, що якщо ціле число$n$ не ділиться на 3,$n^2-1$ то завжди ділиться на 3. Аналогічно, показати, що якщо ціле число$n$ не ділиться на 3, то$n^2-1\equiv0$ (мод 3).

Рішення 1

$n$Дозволяти ціле число не ділиться на 3, то або$n\equiv1$ (мод 3), або$n\equiv2$ (мод 3).

Випадок 1. Якщо$n\equiv1$ (мод 3), то\[n^2-1 \equiv 1^2-1 = 0 \pmod{3}. \nonumber\]

Випадок 2. Якщо$n\equiv2$ (мод 3), то\[n^2-1 \equiv 2^2-1 = 3 \equiv 0 \pmod{3}. \nonumber\]

В обох випадках ми виявили,$n^2-1$ що ділиться на 3.

Рішення 2: $n$Дозволяти ціле число не ділиться на 3, то або$n\equiv1$ (мод 3), або$n\equiv2$ (мод 3). Це еквівалентно висловлюванню$n\equiv\pm1$ (мод 3). Потім\[n^2-1 \equiv (\pm1)^2-1 = 1-1 = 0 \pmod{3}, \nonumber\] який$n^2-1$ засіб ділиться на 3.

практичні вправи$\PageIndex{5}\label{he:modarith-05}$

Використовуйте модульну арифметику, щоб показати, що$5\mid(n^5-n)$ для будь-якого цілого числа$n$.

практичні вправи$\PageIndex{6}$

Використовуйте модульну арифметику, щоб показати,$n(n+1)(2n+1)$ що ділиться на 6 для будь-якого цілого числа$n$.

Підвищення цілого числа до великої потужності створює серйозну проблему. Ми не можемо просто підняти ціле число до великої потужності, тому що результат може бути настільки великим, що калькулятор або комп'ютер повинен перетворити його в десяткове значення і почати використовувати наукові позначення для його обробки. Отже, відповідь не буде точною.

Кращим рішенням є зменшення проміжних результатів по модулю$n$ після кожного множення. Це дасть точний результат, але закінчити доведеться довго, якщо потужність величезна. На щастя, існує набагато швидший спосіб виконати зведення в ступінь, який використовує меншу кількість множень.

Приклад$\PageIndex{6}\label{eg:modarith-06}$

Оцініть$5^{29}$ (мод 11).

Рішення

Спочатку напишіть показник 29 як суму ступенів 2. Ми можемо це зробити за допомогою інспекції. Почніть з найвищої потужності 2, яка менше або дорівнює 29, а потім працюйте з тим, що залишилося в сумі:\[29 = 16+13 = 16+8+5 = 16+8+4+1. \nonumber\] Ми по суті виражаємо 29 в базі 2. Тепер ми можемо написати

\[5^{29} = 5^{16+8+4+1} = 5^{16}\cdot5^8\cdot5^4\cdot5. \nonumber\]

Ці ступені 5 можна отримати за допомогою багаторазового квадратизації:

\[\begin{aligned} 5^1 &=& 5, \\ 5^2 &=& 5^2, \\ 5^4 &=& (5^2)^2, \\ 5^8 &=& (5^4)^2, \\ 5^{16} &=& (5^8)^2, \\ \vdots\hfil && \hfil\vdots \end{aligned}\label{eg:repsq}\]

Ітерація проста: кожна нова потужність виходить шляхом зведення в квадрат попередньої потужності. Оскільки ми робимо модульну арифметику, ми хочемо зменшити кожен проміжний результат по модулю 11: Звідси\[ \begin{array}{lclcrcrr@{\quad\pmod{11}}} 5 &= & 5 & & & & & \text{(mod 11)} \\ 5^2 &= & 25 &\equiv& 3 & & & \text{(mod 11)} \\ 5^4 &\equiv& 3^2 &= & 9 &=& -2 & \text{(mod 11)} \\ 5^8 &\equiv& 9^2 &\equiv&(-2)^2 &=& 4 & \text{(mod 11)} \\ 5^{16} &\equiv& 4^2 &= & 16&\equiv& 5 & \text{(mod 11)} \end{array} \nonumber\] випливає, що\[5^{29} = 5^{16}\cdot5^8\cdot5^4\cdot5 \equiv 5\cdot4\cdot(-2)\cdot5 \pmod{11}. \nonumber\] Після спрощення ми знаходимо$5^{29}\equiv9$ (мод 11).

практичні вправи$\PageIndex{7}\label{he:modarith-06}$

Використовуйте повторне квадратування, щоб знайти$7^{45}$ (мод 11).

практичні вправи$\PageIndex{8}\label{he:modarith-07}$

Використовуйте повторне квадратування для оцінки$9^{58}$ (мод 23).

У модульній арифметиці ми в основному працюємо тільки з рештами. Множина цілих чисел$\{0,1,2,\ldots,n-1\}$ називається множиною цілих чисел по модулю, і позначається$\mathbb{Z}_n$ (вимовляється як Z мод$n$). Крім того, ми визначаємо дві нові арифметичні операції на$\mathbb{Z}_n$. Вони називаються «додавання» та «множення», оскільки вони працюють як звичайне додавання та множення, за винятком того, що ми повинні застосувати операцію mod до результатів. Щоб відрізнити їх від звичайного складання і множення, позначаємо їх на$\oplus$ і$\odot$, і називаються відповідно «круженим плюсом» і «обведеною точкою». Формально

\[a\oplus b = (a+b) \bmod n, \qquad\mbox{and}\qquad a\odot b = (a\cdot b)\bmod n. \nonumber\]

Таблиці додавання і множення для$\mathbb{Z}_6$ наведені нижче.

\[\begin{array}{|c||*{6}{c|}}\hline\oplus & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{6}{c|}}\hline\odot & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ \hline 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ \hline 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ \hline 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \nonumber\]

Порівняйте їх з таблицями для$\mathbb{Z}_7$.

\[\begin{array}{|c||*{7}{c|}}\hline\oplus & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 \\ \hline 6 & 6 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{7}{c|}} \hline\odot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\ \hline 3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\ \hline 4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\ \hline 5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ \hline 6 & 0 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \nonumber\]

В обох таблицях додавання всі можливі значення відображаються в кожному рядку і кожному стовпці. Те ж саме справедливо і в ненульових рядках і ненульових стовпцях у таблиці множення для$\mathbb{Z}_7$. Однак деякі рядки в таблиці множення для$\mathbb{Z}_6$ не містять всіх цілих чисел в$\mathbb{Z}_6$. Це говорить про те, що алгебраїчні властивості$\mathbb{Z}_n$ залежать від величини$n$.

Насправді, всякий раз, коли$n$ є простим, таблиці додавання та множення$\mathbb{Z}_n$ поводяться як ті, в$\mathbb{Z}_7$. Можна показати, що коли$n$ є простим,$\mathbb{Z}_n$ має такі властивості.

Обидва$\oplus$ і$\odot$ є комутативними, що означає\[a\oplus b = b\oplus a \qquad\mbox{and}\qquad a\odot b = b\odot a \nonumber\] для всіх$a,b\in\mathbb{Z}_n$.
Обидва$\oplus$ і$\odot$ асоціативні, що означає, що\[(a\oplus b)\oplus c = a\oplus(b\oplus c) \qquad\mbox{and}\qquad (a\odot b)\odot c = a\odot(b\odot c) \nonumber\] для всіх$a,b,c\in\mathbb{Z}_n$.
Операції$\oplus$ і$\odot$ задовольняють дистрибутивним законам\[a\odot(b\oplus c) = (a\odot b) \oplus (a\odot c) \qquad\mbox{and}\qquad (b\oplus c)\odot a = (b\odot a) \oplus (c\odot a) \nonumber\] для всіх$a,b,c\in\mathbb{Z}_n$.
Ціле число 0 - це адитивна ідентичність, що означає, що$a\oplus 0 = 0\oplus a = a$ для всіх$a\in\mathbb{Z}_n$.
Для кожного$a\in\mathbb{Z}_n$ існує унікальне ціле число,$a'\in\mathbb{Z}_n$ таке, що$a\oplus a'=0$. Це ціле число$a'$ називається адитивним оберненим або від'ємним$a$, і позначається символом$-a$.
Ціле число 1 - мультиплікативна ідентичність, що означає, що$a\odot 1 = 1\odot a = a$ для всіх$a\in\mathbb{Z}_n$.
Для кожного цілого числа$a\in\mathbb{Z}_n^*$ (отже,$a\neq0$) існує унікальне ненульове ціле число$a'\in\mathbb{Z}_n$ таке, що$a\odot a'=1$. Це ціле число$a'$ називається мультиплікативним оберненим або зворотним$a$, і позначається символом$a^{-1}$.

Приклад$\PageIndex{7}\label{eg:modarith-07}$

З наведених вище таблиць тільки 1 і 5 мають мультиплікативні інверси в$\mathbb{Z}_6$. Насправді,\[1\cdot1 = 1 \qquad\mbox{and}\qquad 5\cdot5 = 1 \qquad\mbox{in $\mathbb{Z}_6$} \nonumber\] мають на увазі$1^{-1}=1$, що, і$5^{-1}=5$ в$\mathbb{Z}_6$. З іншого боку, кожне ненульове ціле число в$\mathbb{Z}_7$ має мультиплікативний зворотний:\[1^{-1}=1, \quad 2^{-2}=4, \quad 3^{-1}=5, \quad 4^{-1}=2, \quad 5^{-1}=3, \quad\mbox{and}\quad 6^{-1}=6. \nonumber\] Обов'язково перевірте ці зворотні.

Загалом, з огляду на будь-який набір чисел, ми можемо визначити арифметичні операції будь-яким зручним нам способом, за умови, що вони підкоряються певним правилам. При цьому утворюється алгебраїчна структура. Наприклад, викликаємо набір елементів$S$ з двома двійковими операціями, позначеними$\oplus$ і полем, і$\odot$ пишемо$\langle S,\oplus,\odot\rangle$ або$(S,\oplus,\odot)$, якщо воно задовольняє всім семи властивостям, перерахованим вище. Обидва$\langle\mathbb{R},+,\cdot\,\rangle$ і$\langle\mathbb{Q},+,\cdot\,\rangle$ є полями, але не$\langle\mathbb{Z},+,\cdot\,\rangle$ є, тому що мультиплікативний зворотний$a$ не існує, якщо$a\neq\pm1$.

Теорема$\PageIndex{4}$

Алгебраїчна структура$\langle\mathbb{Z}_n,\oplus,\odot\rangle$ є полем тоді і тільки тоді, коли$n$ є простим.

Доказ: Перевірка більшості властивостей досить проста, за винятком існування мультиплікативного зворотного, що ми тут доведемо. Оскільки$n$ є простим, будь-який$a\in\mathbb{Z}^*$ повинен бути відносно простим$n$. Отже,\[as+nt = 1 \nonumber\] для деяких цілих чисел$s$ і$t$. За модулем$n$ ми знаходимо$nt=0$, отже,$as+nt=1$ стає\[as = 1. \nonumber\] Тому$a^{-1} \equiv s$ (мод$n$).

Теорема говорить нам, що якщо$n$ просте,$\mathbb{Z}_n$ то поле, отже, кожне ненульове ціле число має мультиплікативний обернений.

Приклад$\PageIndex{8}\label{eg:modarith-08}$

Визначте$7^{-1}$ (мод 29).

Рішення: Ми хочемо знайти$a'$ таке число, що$7a'\equiv1$ (мод 29). Зауважте, що$\gcd(7,29)=1$. Використовуючи розширений евклідовий алгоритм, знаходимо\[7(-4)+29\cdot1 = 1. \nonumber\]$29\cdot1\equiv0$ Since (мод 29), після зменшення по модулю 29, ми знаходимо\[7(-4) \equiv 1 \pmod{29}. \nonumber\] Це означає, що$7^{-1}\equiv-4\equiv 25$ (мод 29).

Коли$n$ є складовим,$\mathbb{Z}_n$ це не поле. Тоді не кожне ненульове ціле число в ньому має мультиплікативний обернений. Звичайно, деякі спеціальні ненульові цілі числа все ще можуть мати мультиплікативні зворотні.

практичні вправи$\PageIndex{9}\label{he:modarith-08}$

Визначте$8^{-1}$ (мод 45).

Приклад$\PageIndex{9}\label{eg:modarith-09}$

Вирішити рівняння$7x-3=5$ над$\mathbb{Z}_{29}$.

Рішення: Від$7x-3=5$, знаходимо$7x=8$. Нагадаємо, що це рівняння насправді означає\[7x \equiv 8 \pmod{29}. \nonumber\] Відповідь ні$x=\frac{8}{7}$, тому що містить$\mathbb{Z}_{29}$ лише цілі числа як його елементи. Це те, що ми повинні зробити:$7^{-1}$ множити на обидві сторони конгруентності:\[7^{-1}\cdot 7x \equiv 7^{-1}\cdot8 \pmod{29}. \nonumber\] Оскільки$7^{-1}\cdot7\equiv1$ (мод 29), ми тепер маємо\[x\equiv 7^{-1}\cdot8 \pmod{29}. \nonumber\] У певному сенсі ми використовуємо мультиплікативний зворотний для імітації ділення. В даному випадку$7^{-1}\equiv7$ (мод 29). Звідси,$x\equiv7\cdot8\equiv26$ (мод 29).

практичні вправи$\PageIndex{10}\label{he:modarith-09}$

Вирішити рівняння$8x+23=12$ над$\mathbb{Z}_{45}$.

Приклад$\PageIndex{10}\label{eg:modarith-10}$

Поясніть, чому$3^{-1}$ не існує в$\mathbb{Z}_{24}$.

Рішення: Припустимо,$3^{-1}$ існує в$\mathbb{Z}_{24}$, скажімо,$3^{-1}\equiv z$ (мод 24). Це означає$3z\equiv1$ (мод 24). Отже,\[3z = 24q+1 \nonumber\] для деякого цілого числа$q$. Це, в свою чергу, означає те,\[1 = 3z-24q = 3(z-8q), \nonumber\] що явно неможливо, оскільки$z-8q$ є цілим числом. Це протиріччя показує, що$3^{-1}$ не існує в$\mathbb{Z}_{24}$.

Обидва$\mathbb{R}$ і$\mathbb{Q}$ є нескінченними полями, в той час як$\mathbb{Z}_n$ є кінцевим полем$n$, коли є простим. Наступний результат - воістину дивовижний, тому що він проголошує, що кількість елементів у будь-якому скінченному полі (один з скінченно багатьма елементами) має бути силою певного простого. На жаль, ми не можемо довести це тут, тому що це виходить за рамки цього курсу.

Теорема$\PageIndex{5}$

Існує скінченне поле$n$ елементів тоді і тільки тоді,$n$ коли є мірою простого.

Модульна арифметика по модулю$n$ використовує операцію моду, щоб зменшити відповіді всіх обчислень в межах 0 через$n-1$.
Замість того, щоб чекати, поки ми отримаємо остаточну відповідь$n$, перш ніж зменшити її по модулю, легше зменшити кожен безпосередній результат по модулю,$n$ перш ніж перейти до наступного кроку обчислення.
Ми можемо використовувати від'ємні цілі числа в проміжних кроках.
Множина цілих чисел$\{0,1,2,\ldots,n-1\}$, разом з модульною арифметикою по модулю$n$, позначається як$\mathbb{Z}_n$.
Для$a\cdot a'\equiv1$ (мод$n$), ми говоримо,$a'$ що мультиплікативний зворотний$a$, і позначимо його$a^{-1}$.
Для деяких$a\in\mathbb{Z}_n$ мультиплікативного зворотного$a^{-1}$ може не існувати. Якщо він існує, ми можемо використовувати його для імітації поділу.

Вправа$\PageIndex{1}\label{ex:modarith-01}$

Побудувати таблиці додавання і множення для$\mathbb{Z}_8$. Які ненульові елементи мають мультиплікативні зворотні (зворотні)? Які їх мультиплікативні інверси?

Вправа$\PageIndex{2}\label{ex:modarith-02}$

Повторіть останню проблему с$\mathbb{Z}_9$.

Вправа$\PageIndex{3}\label{ex:modarith-03}$

Знайти суму і добуток 1053 і 1761 в$\mathbb{Z}_{17}$.

Вправа$\PageIndex{4}\label{ex:modarith-04}$

Деякі результати, які ми отримали раніше, можна легко довести за допомогою модульної арифметики. Наприклад, показати, що якщо ціле число$n$ не ділиться на 3, то$n\equiv\pm1$ (мод 3). Що можна сказати про$n^2$ (мод 3)? Тому яку форму потрібно$n^2$ приймати?

Вправа$\PageIndex{5}\label{ex:modarith-05}$

Показати, що жодне ціле число форми$m^2+1$ не кратне 7.

Підказка: Які можливі значення$m$ (мод 7)? Порівняйте це з останньою проблемою.

Вправа$\PageIndex{6}\label{ex:modarith-06}$

Які можливі значення$m$ (мод 13) такі,$m^2+1$ що кратні 13?

Підказка: Обчислити$m^2+1$ (мод 13) для кожного значення$m$.

Вправа$\PageIndex{7}\label{ex:modarith-07}$

Знайти значення$4^{45}$ в$\mathbb{Z}_{11}$

використовуючи той факт, що$45=3\cdot3\cdot5$
за допомогою повторного квадратування

Вправа$\PageIndex{8}\label{ex:modarith-08}$

Використовуйте повторне квадратування для оцінки$5^{23}$ (мод 11).

Вправа$\PageIndex{9}\label{ex:modarith-09}$

Розв'яжіть ці рівняння

$2x+ 5=10$над$\mathbb{Z}_{13}$
$37x+28=25$над$\mathbb{Z}_{57}$
$12-24x=15$над$\mathbb{Z}_{35}$

Вправа$\PageIndex{10}\label{ex:modarith-10}$

$q$Дозволяти$p$ і бути непарними простими числами.

Показати, що$p$ приймає форму або$6k+1$ або$6k+5$.

Підказка: По-перше, поясніть, чому дивне обмежує$p$ форму$6k+1$$6k+3$, і$6k+5$. Далі аргументуйте чому$p\neq 6k+3$.

Що може$p$ бути конгруентним, по модулю 24?
Покажіть, що якщо$p\geq q\geq5$, то$24\mid (p^2-q^2)$.

Підказка: Які можливі значення$p^2$ і по$q^2$ модулю 24?

Вправа$\PageIndex{11}\label{ex:modarith-11}$

Використовуйте модульну арифметику, щоб довести,$n$ що якщо ціле число не ділиться на 5,$n^4-1$ то ділиться на 5.

Вправа$\PageIndex{12}\label{ex:modarith-12}$

Використовуйте модульну арифметику, щоб довести, що$8\mid(5^{2n}+7)$ для будь-якого цілого числа$n\geq0$.

Вправа$\PageIndex{13}\label{ex:modarith-13}$

Використовуйте модульну арифметику, щоб довести, що$3\mid(2^{2n}-1)$ для будь-якого цілого числа$n\geq0$.

Вправа$\PageIndex{14}\label{ex:modarith-14}$

Використовуйте модульну арифметику, щоб довести, що$5\mid(3^{3n+1}+2^{n+1})$ для будь-якого цілого числа$n\geq0$.