View source for Remainder

{{Short description|Amount left over after computation}}
{{Other uses}}
{{use dmy dates|cs1-dates=ly|date=February 2024}}

In [[mathematics]], the '''remainder''' is the amount "left over" after performing some computation. In [[arithmetic]], the remainder is the integer "left over" after [[division (mathematics)|dividing]] one [[integer]] by another to produce an integer [[quotient]] ([[Euclidean division|integer division]]). In [[algebra]] of polynomials, the remainder is the polynomial "left over" after dividing one polynomial by another. The ''[[modulo operation]]'' is the operation that produces such a remainder when given a dividend and divisor.

Alternatively, a remainder is also what is left after [[subtraction|subtracting]] one number from another, although this is more precisely called the ''[[Difference (mathematics)|difference]]''. This usage can be found in some elementary textbooks; colloquially it is replaced by the expression "the rest" as in "Give me two dollars back and keep the rest."<ref>{{harvnb|Smith|1958|p=97}}</ref> However, the term "remainder" is still used in this sense when a [[function (mathematics)|function]] is approximated by a [[series expansion]], where the error expression ("the rest") is referred to as the [[remainder term]].

== Integer division ==

Given an [[integer]] ''a'' and a non-zero integer ''d'', it can be shown that there exist unique integers ''q'' and ''r'', such that {{nowrap|1=''a'' = ''qd'' + ''r''}} and {{nowrap|1=0 ≤ ''r'' < {{abs|''d''}}}}. The number ''q'' is called the ''[[quotient]]'', while ''r'' is called the ''remainder''.

(For a proof of this result, see ''[[Euclidean division]]''. For algorithms describing how to calculate the remainder, see ''[[Division algorithm]]''.)

The remainder, as defined above, is called the ''least positive remainder'' or simply the ''remainder''.<ref>{{harvnb|Ore|1988|p=30}}. But if the remainder is 0, it is not positive, even though it is called a "positive remainder".</ref>

In some occasions, it is convenient to carry out the division so that ''a'' is as close to an integral multiple of ''d'' as possible, that is, we can write 
: ''a'' = ''kd'' + ''s'', with {{abs|''s''}} ≤ {{abs|''d''/2}} for some integer ''k''.
In this case, ''s'' is called the ''least absolute remainder''.<ref>{{harvnb|Ore|1988|p=32}}</ref> As with the quotient and remainder, ''k'' and ''s'' are uniquely determined, except in the case where {{nowrap|1=''d'' = 2''n''}} and {{nowrap|1=''s'' = ±''n''}}. For this exception, we have:
: ''a'' = ''kd'' + ''n'' = (''k'' + 1)''d'' − ''n''.
A unique remainder can be obtained in this case by some convention—such as always taking the positive value of ''s''.

=== Examples ===
In the division of 43 by 5, we have:
: 43 = 8 × 5 + 3,
so 3 is the least positive remainder. We also have that:
: 43 = 9 × 5 − 2,
and −2 is the least absolute remainder.

These definitions are also valid if ''d'' is negative, for example, in the division of 43 by −5,
: 43 = (−8) × (−5) + 3,
and 3 is the least positive remainder, while,
: 43 = (−9) × (−5) + (−2)
and &minus;2 is the least absolute remainder.

In the division of 42 by 5, we have:
: 42 = 8 × 5 + 2,
and since 2 < 5/2, 2 is both the least positive remainder and the least absolute remainder.

In these examples, the (negative) least absolute remainder is obtained from the least positive remainder by subtracting 5, which is ''d''. This holds in general. When dividing by ''d'', either both remainders are positive and therefore equal, or they have opposite signs. If the positive remainder is ''r''<sub>1</sub>, and the negative one is ''r''<sub>2</sub>, then
: ''r''<sub>1</sub> = ''r''<sub>2</sub> + ''d''.

== For floating-point numbers ==

When ''a'' and ''d'' are [[floating-point number]]s, with ''d'' non-zero, ''a'' can be divided by ''d'' without remainder, with the quotient being another floating-point number. If the quotient is constrained to being an integer, however, the concept of remainder is still necessary. It can be proved that there exists a unique integer quotient ''q'' and a unique floating-point remainder ''r'' such that {{nowrap|1=''a'' = ''qd'' + ''r''}} with {{nowrap|0 ≤ ''r'' < {{abs|''d''}}}}.

Extending the definition of remainder for floating-point numbers, as described above, is not of theoretical importance in mathematics; however, many [[programming language]]s implement this definition (see ''[[Modulo operation]]'').

== In programming languages ==
{{Main|Modulo operation}}

