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

редактировать

Деление остатка целого числа на другое

17 делится на 3 группы по 5, причем 2 как ле ftover. Здесь дивиденд равен 17, делитель равен 5, частное равно 3, а остаток равен 2 (что строго меньше делителя 5) или, что более символично, 17 = (5 × 3) + 2.

В арифметике, евклидово деление - или деление с остатком - это процесс деления на одно целое ( делимое) на другой (делитель) таким образом, чтобы получить частное и остаток меньше, чем делитель. Основным свойством является то, что частное и остаток существуют и уникальны при некоторых условиях. Из-за этой уникальности евклидово деление часто рассматривается без ссылки на какой-либо метод вычисления и без явного вычисления частного и остатка. Методы вычисления называются алгоритмами целочисленного деления, наиболее известным из которых является деление в столбик,.

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

Пирог состоит из 9 кусочков, поэтому каждый из 4 человек получает по 2 ломтика, а 1 остается.

Содержание

1 Теорема о делении
2 История
3 Интуитивный пример
4 Примеры
5 Доказательство
- 5.1 Существование
- 5.2 Уникальность
6 Эффективность
7 Варианты
- 7.1 Другие интервалы для остатка
- 7.2 Подразделение Монтгомери
8 В евклидовых областях
9 См. Также
10 Примечания
11 Ссылки

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

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

Для двух целых чисел и b, при b ≠ 0, существуют уникальные целые числа q и r такие, что

a = bq + r

0 ≤ r < |b|,

, где | b | обозначает абсолютное значение числа b.

В приведенной выше теореме каждое из четырех целых чисел имеет собственное имя: a называется делимым, b называется делителем, q - называется частным, а r - остатком.

Вычисление частного и остатка от делимого и делителя называется делением или, в случае неоднозначности, евклидовым делением. Эту теорему часто называют алгоритмом деления (хотя это теорема, а не алгоритм), потому что ее доказательство, приведенное ниже, поддается простому алгоритму деления для вычисления q и r (см. Раздел Доказательство подробнее).

Деление не определено в случае, когда b = 0; см. деление на ноль.

Для остатка и операции по модулю существуют соглашения, отличные от 0 ≤ r <| b |, см. § Другие интервалы для остатка.

История

Хотя «Евклидово деление» названо в честь Евклида, похоже, что он не знал теоремы существования и уникальности, и что единственным известным ему методом вычислений был деление путем повторного вычитания.

До открытия индуистско-арабской системы счисления, которая была введена в Европе в 13 веке Фибоначчи, деление было чрезвычайно трудным, и использовались только лучшие математики смогли это сделать. В настоящее время большинство алгоритмов деления, включая длинное деление, основаны на этой нотации или ее вариантах, таких как двоичные числа. Заметным исключением является деление Ньютона – Рафсона, которое не зависит от какой-либо системы счисления.

Термин «Евклидово деление» был введен в 20 веке как сокращение для «деления Евклидовы кольца ". Он был быстро принят математиками для отличия этого деления от других видов деления чисел.

Интуитивный пример

Предположим, что пирог состоит из 9 ломтиков, и они делиться поровну между 4 людьми. Используя евклидово деление, 9 делится на 4, получается 2 с остатком 1. Другими словами, каждый человек получает 2 кусочка пирога, и остается 1 кусок.

Это можно подтвердить, используя умножение - обратное деление: если каждый из 4 человек получил 2 среза, то всего было выдано 4 × 2 = 8 срезов. Добавляя 1 оставшийся ломтик, получается 9 ломтиков. Вкратце: 9 = 4 × 2 + 1.

