- This article is about an algebra concept. See modulo for other uses.
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus.
Modular arithmetic is sometimes colloquially known as "clock arithmetic". This is a term sometimes used for modular arithmetic when the modulus is 12. It refers to the behavior of addition of hours on a clock face: for example, if we begin at 7 o'clock and add 8 hours, then rather than ending at 15 o'clock (as in usual addition), we are at 3 o'clock. Likewise, if we start at noon and count off 7 hours three times (3 × 7), we end up at 9 o'clock (rather than 21). Essentially, when we reach 12, we start over; 12 is called the modulus, hence the name "modular arithmetic."
We can easily pretend that the clock face contains any number of hours, and calculate according to the new modulus. However, unlike clock faces, numbers in modular arithmetic may start with any number. Musical set theory, for example, uses modulus 12 when representing 12-tone equal temperament, but finds it convenient to start its cycles with zero: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.
The congruence relation
Two integers a, b are said to be congruent modulo n if their difference is divisible by n; that is to say, if they leave the same remainder when divided by n. In this case, we write
- a ≡ b (mod n).
For instance,
- 26 ≡ 14 (mod 12).
This is an equivalence relation, and the equivalence class of the integer a is denoted by [a]n. This equivalence relation has an important additional property: if
- a1 ≡ b1 (mod n)
and
- a2 ≡ b2 (mod n)
then
- a1 + a2 ≡ b1 + b2 (mod n)
and
- a1a2 ≡ b1b2 (mod n).
Sometimes such b is called the residue of a (mod n). If b is non-negative and smaller than n, then b is called common residue. This terminology has little in common with residues in complex analysis. The quantity n is sometimes called the base.
The ring of congruence classes
One can then define formally an addition and multiplication on the set
- Z/nZ = { [0]n, [1]n, [2]n, ..., [n−1]n }
of all equivalence classes by the following rules:
- [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]12 + [6]12 = [2]12.
The notation Z/nZ is used, because it is the factor ring of Z by the ideal nZ containing all integers divisible by n.
The set Z/nZ has a number of important mathematical properties that make it the foundation of many different branches of mathematics.
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.
Applications
Modular arithmetic is applied in number theory, group theory, ring theory, abstract algebra, cryptography, computer science, and the visual and musical arts.
In number theory, modular arithmetic is often used as a tool for primality tests and integer factorization.
In computer science, modular arithmetic is often applied in operations involving binary numbers and other fixed-width, cyclic data structures. The modulo operation, as implemented in many programming languages and calculators, is an application of modular arithmetic that is often used in this context.
In the visual arts, modular arithmetic can be used to create artistic patterns based on the multiplication and addition tables modulo n (see external link, below).
In music, modular arithmetic is used in the consideration of the twelve tone equally tempered scale, where octave and enharmonic equivalency occurs (that is, pitches in a 1∶2 or 2∶1 ratio are equivalent, and C-sharp is the same as D-flat).
History
Modular arithmetic was studied first by Carl Friedrich Gauss and was written about in his book Disquisitiones Arithmeticae in 1801.
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.
See also
External links
|
