5.2: Алгоритм поділу

Last updated
Save as PDF

Page ID: 64112

\( \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}}\)

Коли ми ділимо натуральне число (дивіденд) на інше натуральне число (дільник), отримуємо частку. Множимо частку на дільник, і віднімаємо добуток з дивіденду, щоб отримати залишок. Такий поділ дає два результати: частка і залишок.

Ось як ми зазвичай ділимо 23 на 4:

\ [\ вимагають {вкласти}
\ почати {масив} {rll}
5 &&\\ [-3pt]
4\ вкласти {longdiv} {23}\ керн-.2ex\\ [-3pt]
\ підкреслення {\ фантом {0} 20} &&\\ [-3pt]
\ фантом {00} 3
\ кінець {масив}\ nonumber\]

В цілому поділ\(b\div a\) набуває вигляду

\ [\ вимагають {вкласти}
\ почати {масив} {rll}
q &&\\ [-3pt]
a\ вкласти {longdiv} {\ фантом {0} б}\ керн-.2ex\ [-3pt]
\ підкреслення {\ фантом {0} q} &\\ [-3pt]
\ фантом {00} r
\ кінець {масив}\ nonumber\

так що\(r=b-aq\), або еквівалентно,\(b=aq+r\). Звичайно, обидва\(q\) і\(r\) є цілими числами. Тим не менш, наступні «поділи»

\ [{\ вимагають {вкладіть}\ почати {масив} {rll}
4 &&\\ [-3pt]
4\ вкладіть {longdiv} {23}\ керн-.2ex\\ [-3pt]\ підкреслення {\ фантом {0} 16} &\
\ [-3pt]\ фантом {00} 7\ кінець {масив}} {\ вимагають {вкладіть} {
\\ [-3pt]\ фантом {00} 7
\ кінець {масив}} {\ вимагають {вкладіть}
\\ [-3pt]\ масив} {rll}
2 &&\\ [-3pt]
4\ вкласти {longdiv} {23}\ керн-.2ex\\ [-3pt]
\ підкреслення {\ фантом {0} 8} &\\ [-3pt]
\ фантом {00} 15
\ кінець {масив}} {\ вимагають {вкласти}
\ почати {масив} {rll}
6 &\\ [-3pt]
4\ вкласти {longdiv} {23}\ керн-.2ex\\ [-3pt]
\ підкреслення {\ фантом {0} 24} &&\\ [-3pt]
\ фантом {00} -1
\ end {масив} {\ вимагати {вкласти}
\ почати {масив} {rll}
7 &\\\ [-3pt]
4\ inclose {longdiv} {23}\ керн-.2ex\\ [-3pt]
\ підкреслення {\ фантом {0} 28} &&\\ [-3pt]
\ фантом {00} -5
\ end {масив}}\ nonumber\]

також задовольняємо вимогу\(b=aq+r\), але це не те, що ми зазвичай робимо. Це означає, що\(b=aq+r\) одного недостатньо, щоб визначити, що частка і залишок є. Нам потрібно більш жорстке визначення.

Теорема\(\PageIndex{1}\label{thm:divalgo}\)

Дано будь-які цілі числа\(a\) і\(b\), де\(a>0\), існують цілі числа\(q\) і\(r\) такі, що\[b = aq + r, \nonumber\] де\(0\leq r< a\). Крім того,\(q\) і\(r\) однозначно визначаються\(a\) і\(b\).

Цілі числа\(b\),\(a\)\(q\), і\(r\) називаються дивідендом, дільником , часткою та залишком відповідно. Зверніть увагу, що\(b\) є кратним\(a\) якщо і тільки якщо\(r=0\).

Алгоритм поділу описує те, що відбувається при поділі довгих. Власне кажучи, це не алгоритм. Алгоритм описує процедуру вирішення проблеми. Теорема не говорить нам, як знайти частку і залишок. Деякі математики вважають за краще називати його теоремою ділення. Тут ми слідуємо традиції і називаємо її алгоритмом поділу.

Зауваження

Це контур доказу:

Опишіть, як знайти цілі числа\(q\) і\(r\) такі що\(b=aq+r\).
Покажіть, що наш вибір\(r\) задовольняє\(0\leq r< a\).
Встановити унікальність\(q\) і\(r\).

Щодо останньої частини доказу: показати, що певне число однозначно визначено, типовий підхід\(x\) полягає в тому, щоб припустити, що\(x'\) це інший вибір, який задовольняє даній умові, і показати, що ми повинні мати\(x=x'\).

Доказ

Ми спочатку покажемо існування\(q\) і\(r\). Нехай\[S = \{ b-ax \mid x\in\mathbb{Z} \mbox{ and } b-ax\geq 0 \}. \nonumber\] Ясно,\(S\) це набір невід'ємних цілих чисел. Щоб мати можливість застосувати принцип добре впорядкування, нам потрібно показати, що\(S\) це непорожньо. Ось конструктивний доказ.

Випадок 1. Якщо\(b\geq 0\), ми можемо встановити\(x=0\). Потім\(b-ax=b\geq0\).
Випадок 2. Якщо\(b < 0\), встановити\(x=b\).
З тих пір\(a\geq1\), у нас є\(1-a\leq0\). Тоді\[b-ax = b-ab = b(1-a) \geq 0. \nonumber\]

Оскільки\(S\) непорожній, то випливає з принципу упорядкування, який\(S\) має найменший елемент. Називайте це\(r\). З визначення\(S\), існує деяке ціле число\(q\) таке, що\(b − aq = r\).

Крок 2: Покажіть, що r задовольняє критерію\(0 \leq r < a\).

Отже\(t \in S\). Тепер\(t = r − a < r\) припускає, що ми знайшли ще один елемент\(S\), в якому ще менше, ніж\(r\). Це суперечить мінімалістичності\(r\). Тому\(r < a\).

Нарешті, ми повинні встановити унікальність обох\(q\) і\(r\). \(r'\)Дозволяти\(q'\) і бути цілими числами такі, що\[b=aq'+r', \qquad 0\leq r'< a. \nonumber\] з\(aq+r = b = aq'+r'\), ми знаходимо\(a(q-q') = r'-r\). Отже,\[a\,|q-q'| = |r'-r|. \nonumber\] оскільки\(|r'-r|\) є цілим числом\(|r'-r|\neq0\), якщо, ми б мали\(a\leq |r'-r|\). З\(0\leq r,r'<a\), ми виводимо те\(|r'-r|<a\), що явно суперечить нашому спостереженню, що\(a\leq|r'-r|\). Отже,\(|r'-r|=0\). Потім\(r'=r\). Звідси випливає, що\(q'=q\). Таким чином, частка\(q\) і залишок\(r\) унікальні.

Далі ми показуємо, що\(0\leq r<a\). Визначення\(S\) говорить нам відразу\(r\geq0\), що, тому нам потрібно лише показати це\(r<a\). Припустимо, навпаки,\(r\geq a\). Потім\(r = a+t\) для деякого цілого числа\(t\geq 0\). Тепер\(b-aq = r = a + t\) має на увазі, що\[0 \leq t = b-aq-a = b-a(q+1). \nonumber\] Так\(t\in S\). Тепер\(t = r-a < r\) припускає, що ми знайшли ще один елемент\(S\), в якому ще менше, ніж\(r\). Це суперечить мінімалістичності\(r\). Тому\(r < a\).

Ви не повинні мати жодних проблем з діленням натурального числа на інше натуральне число. Це вид довгого поділу, який ми зазвичай виконуємо. Складніше ділити від'ємне ціле число на натуральне. Коли\(b\) негативний, коефіцієнт також\(q\) буде негативним, але залишок\(r\) повинен бути невід'ємним. У певному сенсі\(r\) є вирішальним фактором: вибираємо\(q\) такий, щоб залишок\(r\) задовольняв умові\(0\leq r<a\).

Загалом, для будь-якого цілого числа\(b\) ділення\(b\) на\(a\) дає десяткове число. Якщо результат не є цілим числом, округліть його до наступного меншого цілого (див. Приклад 6.1.3). Це частка,\(q\) яку ми хочемо, а залишок\(r\) отримуємо від віднімання\(r=b-aq\). Наприклад,\[\frac{-22}{\;\;7} = -3.1428\ldots\,. \nonumber\] Округлення його вниз виробляє частка\(q=-4\), а залишок є\(r=-22-7(-4)=6\); і у нас є\(-22=7\cdot(-4)+6\).

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

Обчисліть частки\(q\) та залишки\(r\) при\(b\) діленні на\(a\):

\(b= 128\),\(a=7\)
\(b=-128\),\(a=7\)
\(b=-389\),\(a=16\)

Обов'язково переконайтеся в цьому\(b=aq+r\).

Алгоритм ділення можна узагальнити до будь-якого ненульового цілого числа\(a\).

Слідство\(\PageIndex{2}\label{cor:divalgo}\)

Задані будь-які цілі числа\(a\) і\(b\) з\(a\neq 0\), існують однозначно визначені цілі числа\(q\) і\(r\) такі\(b = aq +r\), що, де\(0\leq r < |a|\).

Доказ: Нам залишається лише розглянути випадок\(a<0\). Так як\(-a>0\), оригінальний Евклідовий алгоритм запевняє, що існують однозначно\(q'\) визначені цілі числа і\(r\) такі, що\[b = (-a)\cdot q' + r, \nonumber\] де\(0\leq r<-a=|a|\). Тому ми можемо встановити\(q=-q'\).

приклад\(\PageIndex{1}\label{eg:divalgo-01}\)

Не кожен калькулятор або комп'ютерна програма обчислює\(q\) і\(r\) те, як ми хочемо, щоб вони робили в математиці. Найбезпечніше рішення - обчислити звичайним\(|b| \div |a|\) способом, оглянути залишок, щоб побачити, чи відповідає він критерію\(0\leq r<|a|\). При необхідності відрегулюйте значення\(q\) так, щоб залишок\(r\) задовольняв вимогу\(0\leq r<|a|\). Ось кілька прикладів:\[\begin{array}{|r|r|r@{\;=\;}l|r|r|} \hline b & a & b & aq+r & q & r \\ \hline 14 & 4 & 14 & 4\cdot3+2 & 3 & 2 \\ -14 & 4 & -14 & 4\cdot(-4)+2 & -4 & 2 \\ -17 & -3 & -17 & (-3)\cdot6+1 & 6 & 1 \\ 17 & -3 & 17 & (-3)\cdot(-5)+2 & -5 & 2 \\ \hline \end{array} \nonumber\]

Коефіцієнт\(q\) може бути позитивним або негативним, а залишок завжди\(r\) невід'ємним.

Визначення

Дано цілі числа\(a\) і\(b\), з\(a\neq 0\), нехай\(q\) і\(r\) позначають унікальні цілі числа такі\(b=aq+r\), що, де\(0\leq r<|a|\). Визначте бінарні оператори\(\mathrm{ div }\) і\(\bmod\) наступним чином:

Отже,\(b ~ \mathrm{ div } ~ a\) дає частку, і\(b\bmod a\) видає залишок від цілочисельного ділення\(b\div a\). Нагадаємо, що\(b ~ \mathrm{ div } ~ a\) може бути позитивним, негативним або навіть нульовим. Але \(b\bmod a\)завжди невід'ємне ціле число менше\(|a|\).

приклад\(\PageIndex{2}\label{eg:divalgo-02}\)

З останнього прикладу ми маємо

\(14 ~ \mathrm{ div } ~ 4 = 3\), і\(14\bmod 4 = 2\).
\(-14 ~ \mathrm{ div } ~ 4 =-4\), і\(-14\bmod 4 = 2\).
\(-17 ~ \mathrm{ div } ~ -3 = 6\), і\(-17\bmod-3 = 1\).
\(17 ~ \mathrm{ div } ~ -3 =-5\), і\(17\bmod-3 = 2\).

Не забувайте перевіряти обчислення, і пам'ятайте, що позитивними бути не\(a\) потрібно.

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

Заповніть наступну таблицю:

\[\begin{array}{|r|r|r|r|} \hline b & a & b ~ \mathrm{ div } ~ a & b\bmod a \\ \hline 334 & 15 & \qquad\qquad & \qquad\qquad \\ 334 & -15 & & \\ -334 & 15 & & \\ -334 & -15 & & \\ \hline \end{array} \nonumber\]Не забувайте: завжди\(b\bmod a\) ненегативний.

приклад\(\PageIndex{3}\label{eg:divalgo-03}\)

\(n\)Дозволяти ціле число таке, що\[n ~ \mathrm{ div } ~ 6 = q, \qquad \mbox{and} \qquad n\bmod6 = 4. \nonumber\] Визначити значення\((2n+5) ~ \mathrm{ div } ~ 6\), і\((2n+5)\bmod6\).

Рішення: Наведена інформація має на увазі це\(n=6q+4\). Тоді\[2n+5 = 2(6q+4)+5 = 12q+13 = 6(2q+2)+1. \nonumber\] Тому\((2n+5) ~ \mathrm{ div } ~ 6 = 2q+2\), і\((2n+5)\bmod6 = 1\).

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

\(n\)Дозволяти ціле число таке, що\[n ~ \mathrm{ div } ~ 11 = q, \qquad\mbox{and}\qquad n\bmod11 = 5. \nonumber\] Обчислити значення\((6n-4) ~ \mathrm{ div } ~ 11\) і\((6n-4)\bmod11\).

приклад\(\PageIndex{4}\label{eg:divalgo-04}\)

Припустимо, сьогодні середа. Який день тижня - це рік відтепер?

Рішення: Позначте неділю, понеділок,..., суботу як День 0, 1,... 6 відповідно. Сьогодні День 3. Рік (якщо припустити 365 днів у році) з сьогоднішнього дня буде 368 день. Так як\[368 = 7\cdot52+4, \nonumber\] це буде День 4 тижня. Тому рік з сьогоднішнього дня буде четвер.

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

Припустимо, сьогодні п'ятниця. Який день тижня це 1000 днів з сьогоднішнього дня?

Будь-яке ціле число, поділене на 7, дасть залишок від 0 до 6 включно. \[A_i = \{ x\in\mathbb{Z} \mid x\bmod 7 = i \} \quad\mbox{ for } 0\leq i\leq 6, \nonumber\]Визначимо\[\mathbb{Z} = A_0\cup A_1\cup A_2\cup A_3\cup A_4\cup A_5\cup A_6, \nonumber\], знаходимо, де\(A_i\) множини попарно нез'єднані. Колекція множин\[\{A_0,A_1,A_2,A_3,A_4,A_5,A_6\} \nonumber\] називається розділом\(\mathbb{Z}\), тому що кожне ціле число належить до однієї і тільки однієї з цих семи підмножин. Ми також говоримо, що\(\mathbb{Z}\) це неспільний союз\(A_0,A_1,\ldots,A_6\). Цей же аргумент стосується і ділення на будь-яке ціле число\(n\geq2\).

Взагалі колекція або сімейство скінченних множин\(\{S_1,S_2,\ldots, S_n\}\) називається розділом множини,\(S\) якщо\(S\) є неспільним об'єднанням\(S_1,S_2,\ldots\,S_n\). Розділ є дуже важливим поняттям, оскільки він розділяє елементи на\(n\) класи\(S_1,S_2,\ldots,S_n\) таким чином, що кожен елемент\(S\) належить до унікального класу.\(S\) Ми знову повернемося до розділу, коли вивчимо відносини в главі 7.

Резюме та огляд

Ділення цілих чисел можна продовжити до від'ємних цілих чисел.
Задано будь-яке ціле\(b\) і будь-яке\(a\) ненульове ціле число, існують однозначно\(q\) визначені цілі числа і\(r\) такі\(b=aq+r\), що, де\(0\leq r<|a|\).
\(q\)Називаємо частку,\(r\) а залишок.
Причина, по якій ми маємо унікальний вибір,\(q\) і\(r\) є критерієм, на який ми ставимо\(r\). Він повинен задовольнити вимогу\(0\leq r<|a|\).
По суті, критерій\(0\leq r<|a|\) є єдиним найважливішим вирішальним фактором у нашому виборі\(q\) і\(r\).
Визначимо дві бінарні операції над цілими числами. \(\mathrm{ div }\)Операція дає частку, а\(\bmod\) операція видає залишок цілочисельного ділення\(b\div a\). Іншими словами\(b ~ \mathrm{ div } ~ a=q\), і\(b\bmod a=r\).

Вправи 5.2

вправа\(\PageIndex{1}\label{ex:divalgo-01}\)

Знайти\(b ~ \mathrm{ div } ~ a\) і\(b\bmod a\), де

\(a= 13\),\(b= 300\)
\(a= 11\),\(b=-120\)
\(a=-22\),\(b= 145\)

вправа\(\PageIndex{2}\label{ex:divalgo-02}\)

Знайти\(b ~ \mathrm{ div } ~ a\) і\(b\bmod a\), де

\(a= 19\),\(b= 79\)
\(a= 59\),\(b= 18\)
\(a= 16\),\(b=-823\)
\(a=-16\),\(b= 172\)
\(a=- 8\),\(b=- 67\)
\(a=-12\),\(b=-134\)

вправа\(\PageIndex{3}\label{ex:divalgo-03}\)

Доведіть, що\[b\bmod a \in\{0,1,2,\ldots,|a|-1\} \nonumber\] для будь-яких цілих чисел\(a\) і\(b\), де\(a\neq0\).

вправа\(\PageIndex{4}\label{ex:divalgo-04}\)

Доведіть, що серед будь-яких трьох послідовних цілих чисел, один з них кратний 3.

Підказка: Нехай три послідовних цілих числа\(n\) be\(n+1\), і\(n+2\). Які можливі значення\(n\bmod3\)? У що це означає, згідно алгоритму поділу? У кожному конкретному випадку\(n\), що б\(n+1\), і\(n+2\) виглядати?

вправа\(\PageIndex{5}\label{ex:divalgo-05}\)

Довести,\(n^3-n\) що завжди кратне 3 для будь-якого цілого числа\(n\) по

Аналіз у кожному конкретному випадку.
Факторинг\(n^3-n\).

вправа\(\PageIndex{6}\label{ex:divalgo-06}\)

Доведіть, що\(\{n,n+4,n+8,n+12,n+16\}\) множина містить кратну 5 для будь-якого позитивного цілого числа\(n\).

вправа\(\PageIndex{7}\label{ex:divalgo-07}\)

\(n\)Дозволяти\(m\) і бути цілими числами такими, що\[m ~ \mathrm{ div } ~ 5 = s, \qquad m\bmod5=1, \qquad n ~ \mathrm{ div } ~ 5 = t, \qquad n\bmod5=3. \nonumber\] Визначити

\((m+n) ~ \mathrm{ div } ~ 5\)
\((m+n)\bmod5\)
\((mn) ~ \mathrm{ div } ~ 5\)
\((mn)\bmod5\)

вправа\(\PageIndex{8}\label{ex:divalgo-08}\)

\(n\)Дозволяти\(m\) і бути цілими числами такими, що\[m ~ \mathrm{ div } ~ 8 = s, \qquad m\bmod8=3, \qquad n ~ \mathrm{ div } ~ 8 = t, \qquad n\bmod8=6. \nonumber\] Визначити

\((m+2) ~ \mathrm{ div } ~ 8\)
\((m+2)\bmod8\)
\((3mn) ~ \mathrm{ div } ~ 8\)
\((3mn)\bmod8\)
\((5m+2n) ~ \mathrm{ div } ~ 8\)
\((5m+2n)\bmod8\)
\((3m-2n) ~ \mathrm{ div } ~ 8\)
\((3m-2n)\bmod8\)