Modular arithmetic

This article is about an algebra concept. See modulo for other uses.

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus. Modular arithmetic was introduced by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae published in 1801.

One way to understand modular arithmetic is to consider "clock arithmetic": the arithmetic of hours on the clock face. If the time is noted at 7 o'clock and then again 8 hours later, then rather than ending at 15 o'clock (as in usual addition), the time will actually be 3 o'clock, albeit one day later. Likewise, if the clock starts at noon and 7 hours elapses three times (3 × 7), then the time will be 9 o'clock (rather than 21). Since the time starts over at 1 after passing 12, this is similar to arithmetic modulo 12, except that normal modular arithmetic would begin at 0 and "roll over" after 11. The 24 hour clock, which goes from 00:00 to 23:59, is a closer approximation to modular arithmetic, using a modulus of 24.

The congruence relation

Two integers a and b are said to be congruent modulo n, if a and b have the same remainder when divided by n, or equivalently, that their difference (a−b) is a multiple of n. In this case, it is expressed as

a ≡ b (mod n).

For instance,

38 ≡ 14 (mod 12)

because 38 − 14 = 24 which is a multiple of 12. For positive numbers, congruence can also be thought of as asserting that two numbers have the same remainder after dividing by the modulus n. So,

38 ≡ 14 (mod 12)

because when divided by 12 both numbers give 2 as remainder.

Congruence is an equivalence relation, and the equivalence class of the integer a is denoted by [a]_n = { ..., a − 2n, a − n, a, a + n, a + 2n, a + 3n, ...}. This set of all integers congruent to a modulo n is called the congruence class or residue class of a modulo n, and is also denoted by ${\hat {a}}$ .

If

a₁ ≡ b₁ (mod n)

and

a₂ ≡ b₂ (mod n)

then

a₁ + a₂ ≡ (b₁ + b₂)(mod n)

and

a₁a₂ ≡ b₁b₂ (mod n).

This observation underpins modular arithmetic.

This is the prototypical example of a congruence relation.

In simpler terms:

Given any positive integer n and any non-negative integer a, if a is divided by n, the result can be expressed as an integer quotient q and an integer remainder r. Modular arithmetic is only interested in the remainder (or residue) after division by some modulus, and results with the same remainder are regarded as equivalent, or congruent. Two integers a and b are said to be congruent modulo n if (a mod n) = (b mod n).

The ring of congruence classes

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

Z/nZ = { [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/nZ becomes a commutative ring with |n| elements. For instance, in the ring Z/12Z, we have

[8]₁₂ + [6]₁₂ = [2]₁₂.

The notation Z/nZ is used, because it is the factor ring of Z by the ideal nZ containing all integers divisible by n.

In terms of groups, the residue class [a]_n is the coset of a in the quotient group Z/nZ, a cyclic group.

The set Z/nZ has a number of important mathematical properties that make it the foundation of many different branches of mathematics.

Where n = 0, Z/nZ does not have zero elements; rather, it is isomorphic to Z, since [a]₀ = {a}. This seemingly counterintuitive special case follows from the definitions and is useful for example when discussing the characteristic of a ring.

Remainders

The notion of modular arithmetic is related to that of the remainder in division. The operation of finding the remainder is known as the modulo operation and is sometimes written as "mod", so we write "14 mod 12 = 2". This meaning of "mod" is subtly but significantly different from that introduced in this article; it is true to say "38 ≡ 14 (mod 12)" , but it is not true to say "38 = 14 mod 12" — 38 is congruent to 14 modulo 12, but the remainder of 14 divided by 12 is 2, not 38. To avoid this confusion, the congruence relation is sometimes expressed by using modulo instead of mod like "38 ≡ 14 (modulo 12)" in computer science.

When working with modular arithmetic, each equivalence class is usually represented with its least non-negative member, which is called the common residue. This can be found using long division.

Applications

Modular arithmetic is referenced in number theory, group theory, ring theory, abstract algebra, cryptography, computer science, and the visual and musical arts.

It is one of the foundations of number theory, touching on almost every aspect of its study, and provides key examples for group theory, ring theory and abstract algebra.

In cryptography, modular arithmetic directly underpins public key systems such as RSA and Diffie-Hellman, as well as providing finite fields which underlie elliptic curves, and is used in and a variety of symmetric key algorithms including IDEA and RC4.

In computer science, modular arithmetic is often applied in bitwise operations and other operations involving fixed-width, cyclic data structures. The modulo operation, as implemented in many programming languages and calculators, is an application of modular arithmetic that is often used in this context.

In the visual arts, modular arithmetic can be used to create artistic patterns based on the multiplication and addition tables modulo n (see external link, below).

In music, modular arithmetic is used in the consideration of the twelve tone equally tempered scale, where octave and enharmonic equivalency occurs (that is, pitches in a 1∶2 or 2∶1 ratio are equivalent, and C-sharp is the same as D-flat).

References

Tom M. Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. See in particular chapters 5 and 6 for a review of basic modular arithmetic. ISBN 0387901639
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 31.3: Modular arithmetic, pp.862–868.

External links

In this modular art article, one can learn more about applications of modular arithmetic in music.
Congruence from MathWorld.