Main Page | See live article | Alphabetical index

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, in modulo 12 arithmetic the answer is 2, as 2 is the remainder after dividing 14 by the modulus 12.

Table of contents
1 Definition of Modulo
2 Applications of Modular Arithmetic
3 Congruent modulo
4 External Resources

Definition of Modulo

If a is any integer and n is a positive integer, we write a mod n for the remainder in {0, ..., n-1} that occurs if a is divided by n. For instance, 23 mod 12 = 11 (Calculations mod 12 are what one does when converting the time from a 24 hour clock to a 12 hour clock).

In some programming languages, this operation is written as a % n.

Implementation of the 'mod' function

In practice x mod y can be calculated by using equations, in terms of other functions. Differences arise according to the scope of the variables, which in common implementations is broader than in the definition just given.

In terms of the floor function floor(z), the greatest integer less than or equal to z:

x mod y = x - y*floor(x/y).

In terms of truncation to the integer part (known as remain() on several calculators and always positive; performed by C's built-in % operator):

x mod y = x - y*iPart(x/y)

In the case of floor, a negative divisor results in a negative modulus (for example, under this definition, 1 mod -2 = -1). The resulting function is what is known as mod() on calculators and is implemented in some high-level languages, including Perl. Perl also uses the % operator to indicate a modulus operation, alluding to the / division operator.

Both definitions allow for x and y to be typed as integers or rational numbers.

The expression x mod 0 is undefined in the majority of numerical systems, although some do define it to be x.

Applications of Modular Arithmetic

Modular arithmetic, first systematically studied by Carl Friedrich Gauss at the end of the eighteenth century, is applied in number theory, abstract algebra, cryptography, and visual and musical art.

The fundamental arithmetic operations performed by most computers are actually modular arithmetic, where the modulus is 2b (b being the number of bits of the values being operated on). This comes to light in the compilation programming languages such as C; where for example arithmetic operations on "int" integers are all taken modulo 232, on most computers.

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 [1].

Congruent modulo

We call two integers a, b congruent modulo n, written as

a ≡ b (mod n) if their difference a − b is divisible by n, i.e. if a − b = kn for some integer k.

Using this definition, we can generalize to non-integral moduli. For instance, we can define a ≡ b (mod π) if a − b = kπ for some integer k. This idea is developed in full in the context of ring theory below.

Here is an example of the congruence notation.

14 ≡ 26 (mod 12).
This is an equivalence relation, and the equivalence class of the integer a is denoted by [a]n (or simply [a] if the modulus n is understood.) Other notations include a + nZ or a mod n. The set of all equivalence classes is denoted Z/nZ = { [0]n, [1]n, [2]n, ..., [n-1]n }.

If a and b are integers, the congruence

ax ≡ b (mod n)
has a solution x if and only if the greatest common divisor (a, n) divides b. The details are recorded in the linear congruence theorem. More complicated simultaneous systems of congruences with different moduli can be solved using the Chinese remainder theorem or the method of successive substitution.

This equivalence relation has an important properties which follow immediately from the definition: if

a1 ≡ b1 (mod n)    and    a2 ≡ b2 (mod n)
then
a1 + a2 ≡ b1 + b2 (mod n)
and
a1a2 ≡ b1b2 (mod n).

This shows that addition and multiplication are well-defined operations on the set of equivalence classes. In other words, addition and multiplication are defined on Z/nZ by the following formulae: In this way, Z/nZ becomes a commutative ring with n elements. For instance, in the ring Z/12Z, we have
[8]12[3]12 + [6]12 = [30]12 = [6]12.

In abstract algebra, it is realized that modular arithmetic is a special case of forming the factor ring of a ring modulo an ideal. If R is a commutative ring, and I is an ideal of R, then the elements a and b of R are congruent modulo I if a − b is an element of I. As with the ring of integers, this turns out to be an equivalence relation, and addition and multiplication become well-defined operations on the factor ring R/I.

In the ring of integers, if we consider the equation ax ≡ 1 (mod n), then we see that a has a multiplication inverse if and only if a and n are coprime. Therefore, Z/nZ is a field if and only if n is prime. It can be shown that every finite field is an extension of Z/pZ for some prime p.

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

ap ≡ 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 coprime to n. Euler's theorem is a consequence of the Theorem of Lagrange, applied to the group of units of the ring Z/nZ.

External Resources