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

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

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 такие, что

а = bq + г

и

0 ≤ р < | б | ,

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

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

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

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

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

Обобщение

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

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

${\displaystyle \deg r<\deg b,}$

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

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

${\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.}$

Пусть и – такая пара чисел, для которой неотрицательна и минимальна. Если у нас есть евклидово деление. Таким образом, нам нужно доказать, что if then не является минимальным. Действительно , если при и не является минимальным ${\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}$

Это доказывает существование во всех случаях. Это также обеспечивает алгоритм вычисления частного и остатка, начиная с (if ) и добавляя к нему до тех пор , пока. Однако этот алгоритм неэффективен, поскольку количество шагов в нем имеет порядок ${\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' < | б | , то у нас должно быть это

q' = q и r' = r .

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

0 ≤ р < | б |

0 ≤ г' < | б |

а = bq + г

а = bq' + r'

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

б ( q – q ′ ) знак равно р ′ – р .

Итак, b является делителем r ′ – r . Как

| р ′ – р | < | б |

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

р ′ – р знак равно 0 ,

и

б ( q – q ′ ) знак равно 0 .

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

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

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

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

Варианты

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

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

При евклидовом делении с d в качестве делителя предполагается, что остаток принадлежит интервалу [0, 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. «Деление и алгоритмы Евклида». www-groups.mcs.st-andrews.ac.uk . Проверено 15 ноября 2019 г.
2. «Что такое модульная арифметика?». Ханская академия . Проверено 15 ноября 2019 г.
3. «Развлечение с модульной арифметикой - BetterExplained» . www.betterexplained.com . Проверено 15 ноября 2019 г.
4. Бертон, Дэвид М. (2010). Элементарная теория чисел . МакГроу-Хилл. стр. 17–19. ISBN 978-0-07-338314-9.
5. Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Уайли. п. 63. ИСБН 0-471-51001-7.
6. Хайнинг Фан; Мин Гу; Цзягуан Сунь; Квок-Ян Лам (2012). «Получение большего количества формул типа Карацубы в двоичном поле». Информационная безопасность ИЭПП . 6 (1): 14–19. CiteSeerX 10.1.1.215.1576 . doi : 10.1049/iet-ifs.2010.0114. 
7. Ротман 2006, с. 267
8. Фрэли 1993, с. 376

Рекомендации

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