| |
|
As explained below, one can add such congruence classes to get another such congruence class, subtract two such classes to get another, and multiply such classes to get another. When the modulus is a prime number, one can also divide.
Two discrepant conventions prevail:
The original convention is that the expression
In Latin, the language in which Gauss wrote, modulo is the ablative case of modulus. The number n, which in this example is 10, is the modulus.
Accoring to the newer convention, "63 mod 10" means the remainder left when 63 is divided by 10.
In general a mod n is the remainder in {0, ..., n−1} on division of a by n. For instance, 23 mod 12 = 11. (Calculations mod 12 are what one does when converting the time from a 24 hour clock to a 12 hour clock).
In some programming languages, this operation is written as a % n.
The difference in conventions is not very serious, in fact; it is reasonably thought of as reflecting the preference, for computational purposes, of a normal form over the underlying equivalence relation. This can be regarded mainly as a notational convention in this case, where there is a strict-sense normal form.
In practice x mod y can be calculated by using equations, in terms of other functions. Differences arise according to the scope of the variables, which in common implementations is broader than in the definition just given.
In terms of the floor function floor(z), the greatest integer less than or equal to z:
x mod y = x - y*floor(x/y).
In terms of truncation to the integer part (known as remain() on several calculators and always positive; performed by C's built-in % operator):
x mod y = x - y*iPart(x/y)
In the case of floor, a negative divisor results in a negative modulus (for example, under this definition, 1 mod -2 = -1). The resulting function is what is known as mod() on calculators and is implemented in some high-level languages, including Perl. Perl also uses the % operator to indicate a modulus operation, alluding to the / division operator.
Both definitions allow for x and y to be typed as integers or rational numbers.
The expression x mod 0 is undefined in the majority of numerical systems, although some do define it to be x.
Modular arithmetic, first systematically studied by Carl Friedrich Gauss at the end of the eighteenth century, is applied in number theory, abstract algebra, cryptography, and visual and musical art.
The fundamental arithmetic operations performed by most computers are actually modular arithmetic, where the modulus is 2b (b being the number of bits of the values being operated on). This comes to light in the compilation programming languages such as C; where for example arithmetic operations on "int" integers are all taken modulo 232, on most computers.
In music, because of octave and enharmonic equivalency (that is, pitches in a 1/2 or 2/1 ratio are equivalent, and C# is the same as Db), modular arithmetic is used in the consideration of the twelve tone equally tempered scale, especially in twelve tone music. In visual art modular arithmetic can be used to create artistic patterns based on the multiplication and addition tables modulo n [1].
Recall from above that two integers a, b congruent modulo n, written as
Here is an example of the congruence notation.
If a and b are integers, the congruence
This equivalence relation has an important properties which follow immediately from the definition: if
Definition of modulo
The older "theoretical math" convention
means that a and b are both in the same "congruence class" modulo n, i.e., both leave the same remainder on division by n, or, equivalently, a − b is a multiple of n. Thus we have, for example
since 63 and 83 both leave the same remainder (3) on division by 10, or, equivalently, 63 − 83 is a multiple of 10. One says:
or
"Modulo" is usually abreviated to "mod" in speaking, just as in writing. The parentheses, i.e., the round brackets (), are usually not written, but in this case they emphasize the difference between the traditional mathematicians' convention and the modern computing convention. The usage of mathematicians parses the phrase differently from the computing usage.The newer "computing" convention
Implementation of the 'mod' function
Applications of modular arithmetic
Some consequences of the theoretical math usage
Using this definition, we can generalize to non-integral moduli. For instance, we can define a ≡ b (mod π) if a − b = kπ for some integer k. This idea is developed in full in the context of ring theory below.
This is an equivalence relation, and the equivalence class of the integer a is denoted by [a]n (or simply [a] if the modulus n is understood.) Other notations include a + nZ or a mod n. The set of all equivalence classes is denoted Z/nZ = { [0]n, [1]n, [2]n, ..., [n-1]n }.
has a solution x if and only if the greatest common divisor (a, n) divides b. The details are recorded in the linear congruence theorem. More complicated simultaneous systems of congruences with different moduli can be solved using the Chinese remainder theorem or the method of successive substitution.
then
and
This shows that addition and multiplication are well-defined operations on the set of equivalence classes. In other words, addition and multiplication are defined on Z/nZ by the following formulae:
In this way, Z/nZ becomes a commutative ring with n elements.
For instance, in the ring Z/12Z, we have
In the ring of integers, if we consider the equation ax ≡ 1 (mod n), then we see that a has a multiplication inverse if and only if a and n are coprime. Therefore, Z/nZ is a field if and only if n is prime. It can be shown that every finite field is an extension of Z/pZ for some prime p.
An important fact about prime number moduli is Fermat's little theorem: if p is a prime number and a is any integer, then
To say that any two things are the same "modulo" a third thing means, more-or-less, that the difference between the first two is accounted for or explained by the third. That is, the up to concept is often talked about this way, using modulo as a term alerting the hearer. In mathematics, this admits various precise definitions. In particular, two members of a ring or an algebra are congruent modulo an ideal if the difference between them is in the ideal. The use of the term in modular arithmetic is a special case of that usage, and that is how this more general usage evolved. Some loose terms such as almost all can in this way acquire precise meanings from a Boolean algebra version, in which symmetric difference of sets replaced arithmetical subtraction; for example "modulo finite sets".
Mathematicians speaking of things non-mathematical still say "A is the same as B modulo C" when they mean A is the same as B except for differences accounted for by C. But in such non-mathematical contexts, the phrase may not admit any very precise definition. Consequently mathematicians and computer scientists often use the phrase in an informal or even jocular way.
Some users of the term either lack this theoretical viewpoint or else ignore it, and use the word "modulo" more-or-less synonymously with the preposition except.
Slang use of the word modulo
Examples
External Resources