While there are no difficulties inherent in the definitions, there are implementation issues that arise when negative numbers are involved in calculating remainders. Different programming languages have adopted different conventions. For example:
* [[Pascal (programming language)|Pascal]] chooses the result of the ''mod'' operation positive, but does not allow ''d'' to be negative or zero (so, {{nowrap|1=''a'' = (''a'' div ''d'' ) × ''d'' + ''a'' mod ''d''}} is not always valid).<ref name="iso/iec 7185:1990 6.7.2.2">[http://pascal-central.com/iso7185.html Pascal ISO 7185:1990] 6.7.2.2</ref>
* [[C99]] chooses the remainder with the same sign as the dividend ''a''.<ref>{{cite report |title=C99 specification (ISO/IEC 9899:TC2) |url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf |access-date=16 August 2018 |section=6.5.5 Multiplicative operators |date=2005-05-06}}</ref> (Before C99, the C language allowed other choices.)
* [[Perl]], [[Python (programming language)|Python]] (only modern versions) choose the remainder with the same sign as the divisor ''d''.<ref>{{cite web |title=Built-in Functions – Python 3.10.7 documentation |url=https://docs.python.org/3.10/library/functions.html#divmod |access-date=10 September 2022 |date=2022-09-09}}</ref>
* [[Scheme (programming language)|Scheme]] offer two functions, ''remainder'' and ''modulo'' – [[Ada (programming language)|Ada]] and [[PL/I]] have ''mod'' and ''rem'', while [[Fortran]] has ''mod'' and ''modulo''; in each case, the former agrees in sign with the dividend, and the latter with the divisor. [[Common Lisp]] and [[Haskell (programming language)|Haskell]] also have ''mod'' and ''rem'', but ''mod'' uses the sign of the divisor and ''rem'' uses the sign of the dividend.

== Polynomial division ==
{{main|Euclidean division of polynomials}}

Euclidean division of polynomials is very similar to [[Euclidean division]] of integers and leads to polynomial remainders. Its existence is based on the following theorem: Given two univariate polynomials ''a''(''x'') and ''b''(''x'') (where ''b''(''x'') is a non-zero polynomial) defined over a field (in particular, the [[Real number|reals]] or [[complex number]]s), there exist two polynomials ''q''(''x'') (the ''quotient'') and ''r''(''x'') (the ''remainder'') which satisfy:<ref>{{harvnb|Larson|Hostetler|2007|p=154}}</ref>
: ''a''(''x'') = ''b''(''x'')''q''(''x'') + ''r''(''x'')
where
: deg(''r''(''x'')) < deg(''b''(''x'')),
where "deg(...)" denotes the degree of the polynomial (the degree of the constant polynomial whose value is always 0 can be defined to be negative, so that this degree condition will always be valid when this is the remainder). Moreover, ''q''(''x'') and ''r''(''x'') are uniquely determined by these relations.

This differs from the Euclidean division of integers in that, for the integers, the degree condition is replaced by the bounds on the remainder ''r'' (non-negative and less than the divisor, which insures that ''r'' is unique.) The similarity between Euclidean division for integers and that for polynomials motivates the search for the most general algebraic setting in which Euclidean division is valid. The rings for which such a theorem exists are called [[Euclidean domain]]s, but in this generality, uniqueness of the quotient and remainder is not guaranteed.<ref>{{harvnb|Rotman|2006|p=267}}</ref>

Polynomial division leads to a result known as the [[polynomial remainder theorem]]: If a polynomial ''f''(''x'') is divided by {{nowrap|''x'' − ''k''}}, the remainder is the constant {{nowrap|1=''r'' = ''f''(''k'')}}.<ref>{{harvnb|Larson|Hostetler|2007|p=157}}</ref><ref>{{cite web |last=Weisstein |first=Eric W. |title=Polynomial Remainder Theorem |url=https://mathworld.wolfram.com/PolynomialRemainderTheorem.html |access-date=2020-08-27 |website=mathworld.wolfram.com |language=en}}</ref>

== See also ==
{{div col}}
* [[Chinese remainder theorem]]
* [[Divisibility rule]]
* [[Egyptian multiplication and division]]
* [[Euclidean algorithm]]
* [[Long division]]
* [[Modular arithmetic]]
* [[Polynomial long division]]
* [[Synthetic division]]
* [[Ruffini's rule]], a special case of synthetic division
* [[Taylor's theorem]]
{{div col end}}

== Notes==
{{reflist}}

== References ==
* {{citation |first1=Ron |last1=Larson |first2=Robert |last2=Hostetler |title=Precalculus: A Concise Course |year=2007 |publisher=Houghton Mifflin |isbn=978-0-618-62719-6 |url-access=registration |url=https://archive.org/details/precalculusconci00lars }}
* {{citation |first=Oystein |last=Ore |year=1988 |orig-year=1948 |title=Number Theory and Its History |publisher=Dover |isbn=978-0-486-65620-5 |url-access=registration |url=https://archive.org/details/numbertheoryitsh0000orey }}
* {{citation |first=Joseph J. |last=Rotman |year=2006 |title=A First Course in Abstract Algebra with Applications |edition=3rd |publisher=Prentice-Hall |isbn=978-0-13-186267-8 }}
* {{citation |last=Smith |first=David Eugene |title=History of Mathematics, Volume 2 |year=1958 |orig-year=1925 |publisher=Dover |location=New York |isbn=0486204308 }}

== Further reading ==
* {{cite book |author=Davenport, Harold |title=The higher arithmetic: an introduction to the theory of numbers |publisher=Cambridge University Press |location=Cambridge, UK |year=1999 |page=25 |isbn=0-521-63446-6}}
* {{cite book|editor-last=Katz|editor-first=Victor|title=The mathematics of Egypt, Mesopotamia, China, India, and Islam : a sourcebook|year=2007|publisher=Princeton University Press|location=Princeton|isbn=9780691114859}}
* {{cite encyclopedia|last=Schwartzman|first=Steven|title=remainder (noun)|encyclopedia=The words of mathematics : an etymological dictionary of mathematical terms used in english|year=1994|publisher=Mathematical Association of America|location=Washington|isbn=9780883855119|url-access=registration|url=https://archive.org/details/wordsofmathemati0000schw}}
* {{cite book |author=Zuckerman, Martin M |title=Arithmetic: A Straightforward Approach |date=December 1998 |publisher=Rowman & Littlefield Publishers, Inc |location=Lanham, Md |isbn=0-912675-07-1}}

[[Category:Division (mathematics)]]
[[Category:Number theory]]