Евклидово деление - Euclidean division

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

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

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

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

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

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

Учитывая два целых числа $а$ и $б$ , с участием $б \neq 0$ , существуют уникальный целые числа $q$ и $р$ такой, что

а = бк + р

и

0 \leq р < | б |

,

где $| б |$ обозначает абсолютная величина из $б$ .^[5]

В приведенной выше теореме каждое из четырех целых чисел имеет собственное имя: $а$ называется дивиденд, $б$ называется делитель, $q$ называется частное и $р$ называется остаток.^[1]

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

Разделение не определяется в случае, если $б = 0$ ; увидеть деление на ноль.

Для остатка и операция по модулю, есть соглашения, отличные от $0 \leq р < | б |$ , увидеть § Другие интервалы для остатка.

История

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

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

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

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

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

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

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

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

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

Примеры

Если а = 7 и б = 3, тогда q = 2 и р = 1, поскольку 7 = 3 × 2 + 1.
Если а = 7 и б = −3, то q = −2 и р = 1, поскольку 7 = −3 × (−2) + 1.
Если а = −7 и б = 3, тогда q = −3 и р = 2, так как −7 = 3 × (−3) + 2.
Если а = −7 и б = −3, то q = 3 и р = 2, так как −7 = −3 × 3 + 2.

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

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

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

Рассмотрим сначала случай $б < 0$ . Настройка $б ' = - б$ и $q ' = - q$ , уравнение $а = бк + р$ может быть переписан как $а = b'q ' + р$ и неравенство $0 \leq р < | б |$ может быть переписан как $0 \leq р < | б' |$ . Это сокращает существование случая $б < 0$ к делу $б > 0$ .

Аналогично, если $а < 0$ и $б > 0$ , установка $а ' = - а$ , $q ' = - q - 1$ , и $р' = б - р$ , уравнение $а = бк + р$ может быть переписан как $а ' = bq ' + р'$ , а неравенство $0 \leq р < | б |$ может быть переписан как $0 \leq р' < | б |$ . Таким образом, доказательство существования сводится к случаю $а \geq 0$ и $б > 0$ - которые будут рассмотрены в оставшейся части доказательства.

Позволять $q 1 = 0$ и $р 1 = а$ , то это такие неотрицательные числа, что $а = бк 1 + р 1$ . Если $р 1 < б$ тогда деление завершено, поэтому предположим $р 1 \geq б$ . Затем определяя $q 2 = q 1 + 1$ и $р 2 = р 1 - б$ , надо $а = бк 2 + р 2$ с участием $0 \leq р 2 < р 1$ . Поскольку есть только $р 1$ неотрицательные целые числа меньше чем $р 1$ , достаточно повторить этот процесс не более $р 1$ раз, чтобы достичь последнего частного и остатка. То есть существует натуральное число $k \leq р 1$ такой, что $а = бк k + р k$ и $0 \leq р k < | б |$ .

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

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

Пара целых чисел $р$ и $q$ такой, что $а = бк + р$ является уникальным в том смысле, что не может быть другой пары целых чисел, удовлетворяющей тому же условию в теореме Евклида о делении. Другими словами, если у нас есть другое подразделение $а$ от $б$ , сказать $а = bq ' + р'$ с участием $0 \leq р' < | б |$ , тогда у нас должно быть это

q ' = q и р' = р

.

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

0 \leq р < | б |

0 \leq р' < | б |

а = бк + р

а = bq ' + р'

Вычитание двух уравнений дает

