Modular arithmetic
From Exampleproblems
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 we begin at 7 o'clock and add 8 hours, then rather than ending at 15 o'clock (as in usual addition), we are at 3 o'clock. Likewise, if we start at noon and count off 7 hours three times (3 × 7), we end up at 9 o'clock (rather than 21). Essentially, when we reach 12, we start over; 12 is called the modulus, and so this is an example of arithmetic modulo 12.
Contents |
The congruence relation
Two integers a, b are said to be congruent modulo n if their difference is divisible by n. In this case, we write
- a ≡ b (mod n).
For instance,
- 38 ≡ 14 (mod 12)
because 38 − 14 = 24 which is divisible by 12.
This 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 
.
If
- a1 ≡ b1 (mod n)
and
- a2 ≡ b2 (mod n)
then
- a1 + a2 ≡ b1 + b2 (mod n)
and
- a1a2 ≡ b1b2 (mod n).
This observation underpins modular arithmetic. Sometimes such b is called the residue of a (mod n). If b is non-negative and smaller than |n| (the absolute value of n), then b is called common residue. This terminology has little in common with residues in complex analysis. The quantity n is sometimes called the base.
This is the prototypical example of a congruence relation.
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]12 + [6]12 = [2]12.
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]0 = {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". Note that 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.
If we define remainders to always lie between 0 and |n| then the remainder is the same as the common residue defined above, and we can assert that for nonzero n, two numbers are congruent modulo n iff they have the same remainder after division by n. The division algorithm guarantees the existence of a suitable remainder. However, remainders (and so the modulo operation) are sometimes defined so that the remainder of a number has the same sign as that number, and using that definition this rule does not work.
When working with modular arithmetic, we usually represent each equivalence class with its least non-negative member, which is 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 operations involving binary numbers and other 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).
Reference
- 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.
See also
- Quadratic residue
- Legendre symbol
- Quadratic reciprocity
- Primitive root
- Topics relating to the group theory behind modular arithmetic:
- Other important theorems relating to modular arithmetic:
External links
- In this modular art article, one can learn more about applications of modular arithmetic in music.
- Congruence from MathWorld.de:Kongruenz (Zahlentheorie)
