В математике остаток — это сумма , «оставшаяся» после выполнения некоторых вычислений. В арифметике остаток — это целое число, «оставшееся» после деления одного целого числа на другое для получения целого частного ( целочисленное деление ). В алгебре многочленов остаток — это многочлен, «оставшийся» после деления одного многочлена на другой. Операция взятия по модулю — это операция, которая производит такой остаток, если заданы делимое и делитель.
В качестве альтернативы, остаток — это также то, что остается после вычитания одного числа из другого, хотя это более точно называется разностью . Такое использование можно найти в некоторых элементарных учебниках; в разговорной речи оно заменяется выражением «остаток», например, «Верни мне два доллара и оставь себе остальное». [1] Однако термин «остаток» все еще используется в этом смысле, когда функция аппроксимируется с помощью разложения в ряд , где выражение ошибки («остаток») называется остаточным членом .
Если задано целое число a и ненулевое целое число d , можно показать, что существуют уникальные целые числа q и r , такие, что a = qd + r и 0 ≤ r < | d | . Число q называется частным , а r называется остатком .
(Доказательство этого результата см. в разделе Евклидово деление . Алгоритмы, описывающие, как вычислить остаток, см. в разделе Алгоритм деления .)
Остаток, как определено выше, называется наименьшим положительным остатком или просто остатком . [2] Целое число a либо кратно d , либо лежит в интервале между последовательными кратными d , а именно, q⋅d и ( q + 1) d (для положительного q ).
В некоторых случаях удобно выполнять деление так, чтобы a было как можно ближе к целому кратному d , то есть можно записать
В этом случае s называется наименьшим абсолютным остатком . [3] Как и в случае с частным и остатком, k и s определяются однозначно, за исключением случая, когда d = 2 n и s = ± n . Для этого исключения имеем:
В этом случае можно получить уникальный остаток, приняв некоторое соглашение, например, всегда принимая положительное значение s .
При делении 43 на 5 имеем:
так что 3 — это наименьший положительный остаток. У нас также есть это:
и −2 — наименьший абсолютный остаток.
Эти определения справедливы также, если d отрицательно, например, при делении 43 на −5,
и 3 — наименьший положительный остаток, в то время как,
и −2 — наименьший абсолютный остаток.
При делении 42 на 5 имеем:
и поскольку 2 < 5/2, 2 является как наименьшим положительным остатком, так и наименьшим абсолютным остатком.
В этих примерах (отрицательный) наименьший абсолютный остаток получается из наименьшего положительного остатка вычитанием 5, который равен d . Это справедливо в общем случае. При делении на d либо оба остатка положительны и, следовательно, равны, либо они имеют противоположные знаки. Если положительный остаток равен r 1 , а отрицательный — r 2 , то
Когда a и d — числа с плавающей точкой , причем d не равно нулю, a можно разделить на d без остатка, при этом частное будет другим числом с плавающей точкой. Однако, если частное ограничено целым числом, понятие остатка все еще необходимо. Можно доказать, что существует уникальное целое частное q и уникальный остаток с плавающей точкой r, такие, что a = qd + r , где 0 ≤ r < | d |.
Расширение определения остатка для чисел с плавающей точкой, как описано выше, не имеет теоретического значения в математике; однако многие языки программирования реализуют это определение (см. операцию по модулю ).
Хотя в определениях нет никаких трудностей, существуют проблемы с реализацией, которые возникают, когда отрицательные числа участвуют в вычислении остатков. Различные языки программирования приняли различные соглашения. Например:
Евклидово деление многочленов очень похоже на евклидово деление целых чисел и приводит к полиномиальным остаткам. Его существование основано на следующей теореме: даны два одномерных многочлена a ( x ) и b ( x ) (где b ( x ) — ненулевой многочлен), определенных над полем (в частности, действительными или комплексными числами ), существуют два многочлена q ( x ) ( частное ) и r ( x ) ( остаток ), которые удовлетворяют: [7]
где
где "deg(...)" обозначает степень многочлена (степень постоянного многочлена, значение которого всегда равно 0, может быть определена как отрицательная, так что это условие степени всегда будет справедливо, когда это остаток). Более того, q ( x ) и r ( x ) однозначно определяются этими отношениями.
Это отличается от евклидова деления целых чисел тем, что для целых чисел условие степени заменяется ограничениями на остаток r (неотрицательный и меньший делителя, что гарантирует уникальность r ). Сходство между евклидовым делением целых чисел и делением многочленов мотивирует поиск наиболее общей алгебраической ситуации, в которой евклидово деление справедливо. Кольца, для которых существует такая теорема, называются евклидовыми областями , но в этой общности уникальность частного и остатка не гарантируется. [8]
Деление многочленов приводит к результату, известному как теорема о полиномиальном остатке : если многочлен f ( x ) делится на x − k , то остаток равен константе r = f ( k ). [9] [10]
