Division with remainder
applies. The numbers and can be determined by division in writing .
If two natural numbers , the dividend and the divisor (not equal to 0), are to be divided with a remainder, so if
is to be calculated, you are asked how you can represent the number as a multiple of and a "small remainder":
Here is the so-called integer quotient and the rest. The crucial constraint is that a number is in. This is clearly determined.
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.
- 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.
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:
- Instead, you can ask that the remainder be between 0 and (the amount of minus 1).
- Alternatively, one can also require that the remainder lies between and 0, i.e. has the same sign as
- A third option is to choose the remainder with the smallest amount . This variant provides the best approximation for
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
−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
- (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 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 .
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.
We consider the function
- 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
- for all
- but in general is
- z. B.
- Is positive so is for everyone
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":
- Here denotes the quotient rounded towards zero , given by , where denotes the sign function. The following applies to this variant
- but in general
- z. B.
- always has the same sign as , or it applies .
If only the symmetrical variant is available in a language like C (++) or Java, you can get results according to the mathematical variant with:
((a % b) + b) % b,
%the symmetrical modulo operation denotes and the mathematical.
- there ("3 fits into 17 five times and there are 2 left" - the rest is 2)
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 :
The spelling is also common
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:
- or even
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.
Basic arithmetic modulo a natural number
- Modulo 3:
- Modulo 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 .
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 .
It should be noted that the quotient is not taken from the same set (of the real numbers) as the divisor and dividend.
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
The zero polynomial is given a smaller degree than any other polynomial, for example .
The polynomials and can be determined by polynomial division .
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.
if ((x mod 2) == 0)
- 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.
- Calculation of the check digit of the international standard book number
- Checksum Formula Luhn algorithm to confirm identification numbers such as credit card numbers and Canadian social security numbers
- Checksum calculation for CRC and FEC on an integer or binary basis
- Calendar calculation (the relatively complicated calculation of the Easter date )
- Calculation of the checksum of the international bank account number (IBAN)
- In cryptography , Diffie-Hellman key exchange or the RSA cryptosystem
- Calculation of the geometry of Schröder diffusers
- Formation of binary fractals
- Hash function and the procedures mentioned there
- Little Fermatsch sentence
- Euler's theorem
- List of operators for the remainder of a division
- Kristina Reiss , Gerald Schmieder: Basic knowledge of number theory. An introduction to numbers and number ranges. Springer-Verlag, Berlin a. a. 2005, ISBN 3-540-21248-5 .
- Peter Hartmann: Mathematics for Computer Scientists. A practical textbook. 4th revised edition. Vieweg, Wiesbaden 2006, ISBN 3-8348-0096-1 , p. 62, (online) .
- Albrecht Beutelspacher , Marc-Alexander Zschiegner: Discrete Mathematics for Beginners. With applications in technology and IT. Vieweg, Wiesbaden 2007, ISBN 978-3-8348-0094-7 , p. 65, (online) .
- Ulm University: "Elementary Number Theory" 
- Calculate modulo online
- Java is also an island: the remainder operator%
- Integer division and the remainder
- Division with remainder - the secret main law of algebra (PDF; 86 kB)
- Video: Division by remainder (part 1) . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19767 .
- Video: Division by remainder (part 2) . Pedagogical University of Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19768 .