2 Applications of modular arithmetic

Modular arithmetic, first systematically studied by Carl Friedrich Gauss at the end of the eighteenth century, is applied in number theoryTraditionally, number theory is that branch of pure mathematics concerned with the properties of integers and contains many open problems that are easily understood even by non-mathematicians. More generally, the field has come to be concerned with a wide, abstract algebraAbstract algebra Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. The term "abstract algebra" is used to distinguish the field from " elementary algebra" or "high school algebr, cryptographyCryptography (from Greek kryptos "hidden", and graphein "to write") is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — th, 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 CThe C Programming Language Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a low-level standardized programming language developed in the early; where for example arithmetic operations on "int" integers are all taken modulo 2³², on most computers.

2.1 In art

In music, because of octaveIntervals : For the numerical computation software, see GNU Octave. In music, an octave (sometimes abbreviated 8ve or 8va is the interval between one musical note and another with half or double the frequency. For example, if one note is pitched at 400 Hz and enharmonicIn music, an enharmonic is a note which is the equivalent of some other note, but spelled differently. For example, in twelve-tone equal temperament (the normal system of musical tuning in the west), the notes C sharp and D flat are enharmonically equival 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 (see link below).

3 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 + nZ or a mod n. The set of all equivalence classes is denoted Z/nZ = { [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₁ ≡ b₁ (mod n)    and    a₂ ≡ b₂ (mod n)

then

a₁ + a₂ ≡ b₁ + b₂ (mod n)

and

a₁a₂ ≡ b₁b₂ (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/nZ by the following formulae:

• [a]_n + [b]_n = [a + b]_n
• [a]_n[b]_n = [ab]_n

In this way, Z/nZ becomes a commutative ring with n elements. For instance, in the ring Z/12Z, we have

[8]₁₂[3]₁₂ + [6]₁₂ = [30]₁₂ = [6]₁₂.

In abstract algebra, it is realized that modular arithmetic is a special case of forming the factor ring of a ring modulo an ideal. If R is a commutative ring, and I is an ideal of R, then the elements a and b of R are congruent modulo I if a − b is an element of I. As with the ring of integers, this turns out to be an equivalence relation, and addition and multiplication become well-defined operations on the factor ring R/I.

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

a^p ≡ a (mod p).

This was generalized by Euler: for any positive integer n and any integer a that is relatively prime to n,

a^φ(n) ≡ 1 (mod n),

where φ(n) denotes Euler's φ function counting the integers between 1 and n that are coprime to n. Euler's theorem is a consequence of the Theorem of Lagrange, applied to the group of units of the ring Z/nZ.

4 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 bits, but may simply mean "watch out: if you go over 1000 this computer will give you weird results".

5 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".

See modulo.

6 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, this mathematical jargon 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.

6.1 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.

7 See also

Congruence relation

8 External resources

• Perl arithmetic enhancements -- explains the reasoning behind Perl's % operator
• Cut-the-Knot.org: Modular Arithmetic
• Modular Art

<Hide>