Деление с остатком

Деление c остатком — арифметическая операция, играющая большую роль в арифметике, теории чисел, алгебре и криптографии. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом^[1]. Пусть $\text{[math]}$ $\text{[math]}$ $a$ $a$ и $\text{[math]}$ $\text{[math]}$ $b$ $b$ — целые числа, причём $\text{[math]}$ $\text{[math]}$ $b\neq 0.$ $b\neq 0.$ Деление с остатком $\text{[math]}$ $\text{[math]}$ $a$ $a$ («делимого») на $\text{[math]}$ $\text{[math]}$ $b$ $b$ («делитель») означает нахождение таких целых чисел $\text{[math]}$ $\text{[math]}$ $q$ $q$ и $\text{[math]}$ $\text{[math]}$ $r$ $r$ , что выполняется равенство:

\text{[math]}

a=b\cdot q+r

a=b\cdot q+r

Таким образом, результатами деления с остатком являются два целых числа: $\text{[math]}$ $\text{[math]}$ $q$ $q$ называется неполным частным от деления, а $\text{[math]}$ $\text{[math]}$ $r$ $r$ — остатком от деления. На остаток налагается дополнительное условие: $\text{[math]}$ $\text{[math]}$ $0\leqslant r<|b|,$ $0\leqslant r<|b|,$ то есть остаток от деления должен быть неотрицательным числом и по абсолютной величине меньше делителя. Это условие обеспечивает однозначность результатов деления с остатком для всех целых чисел, то есть существует единственное решение уравнения $\text{[math]}$ $\text{[math]}$ $a=b\cdot q+r$ $a=b\cdot q+r$ при заданных выше условиях. Если остаток равен нулю, говорят, что $\text{[math]}$ $\text{[math]}$ $a$ $a$ нацело делится на $\text{[math]}$ $\text{[math]}$ $b .$ $b.$

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

Примеры

При делении с остатком положительного числа $\text{[math]}$ $\text{[math]}$ $a=78$ $a=78$ на $\text{[math]}$ $\text{[math]}$ $b=33$ $b=33$ получаем неполное частное $\text{[math]}$ $\text{[math]}$ $q=2$ $q=2$ и остаток $\text{[math]}$ $\text{[math]}$ $r=12$ $r=12$ .

Проверка:

\text{[math]}

78=33\cdot 2+12.

78=33\cdot 2+12.

При делении с остатком отрицательного числа $\text{[math]}$ $\text{[math]}$ $a=-78$ $a=-78$ на $\text{[math]}$ $\text{[math]}$ $b=33$ $b=33$ получаем неполное частное $\text{[math]}$ $\text{[math]}$ $q=-3$ $q=-3$ и остаток $\text{[math]}$ $\text{[math]}$ $r=21$ $r=21$ .

Проверка:

\text{[math]}

-78=33\cdot (-3)+21.

-78=33\cdot (-3)+21.

При делении с остатком отрицательного числа $\text{[math]}$ $\text{[math]}$ $a=-9$ $a=-9$ на $\text{[math]}$ $\text{[math]}$ $b=-13$ $b=-13$ получаем неполное частное $\text{[math]}$ $\text{[math]}$ $q=1$ $q=1$ и остаток $\text{[math]}$ $\text{[math]}$ $r=4$ $r = 4$ .

Проверка:

\text{[math]}

-9=1\cdot (-13)+4.

-9=1\cdot (-13)+4.

При делении с остатком положительного числа $\text{[math]}$ $\text{[math]}$ $a=9$ $a=9$ на $\text{[math]}$ $\text{[math]}$ $b=90$ $b=90$ получаем неполное частное $\text{[math]}$ $\text{[math]}$ $q=0$ $q=0$ и остаток $\text{[math]}$ $\text{[math]}$ $r=9$ $r=9$ .

Проверка:

\text{[math]}

9=90\cdot 0+9.

9=90\cdot 0+9.

При делении с остатком числа $\text{[math]}$ $\text{[math]}$ $a=78$ $a=78$ на $\text{[math]}$ $\text{[math]}$ $b=26$ $b=26$ получаем неполное частное $\text{[math]}$ $\text{[math]}$ $q=3$ $q=3$ и остаток $\text{[math]}$ $\text{[math]}$ $r=0$ $r=0$ , то есть деление выполняется нацело.

Операция деления с остатком может быть определена не только для целых чисел, но и для других математических объектов (например, для многочленов), см. ниже.

ОпределениеПравить

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

