Modular arithmetic is a system of arithmetic for integers, sometimes referred to as "clock arithmetic", where numbers "wrap around" after they reach a certain value (the modulus). For example, whilst 8 + 6 equals 14 in conventional arithmetic, in modulo 12 arithmetic the answer is two, as two is the remainder after dividing 14 by the modulus 12.
Introduction
Let n be a positive integer. We call two integers a and b congruent modulo n if their difference is divisible by n, or equivalently, if they leave the same remainder when divided by n. In this case, we write
- a = b (mod n).
For instance
- 14 = 26 (mod 12).
This is an equivalence relation, and the equivalence class of an integer a is denoted by [a]n. This equivalence relation has the following properties: if
- a1 = b1 (mod n)
and
- a2 = b2 (mod n)
then
- a1 + a2 = b1 + b2 (mod n)
and
- a1a2 = b1b2 (mod n).
This defines addition and multiplication on the set { [0]n, [1]n, [2]n, ..., [n − 1]n } of all equivalence classes by the rules
and
For instance, for the set with 12 elements, one has
- [8]12 + [6]12 = [2]12.
Group theory
The addition property
- [a]n + [b]n = [a + b]n
implies that this set of equivalence classes { [0]n, [1]n, [2]n, ..., [n − 1]n } is an abelian group. This group is called the cyclic group. It is variously denoted as Cn, Zn, or Z/nZ, depending on the author and the context. In fact, all finite abelian groups are isomorphic to some product of cyclic groups;
this is called the fundamental theorem of abelian groups. This theorem is possibly the most important result arising out of the study of modular arithmetic, and is worth stating again: all finite abelian groups behave in exactly the same way that modular addition does on a set of integers.
The fundamental theorem goes even farther: if the number n is the product of distinct prime number powers p1a1, p2a2, etc., then the cyclic group Z/nZ is isomorphic to the product of groups Z/p1a1Z × Z/p2a2Z × ... etc.. Thus, for example, the group Z/6Z can be thought of as consisting of the sets {[0]6,[3]6} and {[0]6,[2]6,[4]6}. The first set has
- [3]6 + [3]6 = [0]6
and thus behaves identically to the group Z/2Z. The second set can be easily seen to behave just like Z/3Z does. The set element [1]2×[1]3 can be added to itself 6 times before it wraps back to zero.
The notation of using a slash in the name: Z/nZ is meant to remind the reader that this group is a quotient group of the group Z of integers and the subgroup nZ of integers multiplied by n. In this notation, the equivalence classes [a]n are called cosets, and that Z/nZ is thus a factor group.
Note that the numbers 0, ..., n − 1 can be conveniently arranged in a ring akin to the numbers on the face of a clock. Thus, the cyclic group operations can be thought of as the rotation of an n-sided polygon or the rotation of a clock face. This connection to the circle implies that cyclic group can be represented by roots of unity. This group is sometimes called the character group and provides a good example of how something as simple as the group Z/nZ can appear to be mighty complicated in a slightly modified setting.
Ring theory
The multiplication property
- [a]n × [b]n = [ab]n
indicates that the set of nonzero equivalence classes is also an abelian group under multiplication as well as addition if n is prime. (If n is composite, then we won't have inverses for every element.) This implies that Z/nZ is a commutative ring with n elements. Note that in general, a ring cannot be factored into prime factors; the fundamental theorem holds only for abelian groups. Thus, although the notation Z/nZ is often used to denote both the group and the ring, and that superficially these are the same, there is a certain deep sense in which this is not the case: there are certain true statements that can be made for the group that become false for the ring (and vice versa).
The notation Z/nZ in this case helps remind the reader that the factor ring of Z by the ideal nZ containing all integers divisible by n. In abstract algebra, it is realized that modular arithmetic is a special case of forming the factor ring of a ring modulo an ideal.
Number theory
If a and b are integers, the congruence
- ax = b (mod n)
has a solution x if and only if the greatest common divisor gcd(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.
The above shows that the units of the ring Z/nZ are precisely the elements [a]n where a and n don't have any non-trivial divisors in common (are "coprime"). Therefore,
Z/nZ is a field if and only if n is a prime number. The more common notation for this field is 
; although one might say that Z/pZ and are the same thing, the notational difference helps remind the reader that is more than just a ring. Note that all finite fields are extensions of the .
An important fact about prime number moduli is Fermat's little theorem: if p is a prime number and a is any integer, then
- ap = 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 relatively prime to n. Euler's theorem is a consequence of the theorem of Lagrange, applied to the group of units of the ring Z/nZ. Euler's theorem provides a means of studying prime numbers; in this context, the group Z/nZ is sometimes called the character group; it is used to define Dirichlet characters and thus provides the bridge to the study of prime numbers through the Riemann zeta function.
Algorithms
In order to compute the value of n mod k, one must perform long division in some fashion or another. That is, n mod k = r where r is the remainder of the integer division a=n/k. That is, n=a k + r. The most famous and very efficient algorithm for computing the modulus of an integer is the Euclidean algorithm. This algorithm is a basic component of modern cryptography, and also leads to the study of fractals by means of the continued fraction.
Polynomials
The relation [a]n + [b]n = [a + b]n is an example of a polynomial, and specifically of an additive polynomial. If one denotes the free variables by x instead of a, and considers the set of polynomials in x, one finds that this set can be thought of as a vector space, or, more generally, a module. For example, Fermat's identity ap = a (mod p) becomes the cyclotomic polynomial xp − x = 0, whose zeros are the roots of unity.
The structure of groups, rings, vectors spaces and modules can all be studied by means of polynomials. Sometimes, the term modular arithmetic applies to the branch of mathematics that combines all of these disciplines (number theory, group theory, abstract algebra) in the study such polynomials. This branch includes the study of elliptic curves, cryptography and the modular group, and is the fruitful source of some of the most astounding results in mathematics today.
History
The first encyclopedia entry on modular arithmetic was written by Euclid, in Book 7 of Euclid's Elements, in 300 B.C. Modular arithmetic was first systematically studied by Carl Friedrich Gauss at the end of the eighteenth century.
Applications
Modular arithmetic is applied in number theory, abstract algebra, cryptography, and visual and musical art.
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 (see link below).
Reference
- Tom M. Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
External link