Алгоритм деления

В данном занятии мы разработаем алгоритм деления как принцип, который формализует для целых чисел единственное разложение b=qa+r при условии 0\le r<|a|. Сначала доказывается существование частного и остатка, а затем их единственность. Наконец, интерпретируется смысл остатка, устанавливается связь теории с длинным алгоритмом деления как вычислительной процедурой, и предварительно рассматривается его естественная связь с модульной арифметикой и вычислительными приложениями.

Цели обучения

По завершении данного занятия студент сможет:

1. Идентифицировать основные понятия и роли целочисленного деления (делимое, делитель, частное, остаток) и понятие делимости как точного случая.
2. Объяснить формулировку алгоритма/теоремы евклидова деления, включая условия, определяющие остаток (0\le r<|a|), и их назначение для устранения неоднозначностей.
3. Применять евклидово разложение b=qa+r для определения q и r в конкретных примерах, проверяя ограничение на остаток.
4. Анализировать рассмотрение случаев в зависимости от знака делимого и делителя, обосновывая, почему евклидова конвенция сохраняет неотрицательный остаток.
5. Выполнять длинный алгоритм деления как механическую процедуру, основанную на позиционной записи чисел, для получения q и r.

СОДЕРЖАНИЕ:
Деление и делимость
Теорема о евклидовом делении
Доказательство евклидова деления
Интерпретация частного и остатка
Длинный алгоритм деления
Заключение
Предлагаемые и решённые упражнения

Деление и делимость

В арифметике делимость описывает «точный» случай: a\mid b означает, что b записывается точно как кратное a. Однако, хотя делимость между двумя произвольными целыми числами существует не всегда, мы всё же можем задаться вопросом: «сколько раз одно число укладывается в другое и, если оно не укладывается точно, что остаётся». Именно в этом контексте возникает алгоритм деления, который гарантирует, что любое целое число b может быть записано как кратное a плюс «остаток».

В качестве примера рассмотрим a=3 и b=16. Очевидно, что 3 не делит 16. Тем не менее, для операции деления можно найти частное и остаток, поскольку

16 = 5\cdot 3 + 1

Следовательно, при делении b=16 на a=3 (где b является делимым, а a — делителем), обозначаемом как 16/3 или 16\div 3, в качестве частного получаем q=5, а в качестве остатка — r=1. В общем случае алгоритм деления утверждает, что для любых целых чисел a (делитель) и b (делимое) при a\neq 0 существуют единственные целые числа q и r такие, что

b=qa+r,\qquad 0\le r<|a|

В данном примере 16=3\cdot 5+1, и условие 0\le r<|a| выполняется, поскольку 0\le 1<3. Такая формулировка устраняет неоднозначности, когда делитель (или делимое) может быть отрицательным, и гарантирует, что остаток всегда неотрицателен и строго меньше абсолютного значения делителя.

Теорема о евклидовом делении

Результат применения алгоритма деления называется евклидовым делением и опирается на следующий результат.

Теорема: Пусть a,b\in\mathbb{Z} и a\neq 0. Тогда существуют единственные q,r\in\mathbb{Z} такие, что

b=qa+r,\qquad 0\le r<|a|.

Целое число q называется частным, а r — остатком при делении b на a.

Доказательство евклидова деления

Доказательство делится на две части: сначала доказывается существование частного и остатка; затем показывается, что при существовании они являются единственными.

Существование

Пусть a,b\in\mathbb{Z} и a\neq 0, и определим d=|a|, так что d>0. Сначала рассмотрим случай b\ge 0: покажем, что существуют q,r\in\mathbb{Z} такие, что b=dq+r и 0\le r<d. Затем рассмотрим случай b<0. В конце заменим d на |a|, чтобы получить форму b=qa+r с условием 0\le r<|a|.

Для b\in\mathbb{Z} при b\ge 0 установим утверждение P(b): «существуют q,r\in\mathbb{Z} такие, что b=dq+r и 0\le r<d». Докажем по индукции, что P(b) верно для всех b\ge 0.

Базис индукции: Для b=0, принимая q=0 и r=0, получаем 0=d\cdot 0+0 и 0\le 0<d. Следовательно, P(0) истинно.

Индуктивный шаг: Пусть k\ge 0 и предположим, что P(k) истинно. Тогда существуют q,r\in\mathbb{Z} такие, что

k=dq+r,\qquad 0\le r<d.

Прибавляя 1 к обеим частям, получаем

k+1=dq+(r+1).

Кроме того, из 0\le r<d следует, что r+1\le d. Следовательно, возможны лишь случаи r+1<d или r+1=d.

Случай 1: Если r+1<d, определим q'=q и r'=r+1. Тогда

k+1=dq'+r',\qquad 0\le r'<d.

