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

---

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

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

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

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

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

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

---