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

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

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

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

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

Теорема о делении [ править ]

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

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

а = bq + r

и

0 ≤ r <| б | ,

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

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

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

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

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

История [ править ]

Этот раздел требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Евклидово деление»  -  новости  · газеты  · книги  · ученый  · JSTOR ( сентябрь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

До открытия индуистско-арабской системы счисления , которая была введена в Европе в 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<b}$${\displaystyle a=bq+r}$

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

Евклидово деление также может быть расширено до отрицательного делимого (или отрицательного делителя) с использованием той же формулы; ^[1], например, −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.

Доказательство [ править ]

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

Существование [ править ]

Рассмотрим сначала случай b <0 . Положив b ' = - b и q' = - q , уравнение a = bq + r может быть переписано как a = b'q ' + r и неравенство 0 ≤ r < | б | можно переписать как 0 ≤ r < | b ′ | . Это сводит существование случая b <0 к случаю b > 0 .

Точно так же, если a <0 и b > 0 , установив a ' = - a , q' = - q - 1 и r ' = b - r , уравнение a = bq + r может быть переписано как a' = bq ' + r ′ , и неравенство 0 ≤ r <| б | можно переписать как 0 ≤ r ' <| б |. Таким образом, доказательство существования сводится к случаю a ≥ 0 и b > 0, который будет рассмотрен в оставшейся части доказательства.

Пусть q ₁ = 0 и r ₁ = a , тогда это неотрицательные числа такие, что a = bq ₁ + r ₁ . Если r ₁ < b, то деление завершено, поэтому предположим, что r ₁ ≥ b . Тогда, определяя q ₂ = q ₁ + 1 и r ₂ = r ₁ - b , получаем a = bq ₂ + r ₂при 0 ≤ r ₂ < r ₁ . Так как существует только r ₁ неотрицательных целых чисел, меньших r ₁ , достаточно повторить этот процесс не более r ₁ раз, чтобы получить окончательное частное и остаток. То есть существует натуральное число k ≤ r ₁ такое, что a = bq _k + r _k и 0 ≤ r _k <| б | .

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

Уникальность [ править ]

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

q ' = q и r' = r .

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

0 ≤ r <| б |

0 ≤ r ' <| б |

а = bq + r

а = bq ' + r'

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

б ( д - д ' ) = г ' - г .

Значит, b является делителем r ′ - r . В качестве

| r ′ - r | <| б |

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

г ' - г = 0 ,

и

б ( д - д ' ) = 0 .

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

Эффективность [ править ]

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

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

Варианты [ править ]

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

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

При евклидовом делении с 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}$

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

Отделение Монтгомери [ править ]

Учитывая целые числа , и с и LET быть модульным мультипликативный обратный из (т.е. с быть кратным ), то существуют уникальные целые и с такими , что . Этот результат обобщает нечетное деление Гензеля (1900). ^[8]${\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}$

В евклидовых областях [ править ]

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

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

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

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