remainder

TheInfoList

OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the remainder is the amount "left over" after performing some computation. In
arithmetic Arithmetic () is an elementary part of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their chang ...
, the remainder is the integer "left over" after dividing one
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
by another to produce an integer
quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division (mathematics), division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to a ...
( integer division). In
algebra Algebra () is one of the areas of mathematics, broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathem ...
of polynomials, the remainder is the polynomial "left over" after dividing one polynomial by another. The ''
modulo operation In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
'' 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." However, the term "remainder" is still used in this sense when a function is approximated by a
series expansion In mathematics, a series expansion is an expansion of a Function (mathematics), function into a Series (mathematics), series, or infinite sum. It is a method for calculating a Function (mathematics), function that cannot be expressed by just ele ...
, where the error expression ("the rest") is referred to as the remainder term.

# Integer division

Given an
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
''a'' and a non-zero integer ''d'', it can be shown that there exist unique integers ''q'' and ''r'', such that and . The number ''q'' is called the ''
quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division (mathematics), division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to a ...
'', while ''r'' is called the ''remainder''. (For a proof of this result, see
Euclidean division In arithmetic Arithmetic () is an elementary part of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantitie ...
. For algorithms describing how to calculate the remainder, see
division algorithm 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. Divis ...
.) The remainder, as defined above, is called the ''least positive remainder'' or simply the ''remainder''. 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''. As with the quotient and remainder, ''k'' and ''s'' are uniquely determined, except in the case where ''d'' = 2''n'' 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''1, and the negative one is ''r''2, then :r1 = ''r''2 + ''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 language A programming language is a system of notation for writing computer program, computer programs. Most programming languages are text-based formal languages, but they may also be visual programming language, graphical. They are a kind of computer ...
s implement this definition (see
modulo operation In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
).

# 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, is not always valid).Pascal ISO 7185:1990
6.7.2.2
* C99 chooses the remainder with the same sign as the dividend ''a''. (Before C99, the C language allowed other choices.) *
Perl Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offi ...
, Python (only modern versions) choose the remainder with the same sign as the divisor ''d''. *
Haskell Haskell () is a General-purpose programming language, general-purpose, static typing, statically-typed, purely functional programming, purely functional programming language with type inference and lazy evaluation. Designed for teaching, resear ...
and Scheme offer two functions, ''remainder'' and ''modulo'' – Ada,
Common Lisp Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived ...
and
PL/I PL/I (Programming Language One, pronounced and sometimes written PL/1) is a Procedural programming, procedural, imperative programming, imperative computer programming language developed and published by IBM. It is designed for scientific, eng ...
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.

# Polynomial division

Euclidean division of polynomials is very similar to
Euclidean division In arithmetic Arithmetic () is an elementary part of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantitie ...
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 number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...
s), there exist two polynomials ''q''(''x'') (the ''quotient'') and ''r''(''x'') (the ''remainder'') which satisfy: :$a\left(x\right) = b\left(x\right)q\left(x\right) + r\left(x\right)$ where :$\deg\left(r\left(x\right)\right) < \deg\left(b\left(x\right)\right),$ 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. 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'').

*
Chinese remainder theorem 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 thes ...
*
Divisibility rule A divisibility rule is a shorthand and useful way of determining whether a given integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative n ...
* Egyptian multiplication and division *
Euclidean algorithm In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
*
Long division In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu–Arabic numeral system, Hindu-Arabic numerals (Positional notation) that is simple enough to perform by hand. It breaks down a division (mathem ...
*
Modular arithmetic In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
* Polynomial long division * Synthetic division * Ruffini's rule, a special case of synthetic division *
Taylor's theorem In calculus Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study ...

* * * *