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

${\displaystyle a=b\cdot q+r}$

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

Определение

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

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

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

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

${\displaystyle r=a-b\cdot q.}$

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

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

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

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

${\displaystyle r=a{\bmod {b}}.}$

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

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

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

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

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

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

78 mod 33 = 12
78 div 33 = 2

Знак остатка

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

Формально:

если ${\displaystyle a,b\in \mathbb {R} ,b\neq 0}$ , то ${\displaystyle a=bq+r}$ , где ${\displaystyle 0\leqslant r<|b|}$ .

Пример

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

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

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

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

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

${\displaystyle u=vq+r}$ ,

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

${\displaystyle 7+2i=(3-i)(2+i)+i=(3-i)(1+i)+3=(3-i)(2+2i)+(-1-2i).}$

Многочлены

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

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

Пример

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

См. также

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

Примечания