# 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

ab (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

a1b1 (mod n)

and

a2b2 (mod n)

then

a1 + a2b1 + b2 (mod n)

and

a1a2b1b2 (mod n).

## The ring of congruence classes

One can then define formally an addition and multiplication on the set

Z/nZ = { n, n, 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

12 + 12 = 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.

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.

• 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:合同式

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy