Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Деление с остатком целых чисел, деление целых чисел
Division with remainder of integers
division of integers
В арифметике, евклидово деление – или деление с остатком – это процесс деления одного целого числа (делимого) на другое (делитель), таким образом, чтобы получить целое частное и остаток, являющийся натуральным числом, строго меньшим абсолютной величины делителя. Фундаментальным свойством является то, что частное и остаток существуют и являются однозначными при определенных условиях. Благодаря этой однозначности, евклидово деление часто рассматривается без привязки к какому-либо методу вычисления и без явного вычисления частного и остатка. Методы вычисления называются алгоритмами целочисленного деления, наиболее известным из которых является деление в столбик. Евклидово деление и алгоритмы его вычисления имеют основополагающее значение для многих вопросов, связанных с целыми числами, таких как алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел и модульная арифметика, в которой рассматриваются только остатки. Операция, заключающаяся в вычислении только остатка, называется операцией взятия по модулю и часто используется как в математике, так и в информатике.
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor. A fundamental property is that the quotient and the remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder. The methods of computation are called integer division algorithms, the best known of which being long division. Euclidean division, and algorithms to compute it, are fundamental for many questions concerning integers, such as the Euclidean algorithm for finding the greatest common divisor of two integers, and modular arithmetic, for which only remainders are considered. The operation consisting of computing only the remainder is called the modulo operation, and is used often in both mathematics and computer science.
История
Хотя "евклидово деление" названо в честь Евклида, по-видимому, он не знал теорему о существовании и единственности, и единственным методом вычисления, который он использовал, было деление посредством повторного вычитания. До открытия системы арабских и индуистских цифр, представленной в Европе в XIII веке Фибоначчи, деление было чрезвычайно сложным, и только выдающиеся математики могли его выполнять. В настоящее время большинство алгоритмов деления, включая деление в столбик, основаны на этой системе счисления или её вариантах, таких как двоичная система. Примечательным исключением является метод Ньютона-Рафсона, который не зависит от какой-либо системы счисления. Термин "евклидово деление" был введен в XX веке как сокращение для "деления в евклидовых кольцах". Математики быстро приняли его для разграничения этого вида деления от других типов деления чисел.
Although "Euclidean division" is named after Euclid, it seems that he did not know the existence and uniqueness theorem, and that the only computation method that he knew was the division by repeated subtraction. Before the discovery of Hindu–Arabic numeral system, which was introduced in Europe during the 13th century by Fibonacci, division was extremely difficult, and only the best mathematicians were able to do it. Presently, most division algorithms, including long division, are based on this notation or its variants, such as binary numerals. A notable exception is Newton–Raphson division, which is independent from any numeral system. The term "Euclidean division" was introduced during the 20th century as a shorthand for "division of Euclidean rings". It has been rapidly adopted by mathematicians for distinguishing this division from the other kinds of division of numbers.
Интуитивный пример
Предположим, что пирог состоит из 9 кусков, которые нужно поровну разделить между 4 людьми. Используя алгоритм Евклида, 9, деленное на 4, дает 2 и остаток 1. Другими словами, каждый человек получит по 2 куска пирога, и останется 1 кусок. Это можно проверить умножением, которое является обратной операцией деления: если каждый из 4 человек получит по 2 куска, то всего будет раздано 4 × 2 = 8 кусков. Добавив оставшийся кусок, получим 9 кусков. Таким образом: 9 = 4 × 2 + 1. В общем случае, если количество кусков обозначено как *a*, а количество людей – как *b*, то можно разделить пирог поровну между людьми так, чтобы каждый человек получил *q* кусков (частное), при этом *r* кусков останется (остаток). В этом случае выполняется уравнение *a* = *b* × *q* + *r*. Если бы 9 кусков делили между 3 людьми вместо 4, то каждый получил бы 3 куска, и ничего бы не осталось, то есть остаток был бы равен нулю, что означает, что 3 делит 9 нацело, или что 3 является делителем 9. Алгоритм Евклида также можно применять к отрицательным делимым (или отрицательным делителям), используя ту же формулу; например, −9 = 4 × (−3) + 3, что означает, что −9, деленное на 4, равно −3 с остатком 3.
Suppose that a pie has 9 slices and they are to be divided evenly among 4 people. Using Euclidean division, 9 divided by 4 is 2 with remainder 1. In other words, each person receives 2 slices of pie, and there is 1 slice left over. This can be confirmed using multiplication, the inverse of division: if each of the 4 people received 2 slices, then 4 × 2 = 8 slices were given out in total. Adding the 1 slice remaining, the result is 9 slices. In summary: 9 = 4 × 2 + 1. In general, if the number of slices is denoted and the number of people is denoted , then one can divide the pie evenly among the people such that each person receives slices (the quotient), with some number of slices being the leftover (the remainder). In which case, the equation holds. If 9 slices were divided among 3 people instead of 4, then each would receive 3 and no slice would be left over, which means that the remainder would be zero, leading to the conclusion that 3 evenly divides 9, or that 3 divides 9. Euclidean division can also be extended to negative dividend (or negative divisor) using the same formula; for example −9 = 4 × (−3) + 3, which means that −9 divided by 4 is −3 with remainder 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.
If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 3 × 2 + 1. If a = 7 and b = −3, then q = −2 and r = 1, since 7 = −3 × (−2) + 1. If a = −7 and b = 3, then q = −3 and r = 2, since −7 = 3 × (−3) + 2. If a = −7 and b = −3, then q = 3 and r = 2, since −7 = −3 × 3 + 2.
Доказательство
Следующее доказательство теоремы о делении опирается на тот факт, что убывающая последовательность неотрицательных целых чисел рано или поздно остановится. Оно разделено на две части: одна посвящена существованию, а другая – единственности. Другие доказательства используют принцип благоупорядоченности (то есть утверждение, что любое непустое множество неотрицательных целых чисел имеет наименьший элемент), чтобы упростить рассуждения, но имеют недостаток: они не предоставляют напрямую алгоритм для выполнения деления (см. для получения дополнительной информации).
The following proof of the division theorem relies on the fact that a decreasing sequence of non negative integers stops eventually. It is separated into two parts: one for existence and another for uniqueness of and Other proofs use the well ordering principle (i. e., the assertion that every non empty set of non negative integers has a smallest element) to make the reasoning simpler, but have the disadvantage of not providing directly an algorithm for solving the division (see for more).