Для вычисления неполного частного от деления $\text{[math]}$ $\text{[math]}$ $a$ на положительное число $\text{[math]}$ $\text{[math]}$ $b$ следует разделить (в обычном смысле) $\text{[math]}$ $\text{[math]}$ $a$ на $\text{[math]}$ $\text{[math]}$ $b$ и округлить результат до ближайшего целого в меньшую сторону:

\text{[math]}

q=\left\lfloor {\frac {a}{b}}\right\rfloor ,

когда

\text{[math]}

b>0

.

где полускобки $\text{[math]}$ $\text{[math]}$ $\left\lfloor \cdot \right\rfloor$ обозначают взятие целой части. Значение неполного частного $\text{[math]}$ $\text{[math]}$ $q$ позволяет вычислить значение остатка $\text{[math]}$ $\text{[math]}$ $r$ по формуле:

\text{[math]}

r=a-b\cdot q.

Для отрицательного делителя нужно округлять частное в большую сторону:

\text{[math]}

q=\left\lceil {\frac {a}{b}}\right\rceil ,

когда

\text{[math]}

b<0

.

Операция «mod» и связь со сравнениямиПравить

Величина остатка может быть получена бинарной операцией «взятия остатка» от деления $\text{[math]}$ $\text{[math]}$ $a$ на $\text{[math]}$ $\text{[math]}$ $b$ , обозначаемой $\text{[math]}$ mod:

\text{[math]}

r=a{\bmod {b}}.

Не следует путать это обозначение с обозначением сравнения по модулю $\text{[math]}$ $\text{[math]}$ $b$ . Формула для $\text{[math]}$ $\text{[math]}$ $r$ влечёт выполнение сравнения:

\text{[math]}

r\equiv a{\pmod {b}},

однако обратная импликация, вообще говоря, неверна. А именно, это сравнение не подразумевает выполнения неравенства $\text{[math]}$ $\text{[math]}$ $0\leqslant r<|b|$ , необходимого для того, чтобы $\text{[math]}$ $\text{[math]}$ $r$ было остатком.

В программированииПравить

Операция вычисления неполного частного и остатка в различных языках программирования
Язык	Неполное частное	Остаток	Знак остатка
ActionScript		`%`	Делимое
Ada		`mod`	Делитель
`rem`	Делимое
Бейсик	`\`	`MOD`	Не определено
Си (ISO 1990)	`/`	`%`	Не определено
Си (ISO 1999)	`/`	`%`	Делимое^[3]
C++ (ISO 2003)	`/`	`%`	Не определено^[4]
C++ (ISO 2011)	`/`	`%`	Делимое^[5]
C#	`/`	`%`	Делимое
ColdFusion		`MOD`	Делимое
Common Lisp		`mod`	Делитель
	`rem`	Делимое
D	`/`	`%`	Делимое^[6]
Delphi	`div`	`mod`	Делимое
Eiffel	`//`	`\\`	Делимое
Erlang	`div`	`rem`	Делимое
Euphoria		`remainder`	Делимое
Microsoft Excel (англ.)	`QUOTIENT()`	`MOD()`	Делитель
Microsoft Excel (рус.)	`ЧАСТНОЕ()`	`ОСТАТ()`
FileMaker	`Div()`	`Mod()`	Делитель
Fortran		`mod`	Делимое
	`modulo`	Делитель