Случай 2: Если r+1=d, то k+1=dq+d=d(q+1)+0. Определим q'=q+1 и r'=0, и выполняется

k+1=dq'+r',\qquad 0\le r'<d.

В обоих случаях мы построили целые числа q',r' такие, что k+1=dq'+r' и 0\le r'<d. Следовательно, P(k+1) истинно. По индукции заключаем, что P(b) верно для всех b\ge 0.

Теперь рассмотрим случай b<0. Тогда -b>0. Применяя предыдущий результат к -b, существуют q,r\in\mathbb{Z} такие, что

-b=dq+r,\qquad 0\le r<d.

Умножая на -1, получаем

b=-dq-r.

Если r=0, достаточно взять q_1=-q и r_1=0, тогда b=dq_1+r_1 и 0\le r_1<d.

Если r>0, определим q_1=-q-1 и r_1=d-r. Поскольку 0<r<d, имеем 0<d-r<d, то есть 0\le r_1<d. Кроме того,

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

Следовательно, для любого b\in\mathbb{Z} существуют q_1,r_1\in\mathbb{Z} такие, что b=dq_1+r_1 и 0\le r_1<d.

Наконец, напомним, что d=|a|. Если a>0, то d=a, и равенство b=dq_1+r_1 записывается как b=aq_1+r_1, при условии 0\le r_1<|a|.

Если a<0, то d=-a, и b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. Определив q=-q_1 и r=r_1, получаем

b=qa+r,\qquad 0\le r<|a|.

Тем самым доказано существование q и r для любых a,b\in\mathbb{Z} при a\neq 0.

Единственность

Предположим, что существуют q,q',r,r'\in\mathbb{Z} такие, что

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

Вычитая оба выражения, получаем

a(q-q')=r'-r.

Так как 0\le r,r'<|a|, выполняется |r'-r|<|a|. С другой стороны, левая часть является кратной a и, следовательно, также кратной |a|. Единственным целым кратным |a|, абсолютное значение которого строго меньше |a|, является 0; действительно, если |a| m \neq 0 при m\in\mathbb{Z}, то \big| |a| m \big| \ge |a| . Следовательно, r'-r=0, то есть r=r', и, подставляя в b=qa+r, получаем q=q'. Таким образом, разложение является единственным.

Интерпретация частного и остатка

• Что означает «остаток». Если b=qa+r, то r=b-qa — это то, что «остаётся» после вычитания из b кратного qa. Иными словами, r является остатком при приведении b к решётке кратных числа a.
• Почему требуется 0\le r<|a|. Без этого условия пара (q,r) не была бы единственной. Действительно, если b=qa+r, то также b=a(q+1)+(r-a). Условие 0\le r<|a| заставляет остаток находиться в фиксированном интервале \{0,1,2,\dots,|a|-1\}, что блокирует бесконечные «переобозначения» одного и того же числа.
• Что происходит, если a отрицательно. Теорема остаётся справедливой без изменений: остаток остаётся неотрицательным и ограниченным сверху числом |a|. Это важно, поскольку некоторые языки программирования используют усечение к нулю и могут порождать отрицательные остатки, тогда как в математике принимается конвенция 0\le r<|a|, чтобы остаток был «стандартным» представителем.

  Кроме того, когда a>0, частное совпадает с целой частью:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Длинный алгоритм деления

На основе евклидова деления можно реализовать длинный алгоритм деления, используя позиционное представление чисел. Этот алгоритм представляет собой вычислительную технику, позволяющую быстро находить значения q и r при необходимости вычислить b\div a для a,b\in\mathbb{Z} и a\neq 0.

Для его описания сначала рассмотрим несколько примеров, иллюстрирующих процесс и возможные ситуации в ходе выполнения алгоритма.

1. Предположим, что мы хотим вычислить 57\div 4. Здесь 57 — это делимое, а 4 — делитель. Для этого выполним следующую последовательность вычислений:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Записать операцию деления.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Выделить первый префикс (слева) делимого, который}\\ &\text{больше или равен делителю, в данном случае 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{Подумать о наибольшем числе, которое при умножении на $4$}\\ &\text{даёт результат, меньший или равный $5$, и записать его справа. Это 1.} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Умножить результат на делитель и вычесть из выбранного значения.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Выбрать и «спустить» следующую цифру.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Повторить последовательность с последним полученным числом.} \end{array}

   Алгоритм завершается, когда исчерпаны все цифры для «спуска», в результате чего получаем частное q=14 и остаток r=1. В частности, остаток всегда будет меньше делителя.

