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

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

$a=b\cdot q+r$

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

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

Примеры

• При делении с остатком положительного числа $a=78$ на $b=33$ получаем неполное частное $q=2$ и остаток $r=12$.

Проверка: $78=33\cdot 2+12.$

• При делении с остатком отрицательного числа $a=-78$ на $b=33$ получаем неполное частное $q=-3$ и остаток $r=21$.

Проверка: $-78=33\cdot (-3)+21.$

• При делении с остатком отрицательного числа $a=-9$ на $b=-13$ получаем неполное частное $q=1$ и остаток $r=4$.

Проверка: $-9=(-13)\cdot 1+4.$

• При делении с остатком положительного числа $a=9$ на $b=90$ получаем неполное частное $q=0$ и остаток $r=9$.

Проверка: $9=90\cdot 0+9.$

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

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

Определение

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

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

$q=\lfloor \frac{a}{b}\rfloor ,$ когда $b>0$.

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

$r=a-b\cdot q.$

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

$q=\lceil \frac{a}{b}\rceil ,$ когда $b<0$.

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

Шаблон:Anchor Величина остатка может быть получена бинарной операцией «взятия остатка» от деления $a$ на $b$, обозначаемой Шаблон:Math:

$r=amodb.$

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

$r\equiv a(\mathrm{mod}b),$

однако обратная импликация, вообще говоря, неверна. А именно, это сравнение не подразумевает выполнения неравенства $0⩽r<|b|$, необходимого для того, чтобы $r$ было остатком.

В программировании

Операция вычисления неполного частного и остатка в различных языках программирования

Язык	Неполное частное	Остаток	Знак остатка
ActionScript		%	Делимое
Ada		mod	Делитель
		rem	Делимое
Бейсик	\	MOD	Не определено
Си (ISO 1990)	/	%	Не определено
Си (ISO 1999)	/	%	Делимое
C++ (ISO 2003)	/	%	Не определено
C++ (ISO 2011)	/	%	Делимое
C#	/	%	Делимое
ColdFusion		MOD	Делимое
Common Lisp		mod	Делитель
		rem	Делимое
D	/	%	Делимое
Delphi	div	mod	Делимое
Eiffel	//	\\	Делимое
Erlang	div	rem	Делимое
Euphoria		remainder	Делимое
Microsoft Excel (англ.)	Шаблон:Nobr	MOD()	Делитель
Microsoft Excel (рус.)	ЧАСТНОЕ()	ОСТАТ()
FileMaker	Div()	Mod()	Делитель
Fortran		mod	Делимое
		modulo	Делитель
GML (Game Maker)	div	mod	Делимое
Go	/	%	Делимое
Haskell	div	mod	Делитель
	quot	rem	Делимое
J		|~	Делитель
Java	/	%	Делимое
	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	Делимое
Perl	Нет	%	Делитель
PHP	Нет	%	Делимое
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

Знак остатка

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

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

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

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

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

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

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

При отсутствии команды mod остаток программируется как $a-qb$.

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

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

Обобщения

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

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

Формально:

если $a,b\in ℝ,b\ne 0$, то $a=bq+r$, где $0⩽r<|b|$.

Пример

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

$\lfloor \frac{7,9}{2,1}\rfloor =3$ (неполное частное);

$7,9-3\cdot 2,1=1,6$ (остаток).

Гауссовы целые числа

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

$u=vq+r$,

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

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

Многочлены

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

$f(x)=q(x)g(x)+r(x)$, причём $\mathrm{deg}(r)<\mathrm{deg}(g)$.

Пример

$\frac{2x^2+4x+5}{x+1}=2x+2$ (остаток 3), так как: $2x^2+4x+5=(x+1)(2x+2)+3$.

См. также

• Алгоритм Евклида
• Делимость
• Наибольший общий делитель
• Непрерывная дробь
• Сравнение по модулю