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

Деление с остатком целых чисел

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

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

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

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

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

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

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

а = бк + р

и

0 ≤ г < | б | ,

где | b | обозначает абсолютное значение b . ^[4 ]

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

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

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

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

Обобщение

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

В случае одномерных полиномов основное отличие состоит в том, что неравенства заменяются на ${\displaystyle 0\leq r<|b|}$

${\displaystyle r=0}$или ${\displaystyle \deg r<\deg b,}$

где обозначает степень полинома . ${\displaystyle \deg }$

При обобщении на евклидовы области неравенство принимает вид

${\displaystyle r=0}$или ${\displaystyle f(r)<f(b),}$

где обозначают определенную функцию из области определения натуральных чисел, называемую «евклидовой функцией». ${\displaystyle f}$

Уникальность частного и остатка остается верной для многочленов, но в общем случае она неверна.

История

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

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

Термин «евклидово деление» был введен в 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<b}$ ${\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.

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

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

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

Для доказательства существования евклидова деления можно предположить, поскольку, если равенство можно переписать Таким образом, если последнее равенство является евклидовым делением, то первое также является евклидовым делением. ${\displaystyle b>0,}$ ${\displaystyle b<0,}$ ${\displaystyle a=bq+r}$ ${\displaystyle a=(-b)(-q)+r.}$ ${\displaystyle -b>0,}$

Даны и существуют целые числа и такие, что например, и если и в противном случае и ${\displaystyle b>0}$ ${\displaystyle a,}$ ${\displaystyle q_{1}}$ ${\displaystyle r_{1}\geq 0}$ ${\displaystyle a=bq_{1}+r_{1};}$ ${\displaystyle q_{1}=0}$ ${\displaystyle r_{1}=a}$ ${\displaystyle a\geq 0,}$ ${\displaystyle q_{1}=a}$ ${\displaystyle r_{1}=a-ab.}$

Пусть и будет такой парой чисел, для которой является неотрицательным и минимальным. Если у нас есть евклидово деление. Таким образом, мы должны доказать, что если то является не минимальным. Действительно, если есть с и является не минимальным ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r<b.}$ ${\displaystyle r\geq b,}$ ${\displaystyle r}$ ${\displaystyle r\geq b,}$ ${\displaystyle a=b(q+1)+(r-b),}$ ${\displaystyle 0\leq r-b<r,}$ ${\displaystyle r}$

Это доказывает существование во всех случаях. Это также дает алгоритм для вычисления частного и остатка, начиная с (если ) и добавляя к нему до Однако этот алгоритм неэффективен, поскольку его число шагов имеет порядок ${\displaystyle q=0}$ ${\displaystyle a\geq 0}$ ${\displaystyle 1}$ ${\displaystyle a-bq<b.}$ ${\displaystyle a/b}$

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

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

q' = q и r' = r .

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

0 ≤ г < | б |

0 ≤ г' < | б |

а = бк + р

а = бк' + р'

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

б ( q – q ′ ) = г ′ – г .

Так что b является делителем r ′ – r . Так как

| г ′ – г | < | б |

по приведенным выше неравенствам получаем

г ′ – г = 0 ,

и

б ( q – q ′ ) = 0 .

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

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

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

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

Варианты

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

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

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

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

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

дивизия Монтгомери

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

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

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

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

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

Уникальность q и r не требуется. ^[1] Она возникает только в исключительных случаях, обычно для одномерных полиномов и для целых чисел, если добавляется дополнительное условие r ≥ 0 .

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

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

• Лемма Евклида
• Алгоритм Евклида

Примечания

1. "Division and Euclidean algorithms". www-groups.mcs.st-andrews.ac.uk . Архивировано из оригинала 2021-05-06 . Получено 2019-11-15 .
2. "Что такое модульная арифметика?". Khan Academy . Получено 2019-11-15 .
3. «Веселье с модульной арифметикой – BetterExplained». betterexplained.com . Получено 15.11.2019 .
4. Бертон, Дэвид М. (2010). Элементарная теория чисел . McGraw-Hill. стр. 17–19. ISBN 978-0-07-338314-9.
5. Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Wiley. стр. 63. ISBN 0-471-51001-7.
6. Хайнинг Фань; Мин Гу; Цзягуан Сан; Квок-Ян Лам (2012). «Получение большего количества формул, подобных формулам Карацубы, над двоичным полем». IET Information Security . 6 (1): 14–19. CiteSeerX 10.1.1.215.1576 . doi :10.1049/iet-ifs.2010.0114. 
7. Rotman 2006, стр. 267
8. Фрейли 1993, стр. 376

Ссылки

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