б (q - q') = р' - р

.

Так $б$ является делителем $р' - р$ . Так как

| р' - р | < | б |

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

р' - р = 0

,

и

б (q - q') = 0

.

поскольку $б \neq 0$ мы получаем это $р = р'$ и $q = q'$ , что доказывает часть теоремы Евклида о делении о единственности.

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

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

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

Варианты

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

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

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

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

Это используется для приближения действительные числа: Евклидово деление определяет усечение, а центрированное деление определяет округление.

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

Учитывая целые числа ${ displaystyle a}$ , ${ displaystyle m}$ и ${ displaystyle R,}$ с участием ${ displaystyle m> 0}$ и ${ Displaystyle НОД (р, м) = 1,}$ позволять ${ displaystyle R ^ {- 1}}$ быть модульный мультипликативный обратный из ${ displaystyle R}$ (т.е. ${ displaystyle 0$ с участием ${ displaystyle R ^ {- 1} R-1}$ быть кратным ${ displaystyle m}$ ), то существуют единственные целые числа ${ displaystyle q}$ и ${ displaystyle r}$ с участием ${ Displaystyle 0 Leq г <м}$ такой, что ${ Displaystyle а = mq + R ^ {- 1} cdot r}$ .Этот результат обобщает нечетное деление Гензеля (1900).^[8]

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

В евклидовых областях

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

Учитывая элемент

а

и ненулевой элемент

б

в евклидовой области

р

оснащен Евклидова функция

d

(также известный как Евклидова оценка^[10] или функция степени^[9]), существуют

q

и

р

в

р

такой, что

а = бк + р

и либо

р = 0

или

d (р) < d (б)

.

Уникальность $q$ и $р$ не требуется.^[2] Это происходит только в исключительных случаях, обычно для одномерные многочлены, а для целых чисел, если дальнейшее условие $р \geq 0$ добавлен.

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

Смотрите также

Заметки

^ ^а ^б ^c ^d "Полное руководство по высшей математике по делению в столбик и его вариантам - для целых чисел". Математическое хранилище. 2019-02-24. Получено 2019-11-15.
^ ^а ^б «Деление и евклидовы алгоритмы». www-groups.mcs.st-andrews.ac.uk. Получено 2019-11-15.
^ "Что такое модульная арифметика?". Ханская академия. Получено 2019-11-15.
^ «Развлечение с модульной арифметикой - объяснение лучше». betterexplained.com. Получено 2019-11-15.
^ Бертон, Дэвид М. (2010). Элементарная теория чисел. Макгроу-Хилл. С. 17–19. ISBN 978-0-07-338314-9.
^ «Фибоначчи - Средневековая математика - История математики». www.storyofmat Mathematics.com. Получено 2019-11-15.
^ Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Вили. п. 63. ISBN 0-471-51001-7.
^ Haining Fan; Мин Гу; Jiaguang Sun; Квок-Ян Лам (2012). «Получение большего количества формул типа Карацубы над двоичным полем». Информационная безопасность ИЭПП. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576. Дои:10.1049 / iet-ifs.2010.0114.
^ ^а ^б Ротман 2006, п. 267
^ Фрали 1993, п. 376

использованная литература

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

[:0-1] а ^б ^c ^d "Полное руководство по высшей математике по делению в столбик и его вариантам - для целых чисел". Математическое хранилище. 2019-02-24. Получено 2019-11-15.

[:1-2] а ^б «Деление и евклидовы алгоритмы». www-groups.mcs.st-andrews.ac.uk. Получено 2019-11-15.

[3] "Что такое модульная арифметика?". Ханская академия. Получено 2019-11-15.

[4] «Развлечение с модульной арифметикой - объяснение лучше». betterexplained.com. Получено 2019-11-15.

[5] Бертон, Дэвид М. (2010). Элементарная теория чисел. Макгроу-Хилл. С. 17–19. ISBN 978-0-07-338314-9.

[6] «Фибоначчи - Средневековая математика - История математики». www.storyofmat Mathematics.com. Получено 2019-11-15.

[7] Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Вили. п. 63. ISBN 0-471-51001-7.

[8] Haining Fan; Мин Гу; Jiaguang Sun; Квок-Ян Лам (2012). «Получение большего количества формул типа Карацубы над двоичным полем». Информационная безопасность ИЭПП. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576. Дои:10.1049 / iet-ifs.2010.0114.

[Rot06-9] а ^б Ротман 2006, п. 267

[10] Фрали 1993, п. 376

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]