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

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

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


Примеры: 

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



  Проверка: 78=332+12.


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



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


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

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

Определение


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

q=ab,
  где полускобки обозначают взятие целой части. Значение неполного частного q позволяет вычислить значение остатка r по формуле:

r=abq.

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


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

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

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

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


ЯзыкНеполное
частноеОстатокЗнак остатка
ActionScript\texttt
Ada\textttmodДелитель
\textttremДелимое
ASP\textttModНе определено
Бейсик\texttt\{\textttMODНе определено
Си (ISO 1990)\texttt/\texttt
Си (ISO 1999)\texttt/\texttt
C++ (ISO 2003)\texttt/\texttt
C++ (ISO 2011)\texttt/\texttt
C\#\texttt/\texttt
ColdFusion\textttMODДелимое
Common Lisp\textttmodДелитель
\textttremДелимое
D\textttfmodДелимое
Delphi\textttdiv\textttmodДелимое
Eiffel\texttt//\texttt\{\{Делимое
Erlang\textttdiv\textttremДелимое
Euphoria\textttremainderДелимое
Microsoft Excel (англ.)\textttMODДелитель
Microsoft Excel (рус.)\textttЧАСТНОЕ\textttОСТАТ
FileMaker\textttDiv\textttModДелитель
Fortran\textttmodДелимое
\textttmoduloДелитель
GML (Game Maker)\textttdiv\textttmodДелимое
Go\texttt/\texttt
Haskell\textttdiv\textttmodДелитель
\textttquot\textttremДелимое
J\texttt\textlessnowiki\textgreater\textasciitilde\textless/nowiki\textgreaterДелитель
Java\texttt/\texttt
\textttMath.floorDiv\textttMath.floorModДелитель (1.8+)
JavaScript\texttt
Lua\texttt
Mathematica\textttModДелитель
MATLAB\textttidivide(?, ?, 'floor')\textttmodДелитель
\textttidivide\textttremДелимое
MySQL\textttDIV\textttMOD
\texttt
Oberon\textttDIV\textttMOD+, если делитель \textgreater0
Objective Caml\textttmodНе определено
Pascal\textttdiv\textttmodДелимое
PerlНет\texttt
PHPНет\texttt
PL/I\textttmodДелитель (ANSI PL/I)
Prolog (ISO 1995)\textttmodДелитель
PureBasic\texttt/\textttMod
\texttt
Python\texttt//\texttt
QBasic\texttt\{\textttMODДелимое
R\texttt
RPG\texttt
Ruby\texttt
Scheme\textttmoduloДелитель
SenseTalk\textttmoduloДелитель
\textttremДелимое
Tcl\texttt
Verilog (2001)\texttt
VHDL\textttmodДелитель
\textttremДелимое
Visual Basic\texttt\{\textttModДелимое

 Нахождение остатка от деления часто используется в компьютерной технике и телекоммуникационном оборудовании для создания контрольных чисел и получении случайных чисел в ограниченном диапазоне, например в конгруэнтном генераторе случайных чисел.
 Обозначения операции взятия остатка в различных языках программирования представлены в таблице справа. Например, в Паскале операция \textttmod вычисляет остаток от деления, а операция \textttdiv осуществляет целочисленное деление, при котором остаток от деления отбрасывается:
 \beginShaded \beginHighlighting[] \DecValTok78 \KeywordTokmod \DecValTok33 \NormalTok= \DecValTok12 \DecValTok78 \KeywordTokdiv \DecValTok33 \NormalTok= \DecValTok2 \endHighlighting \endShaded

Знак остатка


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

  • Знак остатка совпадает со знаком делимого: неполное частное округляет к нулю.
  • Знак остатка совпадает со знаком делителя: неполное частное округляет к −∞.

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

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

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


 Неполное частное можно вычислить через деление и взятие целой части: q=[ab] ([x], в зависимости от задачи, может быть «полом» или усечением). Однако деление здесь получается дробное, которое намного медленнее целого. Такой алгоритм используется в языках, в которых нет целых типов (отдельные электронные таблицы, программируемые калькуляторы и математические программы), а также в скриптовых языках, в которых издержки интерпретации намного превышают издержки дробной арифметики (Perl, PHP).
 При отсутствии команды \textttmod остаток программируется как aqb.
 Если b положительно, а знак r совпадает со знаком делимого, не определён или неизвестен, для нахождения минимального неотрицательного остатка можно воспользоваться формулой r=(b+(amodb))modb.

Обобщения


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


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

  если a,bR,b0, то a=bq+r, где 0r<|b|


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

7,92,1=3 (неполное частное)
7,932,1=1,6 (остаток)

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


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

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

7+2i=(3i)(2+i)+i=(3i)(1+i)+3=(3i)(2+2i)+(12i)

Многочлены


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

f(x)=q(x)g(x)+r(x), причём deg(r)<deg(g).


Пример:  2x2+4x+5x+1=2x+2 (остаток 3), так как