Euclidean division

The division with remainder or division algorithm is a mathematical theorem of algebra and number theory. He says that there are two numbers and uniquely determined numbers and, for the

Applies. The numbers and can be determined by long division.

The division with remainder is defined for polynomials. The common mathematical structure in which there is a division with remainder, the Euclidean ring.

• 2.1 Example
• 2.2 implementation in computer systems

• 3.1 Examples

• 4.1 Examples

• 7.1 programming
• 7.2 Other Applications

Natural Numbers

If two natural numbers, the dividend a and divisor b ( equal to 0), to be divided with the rest, so if

Is to be calculated, it is asked how one can represent the number a multiple of b and a "small group":

Here c is the so-called integer quotient and R is the remainder crucial constraint is that r is a number in the. This determines r unique.

The remainder being the difference between the dividend and the largest multiple of the divisor, which is at most as large as the dividend. A remainder is not 0 results thus if and only if the dividend is not a multiple of the divisor. It is also said: The dividend is not divisible by the divisor, which is why a rest remains.

If the divisor is fixed, then one speaks, for example, also from Nine rest a number, so the remainder that results when this number by nine.

Example

• 7:3 = 2, remainder 1, since 7 = 3 × 2 1 (" three fits twice in 7 and it remains one left " - the rest really is one)
• 2:3 = 0, remainder 2 as 2 = 3 × 0 2
• 3:3 = 1, remainder is 0, since 3 = 3 × 1 0

Determination of the rest for special divider

Often you can read the rest of the decimal:

• When divided by 2: the rest is 1 if the last digit is odd, and 0 if the last digit is just
• When divided by 3 the remainder is equal to the remainder, to be the iterated sum of the digits when divided by 3
• Division by 5: the remainder is equal to the residual, to be the last point at division by 5
• When divided by 9: the rest is the iterated sum of the digits or 0 if it is 9
• Division by 10 of the rest is the last digit

Similar, though slightly more complicated rules exist for several other divider.

Integers

B is a negative integer, then there is no natural numbers between 0 and b -1. Instead, the proposal calls for that the rest between 0 and | b | -1 ( the amount of b minus 1). Alternatively, you can also request that the remainder in this case is between b 1 and 0, so that the same sign as b. A third possibility is to choose the smallest amount remaining. This variant provides for a = b · c r the best approximation b · c for a

Example

Dividing negative numbers, it follows according to the everyday experience as follows:

7: 3 = 2 remainder 1 -7: 3 = -2 residual -1 Transferred to negative divider - though little graphic - follows:

7: -3 = -2 residue 1 -7: -3 = 2 remainder -1 (This is first done for the choice of quotient and remainder, as if there was no sign, they are " added actual calculation again " so to speak after ). As a quotient, a value is always determined here, the amount of which is less than or equal to the value of the quotient in the field of rational numbers. The rest and its sign follow from the choice of the quotient.

How great the rest on a division now fails, is a matter of taste, one might think, since everyone is free to share only part of a given size, the remainder he says simply to "rest". Let this also the case that " debt " shall not be made, all subsequent results are for example allowed:

7: 3 = 1 remainder 4   7: 3 = 2 remainder 1   7: 3 = 3 remainder -2 or

-7: 3 = -1 radical -4 -7: 3 = -2 residual -1 -7: 3 = -3 residual 2 For normalization, the convention is used in mathematics, from which to obtain the signs of the remains of the divider, as shown in the following examples:

7: 3 = 2 remainder 1 -7: 3 = -3 residual 2   7: -3 = -3 -2 Rest -7: -3 = 2 remainder -1 Here, the membership of a number can be read to a residue class right on the rest.

Implementation in computer systems

Note that DIV and MOD commands ( for integer division and remainder education) in most programming languages ​​(and even in Intel 80x86 processors) this everyday approach are exactly implemented accordingly.

Some programming languages ​​and computer algebra systems reflect this diversity of conventions bill, by providing two or modulo residual operators. In the example, Ada has:

• (A REM B) the same sign as A and an absolute value smaller than the absolute value of B
• (A mod B) the same sign as B, and an absolute value smaller than the absolute value of B

Modulo

Modulo b calculates the remainder of division n divided by m. One can define a function that each pair of numbers { n; m } clearly the divider remainder b assigns. These are called " modulo " [ mo ː modulo ː ] (Latin modulus, ablative case " by measure " or " in moderation ", thus majority Modulis ) and is usually abbreviated to mod. In many programming languages, it is represented by %, and treated as an operator.

We consider the function

In addition to these so-called " Mathematical variant " is often also a similar function called Modulo, which provides different results for negative arguments and " symmetric version" is called:

Gilt and so both options give the same result. In programming languages ​​, the implemented version is not uniform. So Ruby, Python and Perl use the mathematical variant, whereas Java, C, JavaScript and PHP use the symmetric, which is especially important in ports. The computer contained in the Google search uses the mathematical variant.

If in a language like C ( ) or Java only the symmetric version is available, you can get results by the mathematical variant with:

Where% of the symmetric modulo operation and corresponds to the mathematical mod.

Examples

If so, does not follow that is, only, and that differ by an integral multiple of, that is: with. Such an equation can be written more simply using the spread in number theory congruence:

Basic arithmetic operations modulo a natural number

If the number m is a prime number, so you can see the familiar from the reals basic operations with subsequent modulo calculation apply and receive a so-called finite field.

Examples

• Residue class modulo 3:
• Residue class modulo 5:

Generalization: Real Numbers

If a and b are real numbers, b is not 0, then one can define a division with remainder as follows: the integer quotient c and remainder r in the half-open interval [0, | b | ) are those ( uniquely determined ) numbers satisfying the equation a = b · c r satisfy.

Again, there are alternatives to give the rest of the same sign as b, or to select the smallest amount remaining. The latter alternative corresponds to the rounding: The division with remainder of a by 1 provides an integer and c is a real number r with amount less than or equal to 0.5 satisfy the equation a = c r. The number c is the number rounded to integer value of a

It should be noted that in this case the ratio is not taken from the same amount ( of real numbers ), as the divisor and dividend.

Polynomials

An example is the following polynomial

The polynomials and can be determined by polynomial division.

Application

Programming

Division with remainder ( modulo) is relatively frequently used in the programming. The syntax is that of an operator. With mod can check whether a number is even: if (( x mod 2 ) == 0), then x is even. Modulo you can also use if you want to run a special program code in a loop only at every n-th iteration. Moreover, many calculations and algorithms he finds useful application. Generally, one can check with mod, if a number is divisible by another precisely: only the modulus is equal to zero. Furthermore, one must often complement in programming to whole multiples of a number (eg 4 bytes) and gets through the Modulo out how many " pad byte" are still missing. Divmod The function integer quotient and remainder are evaluated.

Other applications

• Calculation of the check digit of the International Standard Book Number
• Checksum formula Luhn algorithm for confirmation of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers
• Calendar Calculation ( the relatively complicated calculation of the Easter date )
• The International Bank Account Number ( IBAN)
• In cryptography, the Diffie -Hellman key exchange or the RSA cryptosystem