Остаток

В математике остаток — это сумма , «оставшаяся» после выполнения некоторых вычислений. В арифметике остаток — это целое число, «оставшееся» после деления одного целого числа на другое для получения целого частного ( целочисленное деление ). В алгебре многочленов остаток — это многочлен, «оставшийся» после деления одного многочлена на другой. Операция взятия по модулю — это операция, которая производит такой остаток, если заданы делимое и делитель.

В качестве альтернативы, остаток — это также то, что остается после вычитания одного числа из другого, хотя это более точно называется разностью . Такое использование можно найти в некоторых элементарных учебниках; в разговорной речи оно заменяется выражением «остаток», например, «Верни мне два доллара и оставь себе остальное». ^[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 , то есть можно записать

a = k⋅d + s , где | s | ≤ | d /2| для некоторого целого числа k .

В этом случае s называется наименьшим абсолютным остатком . ^[3] Как и в случае с частным и остатком, k и s определяются однозначно, за исключением случая, когда d = 2 n и s = ± n . Для этого исключения имеем:

а = к⋅д + н = ( к + 1) д − н .

В этом случае можно получить уникальный остаток, приняв некоторое соглашение, например, всегда принимая положительное значение s .

При делении 43 на 5 имеем:

43 = 8 × 5 + 3,

так что 3 — это наименьший положительный остаток. У нас также есть это:

43 = 9 × 5 − 2,

и −2 — наименьший абсолютный остаток.

Эти определения справедливы также, если d отрицательно, например, при делении 43 на −5,

43 = (−8) × (−5) + 3,

и 3 — наименьший положительный остаток, в то время как,

43 = (−9) × (−5) + (−2)

и −2 — наименьший абсолютный остаток.

При делении 42 на 5 имеем:

42 = 8 × 5 + 2,

и поскольку 2 < 5/2, 2 является как наименьшим положительным остатком, так и наименьшим абсолютным остатком.

В этих примерах (отрицательный) наименьший абсолютный остаток получается из наименьшего положительного остатка вычитанием 5, который равен d . Это справедливо в общем случае. При делении на d либо оба остатка положительны и, следовательно, равны, либо они имеют противоположные знаки. Если положительный остаток равен r ₁ , а отрицательный — r ₂ , то

г ₁ = г ₂ + д .

Когда a и d — числа с плавающей точкой , причем d не равно нулю, a можно разделить на d без остатка, при этом частное будет другим числом с плавающей точкой. Однако, если частное ограничено целым числом, понятие остатка все еще необходимо. Можно доказать, что существует уникальное целое частное q и уникальный остаток с плавающей точкой r, такие, что a  =  qd  +  r , где 0 ≤  r  < | d |.

Расширение определения остатка для чисел с плавающей точкой, как описано выше, не имеет теоретического значения в математике; однако многие языки программирования реализуют это определение (см. операцию по модулю ).

Хотя в определениях нет никаких трудностей, существуют проблемы с реализацией, которые возникают, когда отрицательные числа участвуют в вычислении остатков. Различные языки программирования приняли различные соглашения. Например:

• Паскаль выбирает результат операции mod положительным, но не позволяет d быть отрицательным или нулевым (поэтому a = ( a div d ) × d + a mod d не всегда допустимо). ^[4]
• C99 выбирает остаток с тем же знаком, что и делимое a . ^[5] (До C99 язык C допускал другие варианты.)
• Perl , Python (только современные версии) выбирают остаток с тем же знаком, что и делитель d . ^[6]
• Scheme предлагает две функции, остаток и модуль – в Ada и PL/I есть mod и rem , а в Fortran – mod и modulo ; в каждом случае первая совпадает по знаку с делимым, а вторая – с делителем. Common Lisp и Haskell также имеют mod и rem , но mod использует знак делителя, а rem использует знак делимого.

Евклидово деление многочленов очень похоже на евклидово деление целых чисел и приводит к полиномиальным остаткам. Его существование основано на следующей теореме: даны два одномерных многочлена a ( x ) и b ( x ) (где b ( x ) — ненулевой многочлен), определенных над полем (в частности, действительными или комплексными числами ), существуют два многочлена q ( x ) ( частное ) и r ( x ) ( остаток ), которые удовлетворяют: ^[7]

${\displaystyle а(х)=b(х)q(х)+r(х)}$

где

${\displaystyle \deg(r(x))<\deg(b(x)),}$

где "deg(...)" обозначает степень многочлена (степень постоянного многочлена, значение которого всегда равно 0, может быть определена как отрицательная, так что это условие степени всегда будет справедливо, когда это остаток). Более того, q ( x ) и r ( x ) однозначно определяются этими отношениями.

Это отличается от евклидова деления целых чисел тем, что для целых чисел условие степени заменяется ограничениями на остаток r (неотрицательный и меньший делителя, что гарантирует уникальность r ). Сходство между евклидовым делением целых чисел и делением многочленов мотивирует поиск наиболее общей алгебраической ситуации, в которой евклидово деление справедливо. Кольца, для которых существует такая теорема, называются евклидовыми областями , но в этой общности уникальность частного и остатка не гарантируется. ^[8]

Деление многочленов приводит к результату, известному как теорема о полиномиальном остатке : если многочлен f ( x ) делится на x − k , то остаток равен константе r = f ( k ). ^{[9] [10]}

• Ларсон, Рон; Хостетлер, Роберт (2007), Precalculus:A Concise Course , Houghton Mifflin, ISBN 978-0-618-62719-6
• Оре, Эйстейн (1988) [1948], Теория чисел и ее история , Довер, ISBN 978-0-486-65620-5
• Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Prentice-Hall, ISBN 978-0-13-186267-8
• Смит, Дэвид Юджин (1958) [1925], История математики, том 2 , Нью-Йорк: Довер, ISBN 0486204308

• Дэвенпорт, Гарольд (1999). Высшая арифметика: введение в теорию чисел . Кембридж, Великобритания: Cambridge University Press. стр. 25. ISBN 0-521-63446-6.
• Katz, Victor, ред. (2007). Математика Египта, Месопотамии, Китая, Индии и ислама: справочник . Принстон: Princeton University Press. ISBN 9780691114859.
• Шварцман, Стивен (1994). "остаток (существительное)" . Слова математики: этимологический словарь математических терминов, используемых в английском языке . Вашингтон: Математическая ассоциация Америки. ISBN 9780883855119.
• Цукерман, Мартин М. (декабрь 1998 г.). Арифметика: Прямой подход . Ланхэм, Мэриленд: Rowman & Littlefield Publishers, Inc. ISBN 0-912675-07-1.