modular arithmetic
is a system of arithmetic for certain equivalence_classes of integers, called congruence classes. Sometimes it is suggestively called 'clock_arithmetic', where numbers 'wrap around' after they reach a certain value (the modulus). For example, when the modulus is 12, then any two numbers that leave the same remainder when divided by 12 are equivalent (or "congruent") to each other. The numbers : ..., −34, −22, −10, 2, 14, 26, ... are all "congruent modulo 12" to each other, because each leaves the same remainder (2) on division by 12. The collection of all such numbers is a congruence class. 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 always divide by any class not containing 0.Definition of ''modulo''
Two discrepant conventions prevail:The older convention, used by mathematicians
The original convention is that the expression :a\equiv b\ (\mbox{mod}\ n) 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 :63\equiv 83\ (\mbox{mod}\ 10) 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: :"63 is congruent to 83, modulo 10," or :"63 and 83 are congruent to each other, modulo 10." "Modulo" is usually abbreviated 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 mathematical convention and the modern computing convention. The mathematical usage parses the phrase differently from the computing usage. 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.The newer convention, used in computing
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.Implementation of the 'mod' function
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''.Applications of modular arithmetic
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 2''b'' (''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 art
In music, because of 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'' (see link below).Some consequences of the mathematical usage
Recall from above that two integers ''a'', ''b'' congruent modulo ''n'', written as :''a'' ≡ ''b'' (mod ''n'') if their difference ''a'' − ''b'' is divisible by ''n'', i.e. if ''a'' − ''b'' = ''kn'' for some integer ''k''. 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. Here is an example of the congruence notation. :14 ≡ 26 (mod 12). 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'' + ''n''Z or ''a'' mod ''n''. The set of all equivalence_classes is denoted Z/''n''Z = { [0]''n'', [1]''n'', [2]''n'', ..., [''n''-1]''n'' }. If ''a'' and ''b'' are integers, the congruence :''ax'' ≡ ''b'' (mod ''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. This equivalence relation has important properties which follow immediately from the definition: if :''a''1 ≡ ''b''1 (mod ''n'') and ''a''2 ≡ ''b''2 (mod ''n'') then :''a''1 + ''a''2 ≡ ''b''1 + ''b''2 (mod ''n'') and :''a''1''a''2 ≡ ''b''1''b''2 (mod ''n''). 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/''n''Z by the following formulae:Another "computing" usage
An implied meaning of ''modulo'' in computing contexts is "valid up to this value." For example, "addition is modulo 1,000" means that the addition operation being described provides valid answers until the sum goes beyond 1,000. Digital representations of number spaces are not infinite (see binary_numeral_systems). Thus, if a computer is representing a set of positive integers as 8-bits, the values that can be represented range from 0 to 255. When an addition (or multiplication, or whatever) results in a number above this cutoff, the typical behavior is for the values to wrap around. For example, in the 8-bit positive integer situation, 255 + 1 = 0. This computer is therefore described as "modulo 256". Furthermore, some computers do different operations with different bit representations. So although the storage of integers may be 8-bit ("modulo 256"), the addition of integers may be 12-bit ("modulo 4096"), or anything else. Thus individual operations can also be described as "modulo ''x''". In the case of signed (positive and negative) integers, or floating point numbers, the wrap around effect is more complicated, and is not always perfectly analogous to the formal mathematical modulo. However, the slang persists such that "addition is modulo 1000" may not literally mean (in fact cannot literally mean) that the computer does addition in \log_{2}1000 bits, but may simply mean "watch out: if you go over 1000 this computer will give you weird results".More general use of the word ''modulo'' by mathematicians
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".Slang use of the word ''modulo''
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''.Examples
:"http and https are the same, modulo encryption." - means "the only difference between http and https is the addition of encryption". :"These two characters are equal." :"You mean, equal modulo case." - indicates that the first speaker is wrong: the characters are not the same, one is uppercase and the other lowercase. :"The two students performed equally well on the exam, modulo some minor computational mistakes." - means that the two students demonstrated an equal understanding of the material and its application, but one of them lost some points for minor computational mistakes. :"This code is finished modulo testing" - means "this code is finished except for testing". Since testing is generally considered quite important, whereas in mathematics the use of modular arithmetic generally ignores the difference between modulo-equal numbers, use of a phrase like this might be deliberate understatement.External resources
Original, History and Authors:
en-wikipedia-org/wiki/Modular arithmetic | History and Authors | Edit Content
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation. A copy of the license is included in the section entitled
"GNU Free Documentation License".
