Remainder

Last updated April 16, 2024

In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient (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 subtracting one number from another, although this is more precisely called the 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."^[1] However, the term "remainder" is still used in this sense when a 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 $a = qd + r$ and $0 \leq r < | 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.^[2] The integer a is either a multiple of d, or lies in the interval between consecutive multiples of d, namely, q⋅d and (q + 1)d (for positive q).

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 = k⋅d + s, with |s| ≤ |d/2| for some integer k.

In this case, s is called the least absolute remainder.^[3] As with the quotient and remainder, k and s are uniquely determined, except in the case where d = 2n and s = ± n. For this exception, we have:

a = k⋅d + 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 −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₁, and the negative one is r₂, then

r₁ = r₂ + d.

For floating-point numbers

When a and d are floating-point numbers, 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 a = qd + r with 0 ≤ r < |d|.

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

In programming languages

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 chooses the result of the mod operation positive, but does not allow d to be negative or zero (so, a = (a div d ) × d + a mod d is not always valid).^[4]
C99 chooses the remainder with the same sign as the dividend a.^[5] (Before C99, the C language allowed other choices.)
Perl, Python (only modern versions) choose the remainder with the same sign as the divisor d.^[6]
Scheme offer two functions, remainder and modulo – 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 also have mod and rem, but mod uses the sign of the divisor and rem uses the sign of the dividend.

Polynomial division

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 reals or complex numbers), there exist two polynomials q(x) (the quotient) and r(x) (the remainder) which satisfy:^[7]

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 domains, but in this generality, uniqueness of the quotient and remainder is not guaranteed.^[8]

Polynomial division leads to a result known as the polynomial remainder theorem: If a polynomial f(x) is divided by x − k, the remainder is the constant r = f(k).^[9]^[10]

Notes

↑ Smith 1958 , p. 97
↑ Ore 1988 , p. 30. But if the remainder is 0, it is not positive, even though it is called a "positive remainder".
↑ Ore 1988 , p. 32
↑ Pascal ISO 7185:1990 6.7.2.2
↑ "6.5.5 Multiplicative operators". C99 specification (ISO/IEC 9899:TC2) (PDF) (Report). 6 May 2005. Retrieved 2018-08-16.
↑ "Built-in Functions — Python 3.10.7 documentation". 9 September 2022. Retrieved 2022-09-10.
↑ Larson & Hostetler 2007 , p. 154
↑ Rotman 2006 , p. 267
↑ Larson & Hostetler 2007 , p. 157
↑ Weisstein, Eric W. "Polynomial Remainder Theorem". mathworld.wolfram.com. Retrieved 2020-08-27.

Related Research Articles

In mathematics, Bézout's identity, named after Étienne Bézout who proved it for polynomials, is the following theorem:

In number theory, two integers $a$ and $b$ are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides $a$ does not divide $b$ , and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also $a$ is prime to $b$ or $a$ is coprime with $b$ .

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, more specifically in ring theory, a Euclidean domain is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them. Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $. For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4 .$

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

<span class="mw-page-title-main">Division (mathematics)</span> Arithmetic operation

Division is one of the four basic operations of arithmetic. The other operations are addition, subtraction, and multiplication. What is being divided is called the dividend, which is divided by the divisor, and the result is called the quotient.

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, because it separates an otherwise complex division problem into smaller ones. Sometimes using a shorthand version called synthetic division is faster, with less writing and fewer calculations. Another abbreviated method is polynomial short division.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer by another, in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor. A fundamental property is that the quotient and the remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder. The methods of computation are called integer division algorithms, the best known of which being long division.

In algebra, the polynomial remainder theorem or little Bézout's theorem is an application of Euclidean division of polynomials. It states that, for every number $any polynomial is the sum of and the product by of a polynomial in of degree less than the degree of In particular, is the remainder of the Euclidean division of by and is a divisor of if and only if a property known as the factor theorem.$

In mathematics, the Sturm sequence of a univariate polynomial $p$ is a sequence of polynomials associated with $p$ and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of $p$ located in an interval in terms of the number of changes of signs of the values of the Sturm sequence at the bounds of the interval. Applied to the interval of all the real numbers, it gives the total number of real roots of $p$ .

In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another.

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.

In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

In arithmetic, short division is a division algorithm which breaks down a division problem into a series of easier steps. It is an abbreviated form of long division — whereby the products are omitted and the partial remainders are notated as superscripts.

References

Larson, Ron; Hostetler, Robert (2007), Precalculus:A Concise Course , Houghton Mifflin, ISBN 978-0-618-62719-6
Ore, Oystein (1988) [1948], Number Theory and Its History , Dover, ISBN 978-0-486-65620-5
Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8
Smith, David Eugene (1958) [1925], History of Mathematics, Volume 2, New York: Dover, ISBN 0486204308