Division with remainder

The remainder division or the division algorithm is a mathematical theorem from algebra and number theory . It states that there are two numbers and clearly definite numbers and for which ${\ displaystyle n}$${\ displaystyle m \ neq 0}$${\ displaystyle a}$${\ displaystyle b}$

${\ displaystyle n = m \ cdot a + b \ ,, \ quad 0 \ leq b <| m |}$

applies. The numbers and can be determined by division in writing . ${\ displaystyle a}$${\ displaystyle b}$

Division with remainder is also defined for polynomials . The most general mathematical structure in which there is division by remainder is the Euclidean ring .

Natural numbers

If two natural numbers , the dividend and the divisor (not equal to 0), are to be divided with a remainder, so if ${\ displaystyle a}$${\ displaystyle b}$

${\ displaystyle a: b}$

is to be calculated, you are asked how you can represent the number as a multiple of and a "small remainder": ${\ displaystyle a}$${\ displaystyle b}$

${\ displaystyle a = b \ cdot c + r}$

Here is the so-called integer quotient and the rest. The crucial constraint is that a number is in. This is clearly determined. ${\ displaystyle c}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle \ {0,1, \ dotsc, b-1 \}}$${\ displaystyle r}$

The remainder is thus the difference between the dividend and the largest multiple of the divisor, which is at most as large as the dividend. A remainder not equal to 0 therefore results precisely when the dividend is not a multiple of the divisor. It is also said: The dividend is not through the divisor is divisible , so is a radical left.

If the divisor is fixed, one speaks, for example, of the nine remainder of a number, i.e. the remainder that results from dividing this number by nine.

Examples

• 7: 3 = 2, remainder 1, because 7 = 3 × 2 + 1 ("three fits twice into seven and there is one left" - the remainder is one)
• 2: 3 = 0, remainder 2, since 2 = 3 × 0 + 2
• 3: 3 = 1, remainder 0, since 3 = 3 × 1 + 0

The notation used here is used in elementary schools and partly also in secondary schools, but is problematic from a technical point of view and not entirely correct, as it violates the transitivity of the equivalence relation "=". With this notation you get z. B. for the different quotients 7: 3 and 9: 4 apparently the same result (2, remainder 1). Often the notation 7: 3 = 2 + 1: 3 is preferred.

Determining the remainder for special dividers

Often you can see the rest of the decimal notation:

• When dividing by 2: The remainder is 1 if the last digit is odd, or 0 if the last digit is even.
• When dividing by 3: The remainder is equal to the remainder that the iterated checksum leaves when dividing by 3.
• When dividing by 5: the remainder is equal to the remainder that the last digit leaves when dividing by 5.
• When dividing by 9: The remainder is equal to the remainder that the iterated checksum leaves when dividing by 9.
• When dividing by 10: The remainder is the last digit.

Similar, if somewhat more complicated rules exist for a number of other factors.

Whole numbers

If it is a negative integer , then there are no natural numbers between 0 and that could be used for the remainder . Among the many possibilities, the following three are the most interesting: ${\ displaystyle b}$${\ displaystyle b-1}$${\ displaystyle r}$

1. Instead, you can ask that the remainder be between 0 and (the amount of minus 1).${\ displaystyle r}$${\ displaystyle | b | -1}$${\ displaystyle b}$
2. Alternatively, one can also require that the remainder lies between and 0, i.e. has the same sign as${\ displaystyle r}$${\ displaystyle b + 1}$${\ displaystyle b.}$
3. A third option is to choose the remainder with the smallest amount . This variant provides the best approximation for${\ displaystyle r}$${\ displaystyle a = b \ cdot c + r}$${\ displaystyle b \ cdot c}$${\ displaystyle a.}$

example

If you divide negative numbers, you get the following picture:

 7 :  3 =  2 Rest  1
−7 :  3 = −2 Rest −1


Transferred to negative factors, it follows:

 7 : −3 = −2 Rest  1
−7 : −3 =  2 Rest −1


(Here, for the selection of quotient and remainder, it is initially done as if there were no signs, they are, so to speak, "added again after the actual calculation"). A value is always determined as the integer quotient, the amount of which is not greater than the amount of the ( rational ) quotient. The remainder and its sign follow from the choice of the quotient.

How big the rest of a division turns out is actually a matter of taste. Because everyone is free to share only a part of a given size , he simply declares the rest to be the “rest”. If we also allow "debts" to be incurred, all of the following results are permissible:

 7 :  3 =  1 Rest  4
7 :  3 =  2 Rest  1
7 :  3 =  3 Rest −2


or

−7 :  3 = −1 Rest −4
−7 :  3 = −2 Rest −1
−7 :  3 = −3 Rest  2


For normalization, the convention is used in mathematics to obtain the signs of the remainders from those of the divisors, as shown in the following examples:

 7 :  3 =  2 Rest  1
−7 :  3 = −3 Rest  2
7 : −3 = −3 Rest −2
−7 : −3 =  2 Rest −1


The affiliation of a number to a residual class can be read directly from the remainder.

Implementation in computer systems

DIV and MOD commands or operators (for whole number division and remainder) are implemented in most programming languages (and even in CPUs ) in accordance with this everyday approach.

