Modular arithmetic

From Example Problems
Jump to navigation Jump to search
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 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.

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

ab (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, an, 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{a}} .

If

a1b1 (mod n)

and

a2b2 (mod n)

then

a1 + a2b1 + b2 (mod n)

and

a1a2b1b2 (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

External links

de:Kongruenz (Zahlentheorie) he:חשבון מודולרי ja:合同式 pl:Ciało Zp th:ระบบจำนวนแบบมอดูลาร์