Modular arithmetic

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/nZ, because it is the factor ring of Z by the ideal nZ 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³² on most computers.