Some programming languages ​​and computer algebra systems accommodate this variety of conventions by providing two modulo or remainder operators. In the example Ada has:

• (A rem B) has the same sign as A and an absolute value smaller than the absolute value of B.
• (A mod B) has the same sign as B and an absolute value less than the absolute value of B.

Modulo

Modulo calculates the remainder of the division divided by . You can define a function that assigns a unique remainder to each pair of numbers . This is called modulo (from Latin modulus, case ablative , i.e.: '(measured) with the (small) measure (of ...)'; see also wikt: modulo ) and mostly abbreviated with mod . ${\ displaystyle b}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle (n, m)}$${\ displaystyle b}$

In many programming languages ​​the function is represented by %( percent signs ) and treated as an operator . Early programming languages ​​did not yet know the operator mod , only the data type of the integer value integer (abbreviated INT); That is why the remainder of the division was calculated according to the formula and then rounded to the integer value because of the calculation inaccuracy at the time when dividing. ${\ displaystyle {\ bigg (} {\ frac {n} {m}} - {\ texttt {INT}} \ left ({\ frac {n} {m}} \ right) {\ bigg)} \ cdot m }$

We consider the function

${\ displaystyle \ operatorname {mod} \ colon \ mathbb {Z} \ times (\ mathbb {Z} \ setminus \ {0 \}) \ to \ mathbb {Z}, \ quad (a, m) \ mapsto a { \ bmod {m}}: = a- \ left \ lfloor {\ frac {a} {m}} \ right \ rfloor \ cdot m.}$
The Gaussian bracket designates the largest integer that is not greater than the number in the Gaussian bracket, i.e., if positive, the whole part without the decimal places. Always applies here ${\ displaystyle \ lfloor \ cdot \ rfloor}$
${\ displaystyle (a + km) {\ bmod {m}} = a {\ bmod {m}}}$ for all ${\ displaystyle k \ in \ mathbb {Z},}$
but in general is
${\ displaystyle (-a) {\ bmod {m}} \ neq - (a {\ bmod {m}}),}$z. B.${\ displaystyle (-2) {\ bmod {3}} = 1 \ neq -2 = - (2 {\ bmod {3}}).}$
Is positive so is for everyone${\ displaystyle m}$${\ displaystyle a {\ bmod {m}} \ geq 0}$${\ displaystyle a.}$

In addition to this "mathematical variant", a similar function is often referred to as modulo, which gives different results for negative arguments and is called the "symmetrical variant":

${\ displaystyle (a {\ bmod {m}}): = on \ cdot (a \, \ operatorname {div} \, m)}$
Here denotes the quotient rounded towards zero , given by , where denotes the sign function. The following applies to this variant ${\ displaystyle a \, \ operatorname {div} \, m}$${\ displaystyle a \, / \, m}$${\ displaystyle a \, \ operatorname {div} \, m = \ operatorname {sgn} (a) \; \ operatorname {sgn} (m) \ left \ lfloor {\ frac {| a |} {| m |} } \ right \ rfloor}$${\ displaystyle \ operatorname {sgn} (x)}$
${\ displaystyle (-a) {\ bmod {m}} = - (a {\ bmod {m}}),}$
but in general
${\ displaystyle (a + km) {\ bmod {m}} \ neq a {\ bmod {m}},}$z. B.${\ displaystyle (1-3) {\ bmod {3}} = (- 2) {\ bmod {3}} = - 2 \ neq 1 = 1 {\ bmod {3}}.}$
${\ displaystyle a {\ bmod {m}}}$always has the same sign as , or it applies .${\ displaystyle a}$${\ displaystyle a {\ bmod {m}} = 0}$

If and , both variants give the same result. The implemented variant is not uniform in programming languages . To use Ruby , Perl , Python , Excel and the computers of Google search , the mathematical variant, whereas C , Java , JavaScript and PHP are using symmetric, which is especially important when porting is. ${\ displaystyle a \ geq 0}$${\ displaystyle m> 0}$

If only the symmetrical variant is available in a language like C (++) or Java, you can get results according to the mathematical variant with:

${\ displaystyle a {\ bmod {b}}}$= ((a % b) + b) % b,

where %the symmetrical modulo operation denotes and the mathematical. ${\ displaystyle \ operatorname {mod}}$

Examples

• ${\ displaystyle 17 {\ bmod {3}} = 2,}$there ("3 fits into 17 five times and there are 2 left" - the rest is 2)${\ displaystyle 17 = 5 \ cdot 3 + 2}$
• ${\ displaystyle 2 {\ bmod {3}} = 2,}$ there ${\ displaystyle 2 = 0 \ cdot 3 + 2}$
• ${\ displaystyle 3 {\ bmod {3}} = 0,}$ there ${\ displaystyle 3 = 1 \ cdot 3 + 0}$
• ${\ displaystyle -8 {\ bmod {6}} = - 8- \ left \ lfloor {\ frac {-8} {6}} \ right \ rfloor \ cdot 6 = -8 - (- 2) \ cdot 6 = -8 + 12 = 4}$