2. Предположим, что мы хотим вычислить 132\div 5. Для этого выполним следующую последовательность вычислений:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Выделить первый префикс делимого и найти натуральное число,}\\ & \text{которое при умножении на 5 будет меньше или равно ему. Если это невозможно,}\\ & \text{присоединять следующую цифру, пока это не станет возможным.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Когда предыдущий шаг выполнен, продолжить алгоритм в обычном режиме.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. Если делимое имеет больше цифр, процедура выполняется аналогичным образом. Например, при вычислении 3521\div 12 получаем:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. Если одно из чисел отрицательно, существуют два допустимых способа представления результата. Однако стандартной формой в теории чисел является та, в которой остаток положителен и, следовательно, согласуется с евклидовым делением. Например, при вычислении -598\div 21 возможны следующие два разложения, оба корректные как тождества:

   • С отрицательным остатком: Он получается путём удаления знака в начале операции и его восстановления в конце.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     Из этого следует:

     598 = 21 \times 28 + 10

     Затем, умножая всё равенство на -1, получаем:

     -598 = 21 \times (-28) - 10

     Таким образом, в этом представлении результатом -598\div 21 является частное q=-28 и остаток r=-10.

     И если вновь умножить всё равенство на -1, получаем:

     598 = (-21)\times(-28) + 10

     Таким образом, результатом 598\div (-21) является частное q=-28 и остаток r=10.

   • С положительным остатком и согласованный с евклидовым делением: Из предыдущего разложения следует:

     -598 = 21 \times (-28) - 10

     Затем, прибавляя 0=21-21 к правой части этого равенства, получаем:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Следовательно, при согласовании с евклидовым делением результат вычисления -598\div 21 даёт частное q=-29 и остаток r=11.

   С точки зрения принятой конвенции в евклидовом делении только результат с положительным остатком соответствует евклидовым частному и остатку. Однако оба выражения являются корректными тождествами и могут быть полезны в различных контекстах. Хотя длинный алгоритм деления может приводить к отрицательным остаткам, это оказывается удобным для механического получения результатов и выполнения алгебраических преобразований без дополнительных шагов. С другой стороны, результаты с положительным остатком, согласованные с евклидовым делением, позволяют зафиксировать канонического представителя каждого класса вычетов (например, в \{0,1,\dots,n-1\}), что облегчает точную и однозначную маркировку целых чисел. Следует отметить, что существуют и другие соглашения о представителях, такие как симметричные вычеты, которые также являются допустимыми после фиксации правила.

Заключение

Алгоритм деления гарантирует, что любое целочисленное деление может быть единственным образом представлено в виде b=qa+r при 0\le r<|a|, что задаёт стандартный критерий интерпретации частного и остатка даже при участии отрицательных чисел. Длинный алгоритм деления представляет собой не более чем практическую реализацию этого разложения, основанную на позиционном представлении, и позволяет механически вычислять q и r. Наконец, эта евклидова форма не только устраняет неоднозначности, но и естественным образом связана с модульной арифметикой: остаток r выступает в роли канонического представителя класса вычетов числа b по модулю a, что лежит в основе многих методов теории чисел и вычислительных приложений, которые будут рассмотрены в последующих материалах.

Предлагаемые и решённые упражнения

Евклидово деление

1. (решено) Найдите q и r такие, что

   137 = 9q + r,\qquad 0\le r\lt 9.

   Решение: Найдите наибольшее число, которое при умножении на 9 не превышает 137. Имеем 15\times 9 = 135 и 16\times 9 = 144, следовательно, искомое частное равно q=15. Теперь вычислите остаток r=137-9q и проверьте, что 0\le r\lt 9. Проверка даёт:

   r=137-9\cdot 15=137-135=2.

   Таким образом, 137=9\cdot 15+2 при 0\le 2\lt 9.

2. (решено) Найдите q и r такие, что

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Решение: Найдите наибольшее число, которое при умножении на 37 не превышает 2025. Заметим, что 37\times 54 = 1998 и 37\times 55 = 2035, следовательно, искомое частное равно q=54. Теперь вычислите остаток r=2025-37q и проверьте, что 0\le r\lt 37. Проверка даёт:

   r=2025-37\cdot 54=2025-1998=27.

   Таким образом, 2025=37\cdot 54+27 при 0\le 27\lt 37.

3. Найдите q и r такие, что

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Найдите q и r такие, что

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Найдите q и r такие, что

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Фиксированный остаток и поиск целых чисел. Пусть a=12.

   (a) Опишите множество всех целых чисел b, для которых евклидово деление на 12 имеет остаток r=5.

   (b) Найдите наименьшее целое число b\gt 1000, удовлетворяющее этому условию, и определите соответствующее частное q.

Длинный алгоритм деления

В каждом случае примените длинный алгоритм деления, чтобы вычислить частное q и остаток r. Преобразуйте результат в евклидово деление, если алгоритм даёт отрицательный остаток.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.