GML (Game Maker)	`div`	`mod`	Делимое
Go	`/`	`%`	Делимое
Haskell	`div`	`mod`	Делитель
`quot`	`rem`	Делимое
J		`\|~`	Делитель
Java	`/`	`%`	Делимое^[7]
`Math.floorDiv`	`Math.floorMod`	Делитель (1.8+)
JavaScript	.toFixed(0)	`%`	Делимое
Lua		`%`	Делитель
Mathematica	`Quotient`	`Mod`	Делитель
MATLAB	`idivide(?, ?, 'floor')`	`mod`	Делитель
`idivide`	`rem`	Делимое
MySQL	`DIV`	`MOD` `%`	Делимое
Oberon	`DIV`	`MOD`	+
Objective Caml		`mod`	Не определено
Pascal	`div`	`mod`	Делимое^[8]
Perl	Нет	`%`	Делитель
PHP	Нет^[9]	`%`	Делимое
PL/I		`mod`	Делитель (ANSI PL/I)
Prolog (ISO 1995)		`mod`	Делитель
PureBasic	`/`	`Mod` `%`	Делимое
Python	`//`	`%`	Делитель
QBasic	`\`	`MOD`	Делимое
R	%/%	`%%`	Делитель
RPG		`%REM`	Делимое
Ruby	`/`	`%`	Делитель
Scheme		`modulo`	Делитель
SenseTalk		`modulo`	Делитель
`rem`	Делимое
Tcl		`%`	Делитель
Verilog (2001)		`%`	Делимое
VHDL		`mod`	Делитель
`rem`	Делимое
Visual Basic	`\`	`Mod`	Делимое

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

Обозначения операции взятия остатка в различных языках программирования представлены в таблице справа. Например, в Паскале операция mod вычисляет остаток от деления, а операция div осуществляет целочисленное деление, при котором остаток от деления отбрасывается:

78 mod 33 = 12
78 div 33 = 2

Знак остаткаПравить

Операция взятия остатка в языках программирования может возвращать отрицательный результат (для отрицательного делимого или делителя). Тут есть два варианта:

Знак остатка совпадает со знаком делимого: неполное частное округляет к нулю.
Знак остатка совпадает со знаком делителя: неполное частное округляет к $\text{[math]}$ $\text{[math]}$ $-\infty$ .

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

Есть сумма $\text{[math]}$ $\text{[math]}$ $n$ копеек, положительная или отрицательная. Перевести её в рубли и копейки: n div 100 и n mod 100. Знак остатка совпадает со знаком делимого.
Есть бесконечное клеточное поле, каждая клетка 16×16 пикселей. В какую клетку попадает точка ( $\text{[math]}$ $\text{[math]}$ $x$ , $\text{[math]}$ $\text{[math]}$ $y$ ), и каковы координаты относительно верхнего левого угла клетки? Ответ: x div 16, y div 16 и (x mod 16, y mod 16) соответственно. Знак остатка совпадает со знаком делителя.

Операция div в x86/x64 делит регистровую пару rdx:rax на любой другой регистр или число из памяти^[10]. Неполное частное и остаток выходят по первому варианту — округляют к нулю.

Как запрограммировать, если такой операции нет?Править

Неполное частное можно вычислить через деление и взятие целой части: $\text{[math]}$ $\text{[math]}$ $q=\left[{\frac {a}{b}}\right]$ , где $\text{[math]}$ $\text{[math]}$ $[x]$ , в зависимости от задачи, может быть «полом» или усечением. Однако деление здесь получается дробное, которое намного медленнее целого. Такой алгоритм используется в языках, в которых нет целых типов (отдельные электронные таблицы, программируемые калькуляторы и математические программы), а также в скриптовых языках, в которых издержки интерпретации намного превышают издержки дробной арифметики (Perl, PHP).

При отсутствии команды mod остаток программируется как $\text{[math]}$ $\text{[math]}$ $a-qb$ .

Если $\text{[math]}$ $\text{[math]}$ $b$ положительно, а знак $\text{[math]}$ $\text{[math]}$ $r$ совпадает со знаком делимого, не определён или неизвестен, для нахождения минимального неотрицательного остатка можно воспользоваться формулой $\text{[math]}$ $\text{[math]}$ $r'=(b+(a\operatorname {mod} b))\operatorname {mod} b$ .

Неполное частное и неотрицательный остаток от деления на степень двойки $\text{[math]}$ $\text{[math]}$ $2^{n}$ — это битовый сдвиг $\text{[math]}$ $\text{[math]}$ $a\gg n$ (для чисел со знаком — арифметический) и $\text{[math]}$ $\text{[math]}$ $a\operatorname {\&} (2^{n}-1)$ .

ОбобщенияПравить

Вещественные числаПравить

Если два числа $\text{[math]}$ $\text{[math]}$ $a$ и $\text{[math]}$ $\text{[math]}$ $b$ (отличное от нуля) относятся к множеству вещественных чисел, $\text{[math]}$ $\text{[math]}$ $a$ может быть поделено на $\text{[math]}$ $\text{[math]}$ $b$ без остатка, и при этом частное также является вещественным числом. Если же частное по условию должно быть целым числом, в этом случае остаток будет вещественным числом, то есть может оказаться дробным.

Формально:

если

\text{[math]}

a,b\in \mathbb {R} ,b\neq 0

, то

\text{[math]}

a=bq+r

, где

\text{[math]}

0\leqslant r<|b|

.

Пример

Деление 7,9 на 2,1 с остатком даёт:

\text{[math]}

\left\lfloor {\frac {7{,}9}{2{,}1}}\right\rfloor =3

(неполное частное);

\text{[math]}

7{,}9-3\cdot 2{,}1=1{,}6

(остаток).

Гауссовы целые числаПравить

Гауссово число — это комплексное число вида $\text{[math]}$ $\text{[math]}$ $a+bi$ , где $\text{[math]}$ $\text{[math]}$ $a, b$ — целые числа. Для них можно определить деление с остатком: любое гауссово число $\text{[math]}$ $\text{[math]}$ $u$ можно разделить с остатком на любое ненулевое гауссово число $\text{[math]}$ $\text{[math]}$ $v$ , то есть представить в виде:

\text{[math]}

u=vq+r

,

где частное $\text{[math]}$ $\text{[math]}$ $q$ и остаток $\text{[math]}$ $\text{[math]}$ $r$ — гауссовы числа, причём $\text{[math]}$ $\text{[math]}$ $|r|<|v|.$ Однако, в отличие от целых чисел, остаток от деления определяется неоднозначно. Например, $\text{[math]}$ $\text{[math]}$ $7+2i$ можно разделить на $\text{[math]}$ $\text{[math]}$ $3-i$ тремя способами:

\text{[math]}

7+2i=(3-i)(2+i)+i=(3-i)(1+i)+3=(3-i)(2+2i)+(-1-2i).

МногочленыПравить

При делении с остатком двух многочленов $\text{[math]}$ $\text{[math]}$ $f(x)$ и $\text{[math]}$ $\text{[math]}$ $g(x)$ для однозначности результата вводится условие: степень многочлена-остатка должна быть строго меньше степени делителя:

\text{[math]}

f(x)=q(x)g(x)+r(x)

, причём

\text{[math]}

\deg(r)<\deg(g)

.

Пример: $\text{[math]}$ $\text{[math]}$ ${\frac {2x^{2}+4x+5}{x+1}}=2x+2$ (остаток 3), так как: $\text{[math]}$ $\text{[math]}$ $2x^{2}+4x+5=(x+1)(2x+2)+3$ .

См. такжеПравить

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

↑ ¹ ² Деление // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2.
↑ Потапов М. К., Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций. М.: Наука, 1981, 560 с., С. 9.
↑ ISO/IEC 9899:TC2: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. [This is often called «truncation toward zero».]; в списке изменений 1999→TC1 и TC1→TC2 данное изменение не числится.
↑ «ISO/IEC 14882:2003 : Programming languages -- C++», 5.6.4: International Organization for Standardization, International Electrotechnical Commission, 2003 . «the binary % operator yields the remainder from the division of the first expression by the second. …. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined».
↑ N3242=11-0012 (Working draft), текст совпадает с C99
↑ D language specification (англ.). dlang.org. Дата обращения: 29 октября 2017. Архивировано из оригинала 3 октября 2017 года.
↑ Арнолд, Кен, Гослинг, Дж., Холмс, Д. Язык программирования Java. — 3-е изд. — М., СПб., Киев: Вильямс, 2001. — С. 173—174. — ISBN 5-8459-0215-0.
↑ Стандарт 1973 года: div — division with truncation.
↑ PHP: Arithmetic Operators — Manual (неопр.). Дата обращения: 27 ноября 2014. Архивировано 19 ноября 2014 года.
↑ DIV — Unsigned Divide

[ME-1] ¹ ² Деление // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2.

[2] Потапов М. К., Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций. М.: Наука, 1981, 560 с., С. 9.

[3] ISO/IEC 9899:TC2: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. [This is often called «truncation toward zero».]; в списке изменений 1999→TC1 и TC1→TC2 данное изменение не числится.

[4] «ISO/IEC 14882:2003 : Programming languages -- C++», 5.6.4: International Organization for Standardization, International Electrotechnical Commission, 2003 . «the binary % operator yields the remainder from the division of the first expression by the second. …. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined».

[5] N3242=11-0012 (Working draft), текст совпадает с C99

[6] D language specification (англ.). dlang.org. Дата обращения: 29 октября 2017. Архивировано из оригинала 3 октября 2017 года.

[7] Арнолд, Кен, Гослинг, Дж., Холмс, Д. Язык программирования Java. — 3-е изд. — М., СПб., Киев: Вильямс, 2001. — С. 173—174. — ISBN 5-8459-0215-0.

[8] Стандарт 1973 года: div — division with truncation.

[9] PHP: Arithmetic Operators — Manual (неопр.). Дата обращения: 27 ноября 2014. Архивировано 19 ноября 2014 года.

[10] DIV — Unsigned Divide

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]