It does not follow from , but only, that and differ by an integral multiple of , i.e.: with . Such an equation can also be written more easily with the help of the congruence relation common in number theory : ${\ displaystyle a {\ bmod {m}} = b {\ bmod {m}}}$ ${\ displaystyle a = b}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle m}$${\ displaystyle a = b + (k \ cdot m)}$${\ displaystyle k \ in \ mathbb {Z}}$

${\ displaystyle a \ equiv b \ mod m}$ or ${\ displaystyle a \ equiv _ {m} b}$

The spelling is also common

${\ displaystyle a = b {\ pmod {m}},}$

both with and without the bracket, and not only where this would be correct without the bracket when viewed as a remainder operator, but also otherwise: ${\ displaystyle 1 = 11 {\ pmod {10}},}$

${\ displaystyle 11 = 1 {\ pmod {10}}}$ or even
${\ displaystyle 11 = 21 {\ pmod {10}}}$

The background here is that one then understands the equivalence class uniquely determined by the representative 1 of the numbers congruent to 1 modulo m as an element of the remainder class ring ; in this sense, the two terms are actually the same as different representatives of the same equivalence class . In practice there is no difference to the use of the congruence symbol. ${\ displaystyle \ mathbb {Z} _ {m}}$

Basic arithmetic modulo a natural number

If the number m is a prime number , the basic arithmetic operations familiar from real numbers can be used with subsequent modulo calculation and a so-called finite field is obtained .

Examples

• Modulo 3: ${\ displaystyle \ left ((2 {\ bmod {3}}) + (2 {\ bmod {3}}) \ right) {\ bmod {3}} = 4 {\ bmod {3}} = 1 {\ bmod {3}}}$
• Modulo 5: ${\ displaystyle \ left ((3 {\ bmod {5}}) \ cdot (3 {\ bmod {5}}) \ right) {\ bmod {5}} = 9 {\ bmod {5}} = 4 { \ bmod {5}}}$

Generalization: Real numbers

If and are real numbers, not equal to 0, then a division with remainder can be defined as follows: The integer quotient and remainder in the half-open interval are those (uniquely determined) numbers that satisfy the equation . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a}$${\ displaystyle c}$${\ displaystyle r}$ ${\ displaystyle [0, | b |)}$${\ displaystyle a = b \ cdot c + r}$

Here, too, there are the alternatives of giving the remainder the same sign as or choosing the remainder with the smallest amount. The latter alternative corresponds to rounding : The division with remainder of by 1 yields an integer and a real number with a magnitude less than or equal to 1/2 that satisfy the equation . The number is the value of rounded to whole numbers . ${\ displaystyle b}$${\ displaystyle a}$${\ displaystyle c}$${\ displaystyle r}$${\ displaystyle a = c + r}$${\ displaystyle c}$${\ displaystyle a}$

It should be noted that the quotient is not taken from the same set (of the real numbers) as the divisor and dividend.

Polynomials

When dividing with the remainder for polynomials , the polynomial from the polynomial ring (via , a commutative ring with ) that appears as a divisor must meet one requirement: The leading coefficient of must be a unit of (in particular, the zero polynomial is not ). Under this condition, for every uniquely determined polynomials with ${\ displaystyle f (X)}$ ${\ displaystyle R [X]}$${\ displaystyle R}$ ${\ displaystyle 1}$${\ displaystyle f (X)}$${\ displaystyle R}$${\ displaystyle f (X)}$${\ displaystyle g (X) \ in R [X]}$${\ displaystyle q (X), r (X) \ in R [X]}$

${\ displaystyle g (X) = q (X) \ cdot f (X) + r (X)}$
${\ displaystyle \ operatorname {deg} (r) <\ operatorname {deg} (f)}$

The zero polynomial is given a smaller degree than any other polynomial, for example . ${\ displaystyle - \ infty}$

example
${\ displaystyle 2X ^ {2} + 4X + 5 = (2X + 2) (X + 1) +3 \ in \ mathbb {R} [X]}$

The polynomials and can be determined by polynomial division . ${\ displaystyle q (X)}$${\ displaystyle r (X)}$

application

programming

Division by remainder (modulo) is used relatively often in programming. The corresponding operator is often called modor in different programming languages %. You can check about whether a given number is even, by performing the following query: . Modulo can also be used if you only want to execute a special program code in a loop every time it is run through the loop. The operator can also be used effectively for many calculations and algorithms. In general, you can use to check whether a number is exactly divisible by another: Only then does the modulo operator return the value 0. Furthermore, you often have to add whole multiples of a number (e.g. 4 bytes) and can use the modulo to calculate how many “ pad bytes ” are still missing. The function calculates the integer quotient and remainder together. ${\ displaystyle x}$if ((x mod 2) == 0)${\ displaystyle x}$moddivMod

example
A clock is programmed and the time has been given as a second value since midnight. Then you can calculate the seconds value mod 3600. If this is equal to 0, you know that a full hour has started. This information can be used to e.g. B. to trigger an acoustic signal (gong every full hour). With the calculation of the seconds value mod 60 you get the seconds since the last full minute, which are often displayed as the last two digits by digital clocks.