В общем, если количество фрагментов обозначено $a {\ displaystyle a}$ $a$ , а количество людей обозначено $b {\ displaystyle b}$ $b$ , тогда можно разделить пирог поровну между людьми так, чтобы каждый человек получил $q {\ displaystyle q}$ $q$ срезы (частное), с некоторым количеством фрагментов $r < b {\displaystyle r$ ${\ displaystyle r <b}$ , оставшимся (остаток). В этом случае выполняется уравнение $a = b q + r {\ displaystyle a = bq + r}$ ${\ displaystyle a = bq + r}$ .

В качестве альтернативного примера, если 9 фрагментов были разделены между 3 людьми вместо 4, то каждый получил бы 3 и ни один фрагмент не остался бы, что означает, что остаток будет равен нулю, что приведет к выводу, что 3 делит 9 без остатка или 3 делит 9.

Евклидово деление может быть расширено до отрицательного делимого (или отрицательного делителя) по той же формуле; например, −9 = 4 × (−3) + 3, что означает, что −9, разделенное на 4, будет −3 с остатком 3.

Примеры

Если a = 7 и b = 3, то q = 2 и r = 1, поскольку 7 = 3 × 2 + 1.
Если a = 7 и b = −3, то q = −2 и r = 1, поскольку 7 = −3 × (- 2) + 1.
Если a = −7 и b = 3, то q = −3 и r = 2, поскольку −7 = 3 × (−3) + 2.
Если a = −7 и b = −3, то q = 3 и r = 2, так как −7 = −3 × 3 + 2.

Доказательство

Следующее доказательство теоремы о делении опирается на тот факт, что убывающая последовательность неотрицательных целых чисел в конце концов прекращается. Он разделен на две части: одну для существования, а другую для уникальности $q {\ displaystyle q}$ $q$ и $r {\ displaystyle r}$ $r$ . В других доказательствах используется принцип правильного порядка (т. Е. Утверждение, что каждый непустой набор из неотрицательных целых чисел имеет наименьший элемент), чтобы сделать рассуждения проще, но имеют недостаток в том, что они не предоставляют напрямую алгоритм для решения деления (подробнее см. § Эффективность).

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

Сначала рассмотрим случай b < 0. Setting b' = –b and q' = –q, the equation a = bq + r may be rewritten as a = b'q' + r and the inequality 0 ≤ r < |b| may be rewritten as 0 ≤ r < |b′|. This reduces the existence for the case b < 0 to that of the case b>0.

Аналогично, если a < 0 and b>0, установив a '= –a, q' = –q - 1 и r '= b - r, уравнение a = bq + r может быть переписано как '= bq' + r 'и неравенство 0 ≤ r < |b| may be rewritten as 0 ≤ r' < |b|. Thus the proof of the existence is reduced to the case a ≥ 0 and b>0 - которое будет рассмотрено в оставшейся части доказательства.

Пусть q 1 = 0 и r 1 = a, тогда это неотрицательные числа такие, что a = bq 1 + r 1. Если r 1< b then the division is complete, so suppose r1≥ b. Затем, определяя q 2 = q 1 + 1 и r 2 = r 1 - b, получаем a = bq 2 + r 2 с 0 ≤ r 2< r1. Поскольку существует только r 1 неотрицательных целых чисел, меньших, чем r 1, достаточно повторить этот процесс не более r 1 раз, чтобы получить окончательное частное и остальное. То есть существует натуральное число k ≤ r 1 такое, что a = bq k + r k и 0 ≤ r k< |b|.

Это доказывает существование а также дает простой алгоритм деления для вычисления частного и остатка. Однако этот алгоритм неэффективен, так как его количество шагов порядка a / b.

Уникальность

Пара целых чисел r и q такая, что a = bq + r уникальна в том смысле, что не может быть другой пары целых чисел, удовлетворяющей тому же условию в Теорема Евклида о делении. Другими словами, если у нас есть другое деление a на b, скажем, a = bq '+ r' с 0 ≤ r '< |b|, then we must have that

q' = q и r '= r.

Чтобы доказать это утверждение, мы сначала начнем с предположения, что

0 ≤ r < |b|

0 ≤ r '< |b|

a = bq + r

a = bq' + r '

Вычитая два уравнения дают

b (q - q ′) = r ′ - r.

Таким образом, b является делителем r ′ - r. Поскольку

| r ′ - r | < |b|

по указанным выше неравенствам получаем

r ′ - r = 0,

b (q - q ′) = 0.

Поскольку b ≠ 0, получаем, что r = r ′ и q = q ′, что доказывает часть теоремы о единственности евклидова деления.

Эффективность

В общем, доказательство существования не предоставляет алгоритм для вычисления существующего частного и остатка, но приведенное выше доказательство немедленно предоставляет алгоритм (см. Алгоритм деления # Деление путем повторного вычитания ), хотя он не очень эффективен, так как требует столько же шагов, сколько размер частного. Это связано с тем, что он использует только сложение, вычитание и сравнение целых чисел, без использования умножения, а также какое-либо конкретное представление целых чисел, такое как десятичная запись.

С точки зрения десятичной записи, деление в столбик обеспечивает гораздо более эффективный алгоритм решения евклидовых делений. Его обобщение на двоичную и шестнадцатеричную нотацию обеспечивает дополнительную гибкость и возможность компьютерной реализации. Однако для больших входных данных обычно предпочтительны алгоритмы, сводящие деление к умножению, такие как Ньютон – Рафсон, потому что им требуется только время, пропорциональное времени умножения, необходимого для проверки результата. независимо от используемого алгоритма умножения (подробнее см. Алгоритм деления # Методы быстрого деления ).

Варианты

Евклидово деление допускает ряд вариантов, некоторые из которых перечислены ниже.

Другие интервалы для остатка

При евклидовом делении с d в качестве делителя остаток должен принадлежать интервалу [0, d) длины | d |. Может использоваться любой другой интервал такой же длины. Точнее, заданы целые числа $m {\ displaystyle m}$ $m$ , $a {\ displaystyle a}$ $a$ , $d {\ displaystyle d}$ $d$ с $m>0 {\ displaystyle m>0}$ $m>0$ существуют уникальные целые числа $q {\ displaystyle q}$ $q$ и $r {\ displaystyle r}$ $r$ с $d ≤ r < m + d {\displaystyle d\leq r$ $d \ leq r <m + d$ такие что $a = mq + r {\ displaystyle a = mq + r}$ $a = mq + r$ .

В частности, если $d = - ⌊ m 2 ⌋ {\ displaystyle d = - \ left \ lfloor {\ frac {m } {2}} \ right \ rfloor}$ $d = - \ left \ lfloor {\ frac {m} {2}} \ right \ rfloor$ , затем $- ⌊ m 2 ⌋ ≤ r < m − ⌊ m 2 ⌋ {\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r$ $- \ left \ lfloor {\ frac {m} {2}} \ right \ rfloor \ leq r <m- \ left \ lfloor {\ frac {m} {2}} \ right \ rfloor$ . Это деление называется центрированным делением, а его остаток $r { \ displaystyle r}$ $r$ называется центрированным остатком или наименьшим абсолютным остатком.

Используется для аппроксимации действительных чисел : евклидово деление определяет усечение, а центрированное деление определяет округление.

деление Монтгомери

Заданные целые числа $a {\ displaystyle a}$ $a$ , $m {\ displaystyle m}$ $m$ и $R, {\ displaystyle R,}$ $R,$ с $m>0 { \ displaystyle m>0}$ $m>0$ и $gcd (R, m) = 1, {\ displaystyle \ gcd (R, m) = 1,}$ $\ gcd (R, m) = 1,$ let $R - 1 {\ displaystyle R ^ { -1}}$ $R ^ {- 1}$ быть модульным мультипликативным обратным для $R {\ displaystyle R}$ $R$ (т. Е. $0 < R − 1 < m {\displaystyle 0$ $0 <R ^ {- 1} <m$ с $R - 1 R - 1 {\ displaystyle R ^ {- 1} R-1}$ $R ^ {- 1} R-1$ кратное $m {\ displaystyle m}$ $m$ ), то существуют уникальные целые числа $q {\ displaystyle q}$ $q$ и $r {\ displaystyle r}$ $r$ с $0 ≤ r < m {\displaystyle 0\leq r$ $0 \ leq r <m$ таким образом, что $a = mq + Р - 1 ⋅ р {\ displaystyle a = mq + R ^ {- 1} \ cdot r}$ $a = mq + R ^ {- 1} \ cdot r$ . Этот результат обобщает нечетное деление Гензеля (1900).

Значение $r {\ displaystyle r}$ $r$ - это N-остаток, определенный в редукции Монтгомери.

в евклидовом домены

Евклидовы домены (также известные как евклидовы кольца ) определяются как целостные домены, которые поддерживают следующее обобщение евклидова деления:

Для элемента a и ненулевой элемент b в евклидовой области R, снабженный евклидовой функцией d (также известной как евклидова оценка или функция степени ), существует q и r в R такое, что a = bq + r и либо r = 0, либо d (r) < d(b).

Единственность q и r не требуется. Это происходит только в исключительных случаях, обычно для одномерных многочленов, и для целых чисел, если добавляется дополнительное условие r ≥ 0.

Примеры евклидовых областей включают поля, кольца полиномов в одной переменной над полем и гауссовские целые числа. Евклидово деление многочленов было предметом конкретных разработок.

См. Также

Примечания

Ссылки

Фрали, Джон Б. (1993), Первый курс абстрактной алгебры (5-е изд..), Аддисон-Уэсли, ISBN 978-0-201-53467-2
Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Прентис-Холл, ISBN 978-0-13-186267-8