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

Деление 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), так как