**Modular arithmetic** is a modified 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, under modulo 12 the answer is two, as two is the 'remainder' after dividing 14 by the modulus 12.

Formally, if the modulus *n* is any positive integer, we call two integers *a*, *b* **congruent modulo ***n* iff 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*).

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* and

*b* are congruent and

*x* and

*y* are congruent, then so are

*a + x* and

*b + y*, and

*ax* and

*by*. This allows to define an addition and multiplication on the set

**Z**_{n} = { [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**_{n} becomes a commutative

ring with

*n* elements. 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. This ring is also often written as

**Z**/

*n***Z**, because it is the factor ring of

**Z** by the

ideal *n***Z** containing all integers divisible by

*n*.

The units of this ring are precisely the elements [*a*]_{n} where *a* and *n* don't have any non-trivial divisors in common (are "relatively prime"). Therefore,
**Z**_{n} is a field if and only if *n* is a prime number. All finite fields are extensions of these.

An important fact about prime number moduli is Fermat's little theorem: if *p* is a prime number and *a* is any integer, then

*a*^{p} = *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**_{n}.

Modulo arithmetic, first systematically studied by Carl Friedrich Gauss at the end of the eighteenth century, is applied in number theory, abstract algebra and cryptography. In abstract algebra, it is realized that modulo arithmetic is a special case of forming the [factor ring]? of a ring modulo an ideal.

The fundamental arithmetic operations performed by most computers are actually modulo arithmetic, where the modulus is 2^{b} (*b* being the number of bits of the values being operated on). This is exposed in programming languages like C where for example arithmetic operations on "int" integers are all modulus 2^{32} on most computers.