Modular arithmetic
|
|
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 2, as 2 is the remainder after dividing 14 by the modulus 12.
| Contents |
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).
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 term "ring" originates here, because the numbers 0, ..., n − 1 are most conveniently arranged in a ring akin to the numbers on the face of a clock. 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. These are further developed in the article on modular arithmetic theory.
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).
History
Modular arithmetic was introduced into mathematics in the book Disquisitiones Arithmeticae by Carl Friedrich Gauss in 1801.
See also
For more information on the group theory behind modular arithmetic, see
Some important theorems about modular arithmetic:
For more advanced properties of modular arithmetic:
Modular arithmetic is often used as a tool for primality tests and integer factorization.
External link
- In this modular art (http://britton.disted.camosun.bc.ca/modart/jbmodart.htm) article, one can learn more about applications of modular arithmetic in music.ja:合同式