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

Деление c остатком — арифметическая операция, играющая большую роль в арифметике, теории чисел, алгебре и криптографии. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом^[1]. Пусть ${\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}$, то есть деление выполняется нацело.

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

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

Для вычисления неполного частного от деления ${\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}$.

Величина остатка может быть получена бинарной операцией «взятия остатка» от деления ${\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 на любой другой регистр или число из памяти^[10]. Неполное частное и остаток выходят по первому варианту — округляют к нулю.

Неполное частное можно вычислить через деление и взятие целой части: ${\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}$.

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