остаток

В школьной арифметике под термином «остаток» понимают невырожденную часть при делении целых чисел: при делении целого числа a на ненулевое целое b получают частное q и остаток r, связанные равенством $a = bq + r$ и удовлетворяющие ограничению $0 \le r < |b|$. Это утверждение — стандартная формулировка теоремы о делении с остатком (иногда называют алгоритмом деления) и гарантирует существование и единственность таких q и r для заданных a и b.

Остаток тесно связан с понятием сравнения по модулю: любой целый a сопоставляется своему классу вычетов по модулю b, и в этом смысле остаток — канонический представитель класса вычетов, так что $a \equiv r \pmod{b}$. Практически часто используется запись через операцию «mod»: остаток можно определить через целую часть частного и функцию пол: $a \bmod n = a - n\left\lfloor\dfrac{a}{n}\right\rfloor$. В компьютерных реализациях и задачах теории чисел остаток служит основной операцией для определения парности, цикличности (например, часовое исчисление), вычисления контрольных сумм и в криптографии.

Важно помнить про соглашение по знакам: в школьной практике обычно принимают остаток неотрицательным и строго меньшим по модулю делителя, что отражено в ограничении $0 \le r < |b|$. При работе с отрицательными делимыми бывают иные соглашения (например, знак остатка может совпадать со знаком делимого), поэтому при решении задач полезно явно уточнять выбранную конвенцию. Характерные свойства остатков — аддитивность и мультипликативность по модулю в форме вычетов — лежат в основе китайской теоремы об остатках и методов вычисления больших степеней по модулю.