Modular arithmetic

This article is about an algebra concept. See modulo for other uses.

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.

Table of contents

1 The congruence relation 2 The ring of congruence classes 3 Applications 4 History 5 See also 6 External link

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

a₁ ≡ b₁ (mod n)

and

a₂ ≡ b₂ (mod n)

then

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

and

a₁a₂ ≡ b₁b₂ (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]₁₂ + [6]₁₂ = [2]₁₂.

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

• Cyclic group
• Multiplicative group of integers modulo n

Some important theorems about modular arithmetic:

• Chinese remainder theorem
• Fermat's little theorem
• Lagrange's theorem

For more advanced properties of modular arithmetic:

• Quadratic residue
• Legendre symbol
• Quadratic reciprocity
• Primitive root

Modular arithmetic is often used as a tool for primality tests and integer factorization.

External link

• In this modular art article, one can learn more about applications of modular arithmetic in music.

Help build the largest human-edited directory on the web.

Submit a Site - Open Directory Project - Become an Editor