WikiSort.ru - Не сортированное

Деление 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], либо теория сразу формулируется для целых чисел, как указано выше.

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

Обобщения

См. также

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

Примечания