Remainder

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations where appropriate. (April 2010)

In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient.

The general form of a linear equation can be expressed as a = q × d + r. In this equation, q can be referred to as the quotient and d as the divisor, while r as the remainder. The equation can be transformed to find the remainder as: r = a - q × d. However, a and d must be natural numbers, with d being non-zero. The quotient is the integer result of the division of a by d. The remainder must also be an integer.

Contents 1 The remainder for natural numbers 2 The case of general integers 3 The remainder for real numbers 4 The inequality satisfied by the remainder 5 Quotient and remainder in programming languages 6 See also 7 References

[edit] The remainder for natural numbers

If a and d are natural numbers, with d non-zero, it can be proven that there exist unique integers q and r, such that a = qd + r and 0 ≤ r < d. The number q is called the quotient, while r is called the remainder. The division algorithm provides a proof of this result and also an algorithm describing how to calculate the remainder.

[edit] The case of general integers

If a and d are integers, with d non-zero, then a remainder is an integer r such that a = qd + r for some integer q, and with 0 ≤ |r| < |d|.

When defined this way, there are two possible remainders. For example, the division of −42 by −5 can be expressed as either

−42 = 9×(−5) + 3

as is usual for mathematicians,^{[citation needed]} or

−42 = 8×(−5) + (−2).

So the remainder is then either 3 or −2.

This ambiguity in the value of the remainder can be quite serious computationally; for mission critical computing systems, the wrong choice can lead to dangerous consequences. In the case above, the negative remainder is obtained from the positive one just by subtracting 5, which is d. This holds in general. When dividing by d, if the positive remainder is r₁, and the negative one is r₂, then

r₁ = r₂ + d.

[edit] The remainder for real numbers

When a and d are real numbers, with d non-zero, a can be divided by d without remainder, with the quotient being another real 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 real remainder r such that a=qd+r with 0≤r < |d|. As in the case of division of integers, the remainder could be required to be negative, that is, -|d| < r ≤ 0.

Extending the definition of remainder for real numbers as described above is not of theoretical importance in mathematics; however, many programming languages implement this definition—see modulo operation.

[edit] The inequality satisfied by the remainder

The way remainder was defined, in addition to the equality a=qd+r an inequality was also imposed, which was either 0≤ r < |d| or -|d| < r ≤ 0. Such an inequality is necessary in order for the remainder to be unique—that is, for it to be well-defined. The choice of such an inequality is somewhat arbitrary. Any condition of the form x < r ≤ x+|d| (or x ≤ r < x+|d|), where x is a constant, is enough to guarantee the uniqueness of the remainder.

[edit] Quotient and remainder in programming languages

With two choices for the inequality, there are two possible choices for the remainder, one negative and the other positive. This means that there are also two possible choices for the quotient. Usually, in number theory, we always choose the positive remainder.^{[citation needed]} But programming languages need not, and different languages have adopted different conventions: C99 and Pascal choose the remainder with the same sign as the dividend a. (Before C99, the C language allowed either choice.) Perl, Python, and Common Lisp choose the remainder with the same sign as the divisor d. Haskell and Scheme offer two functions, remainder and modulo; the former agrees in sign with the dividend, and the latter with the divisor.

[edit] See also

• Chinese remainder theorem
• Division algorithm
• Euclidean algorithm
• Modular arithmetic
• Modulo operation

[edit] References

• Davenport, Harold (1999). The higher arithmetic: an introduction to the theory of numbers. Cambridge, UK: Cambridge University Press. p. 25. ISBN 0-521-63446-6. 
• Zuckerman, Martin M. Arithmetic: A Straightforward Approach. Lanham, Md: Rowman & Littlefield Publishers, Inc. ISBN 0-912675-07-1.