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.
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.
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.
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].
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:
- [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/12
Z, 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.