Remainder
Encyclopedia
In arithmetic
, the remainder (or residue) is the amount "left over" after the division
of two integer
s 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 number
s, with d being non-zero. The quotient is the integer result (rounded down) of the division of a by d. The remainder must also be an integer.
s, 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.
When defined this way, there are two possible remainders. For example, the division of −42 by −5 can be expressed as either
as is usual for mathematicians, or
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 r1, and the negative one is r2, then
s, 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 language
s implement this definition—see modulo operation
.
and Pascal
choose the remainder with the same sign as the dividend a. (Before C99, the C language allowed either choice.) Perl
, Python
(only modern versions), 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.
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
, the remainder (or residue) is the amount "left over" after the division
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
of two integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s which cannot be expressed with an integer quotient
Quotient
In mathematics, a quotient is the result of division. For example, when dividing 6 by 3, the quotient is 2, while 6 is called the dividend, and 3 the divisor. The quotient further is expressed as the number of times the divisor divides into the dividend e.g. The quotient of 6 and 2 is also 3.A...
.
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 number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, with d being non-zero. The quotient is the integer result (rounded down) of the division of a by d. The remainder must also be an integer.
The remainder for natural numbers
If a and d are natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, 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
Division algorithm
In mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be specified precisely by a theorem stating that these exist uniquely with given properties. An integer division algorithm is any effective method for producing...
provides a proof of this result and also an algorithm describing how to calculate the remainder.
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, 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 r1, and the negative one is r2, then
- r1 = r2 + d.
The remainder for real numbers
When a and d are real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s, 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 language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s implement this definition—see modulo operation
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
.
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.Quotient and remainder in programming languages
With two choices for the inequality, there are two choices for the remainder, one negative and the other positive. This means that there are also two possible choices for the quotient. In number theory the positive remainder is chosen by convention. But programming languages need not, and different languages have adopted different conventions: C99C99
C99 is a modern dialect of the C programming language. It extends the previous version with new linguistic and library features, and helps implementations make better use of available computer hardware and compiler technology.-History:...
and Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
choose the remainder with the same sign as the dividend a. (Before C99, the C language allowed either choice.) Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
(only modern versions), and Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
choose the remainder with the same sign as the divisor d. Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
and Scheme offer two functions, remainder and modulo; the former agrees in sign with the dividend, and the latter with the divisor.
See also
- Chinese remainder theoremChinese remainder theoremThe Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
- Division algorithmDivision algorithmIn mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be specified precisely by a theorem stating that these exist uniquely with given properties. An integer division algorithm is any effective method for producing...
- Euclidean algorithmEuclidean algorithmIn mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
- Modular arithmeticModular arithmeticIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
- Modulo operationModulo operationIn computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
- Divisibility ruleDivisibility ruleA divisibility rule is a shorthand way of discovering whether a given number is divisible by a fixed divisor without performing the division, usually by examining its digits...