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

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

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

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

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

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

а = bq + г

и

0 \leq р < | б |

,

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

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

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

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

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

Обобщение

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

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

r=0

или

\deg r<\deg b,

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

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

r=0

или

f(r)<f(b),

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

Единственность частного и остатка остается верной для многочленов, но в целом она неверна.

История

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

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

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

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

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

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

В общем случае, если количество срезов обозначается $a$ и количество человек обозначается $b$ , то можно разделить пирог поровну между людьми так, чтобы каждый получил $q$ срезы (частное), с некоторым количеством срезов $r<b$ будучи остатком (остатком). В этом случае уравнение $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$ и $r$ . Другие доказательства используют принцип правильного порядка (т. е. утверждение, что каждый непустой набор имеет неотрицательных целых чисел наименьший элемент), чтобы упростить рассуждения, но имеют тот недостаток, что не предоставляют непосредственно алгоритм решения деления ( см. § Эффективность ). подробнее ^[5]

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

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

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

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

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

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

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

q' = q и r' = r

.

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

0 \leq р < | б |

0 \leq г' < | б |

а = bq + г

а = bq' + r'

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

б (q - q') знак равно р' - р

.

Итак, $b$ является делителем $r' - r$ . Как

| р' - р | < | б |

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

р' - р знак равно 0

,

и

б (q - q') знак равно 0

.

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

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

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

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

Варианты

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

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

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

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

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

Подразделение Монтгомери

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

Значение $r$ N $-$ остаток, определенный в сокращении Монтгомери .

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

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

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

a

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

b

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

R,

снабженной евклидовой функцией

d

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

q

и

r

в

R

такие, что

a = bq + r

и либо

r = 0,

либо

d (r) < d (b)

.

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

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

См. также

Примечания

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

Ссылки

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

[:1-1] Jump up to: ^а ^б «Деление и алгоритмы Евклида» . www-groups.mcs.st-andrews.ac.uk . Архивировано из оригинала 06 мая 2021 г. Проверено 15 ноября 2019 г.

[2] «Что такое модульная арифметика?» . Ханская академия . Проверено 15 ноября 2019 г.

[3] «Развлечение с модульной арифметикой – BetterExplained» . bestexplained.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 .

[Rot06-7] Jump up to: ^а ^б Ротман 2006 , с. 267

[8] Фрэли 1993 , с. 376

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]