|
Modular arithmetic is a system of arithmetic for The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ...integers, sometimes referred to as " Modular arithmetic is a modified system of arithmetic for integers, sometimes referred to as odometer or clock arithmetic, where numbers wrap around after they reach a certain value (the modulus). ...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 two, as two is the remainder after dividing 14 by the modulus 12.
Introduction Let n be a positive integer. We call two integers a and b congruent modulo n if their difference is divisible by n, or equivalently, if they leave the same In mathematics, the result of the division of two integers usually cannot be expressed with an integer quotient, unless a remainder —an amount left over— is also acknowledged. ...remainder when divided by n. In this case, we write - a = b (mod n).
For instance - 14 = 26 (mod 12).
This is an In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...equivalence relation, and the equivalence class of an integer a is denoted by [a]n. This equivalence relation has the following properties: if - a1 = b1 (mod n)
and - a2 = b2 (mod n)
then - a1 + a2 = b1 + b2 (mod n)
and - a1a2 = b1b2 (mod n).
This defines addition and multiplication on the set { [0]n, [1]n, [2]n, ..., [n − 1]n } of all equivalence classes by the rules and For instance, for the set with 12 elements, one has - [8]12 + [6]12 = [2]12.
Group theory The addition property - [a]n + [b]n = [a + b]n
implies that this set of equivalence classes { [0]n, [1]n, [2]n, ..., [n − 1]n } is an In mathematics, an abelian group is a commutative group, i. ...abelian group. This The term group can refer to several concepts: In music, a group is another term for band or other musical ensemble. ...group is called the In mathematics, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that every element of the group is a power of a. ...cyclic group. It is variously denoted as Cn, Zn, or Z/nZ, depending on the author and the context. In fact, all finite abelian groups are In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ...isomorphic to some product of cyclic groups; this is called the In abstract algebra, an abelian group (G,+) is called finitely generated if there exist finitely many elements x1,...,xs in G such that every x in G can be written in the form x = n1x1 + n2x2 + ... + nsxs with integers n1,...,ns. ...fundamental theorem of abelian groups. This theorem is possibly the most important result arising out of the study of modular arithmetic, and is worth stating again: all finite abelian groups behave in exactly the same way that modular addition does on a set of integers.
The fundamental theorem goes even farther: if the number n is the product of distinct In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ...prime number powers p1a1, p2a2, etc., then the cyclic group Z/nZ is isomorphic to the product of groups Z/p1a1Z × Z/p2a2Z × ... etc.. Thus, for example, the group Z/6Z can be thought of as consisting of the sets {[0]6,[3]6} and {[0]6,[2]6,[4]6}. The first set has
- [3]6 + [3]6 = [0]6
and thus behaves identically to the group Z/2Z. The second set can be easily seen to behave just like Z/3Z does. The set element [1]2×[1]3 can be added to itself 6 times before it wraps back to zero.
The notation of using a slash in the name: Z/nZ is meant to remind the reader that this group is a In mathematics, given a group G and a normal subgroup N of G, the quotient group, or factor group, of G over N is a group that intuitively collapses the normal subgroup N to the identity element. ...quotient group of the group Z of integers and the In mathematics, given a group G under a binary operation *, we say that some subset H of G is a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H is a group operation...subgroup nZ of integers multiplied by n. In this notation, the equivalence classes [a]n are called In mathematics, if G is a group, H a subgroup of G, and g an element of G, then gH = { gh : h an element of H } is a left coset of H in G, and Hg = { hg : h an element of H } is a right coset of H in G...cosets, and that Z/nZ is thus a In mathematics, given a group G and a normal subgroup N of G, the quotient group, or factor group, of G over N is a group that intuitively collapses the normal subgroup N to the identity element. ...factor group.
Note that the numbers 0, ..., n − 1 can be conveniently arranged in a ring akin to the numbers on the face of a clock. Thus, the cyclic group operations can be thought of as the rotation of an n_sided polygon or the rotation of a clock face. This connection to the circle implies that cyclic group can be Representation theory is the branch of mathematics that studies properties of abstract groups via their representations as linear transformations of vector spaces. ...represented by In mathematics, the n_th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 _ 1754), are complex numbers located on the unit circle. ...roots of unity. This group is sometimes called the character group and provides a good example of how something as simple as the group Z/nZ can appear to be mighty complicated in a slightly modified setting.
Ring theory The multiplication property - [a]n × [b]n = [ab]n
indicates that the set of nonzero equivalence classes is also an abelian group under multiplication as well as addition if n is prime. (If n is composite, then we won't have inverses for every element.) This implies that Z/nZ is a commutative In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ...ring with n elements. Note that in general, a ring cannot be factored into prime factors; the fundamental theorem holds only for abelian groups. Thus, although the notation Z/nZ is often used to denote both the group and the ring, and that superficially these are the same, there is a certain deep sense in which this is not the case: there are certain true statements that can be made for the group that become false for the ring (and vice versa).
The notation Z/nZ in this case helps remind the reader that the factor ring of Z by the In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...ideal nZ containing all integers divisible by n. In Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ...abstract algebra, it is realized that modular arithmetic is a special case of forming the In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...factor ring of a ring modulo an In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...ideal.
Number theory If a and b are integers, the As an abstract term, congruence means similarity between objects. ...congruence - ax = b (mod n)
has a solution x if and only if the In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (GCF) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...greatest common divisor gcd(a, n) divides b. The details are recorded in the In modular arithmetic, the question of when a linear congruence can be solved is answered by the linear congruence theorem. ...linear congruence theorem. More complicated simultaneous systems of congruences with different moduli can be solved using the The Chinese remainder theorem is any of a number of related results in abstract algebra and number theory. ...Chinese remainder theorem.
The above shows that the units of the ring Z/nZ are precisely the elements [a]n where a and n don't have any non_trivial divisors in common (are " In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ...coprime"). Therefore, Z/nZ is a A field is an open land area, used for growing agricultural crops. ...field if and only if n is a In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ...prime number. The more common notation for this field is ; although one might say that Z/pZ and are the same thing, the notational difference helps remind the reader that is more than just a ring. Note that all In abstract algebra, a finite field or Galois field (so named in honor of Evariste Galois) is a field that contains only finitely many elements. ...finite fields are extensions of the .
An important fact about prime number moduli is Fermats little theorem states that if p is a prime number, then for any integer a, This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p (see modular arithmetic). ...Fermat's little theorem: if p is a prime number and a is any integer, then
- ap = a (mod p).
This was generalized by Leonhard Euler aged 49 (oil painting by Emanuel Handmann, 1756) Leonhard Euler (April 15, 1707 _ September 18, 1783) (pronounced oiler) was a Swiss mathematician and physicist. ...Euler: for any positive integer n and any integer a that is relatively prime to n, - aφ(n) = 1 (mod n),
where φ(n) denotes In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...Euler's φ function counting the integers between 1 and n that are In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ...relatively prime to n. In number theory, Eulers theorem (also known as the Fermat_Euler theorem) states that if n is a positive integer and a is coprime to n, then aφ(n) ≡ 1 ( mod n) where φ(n) denotes Eulers totient function. ...Euler's theorem is a consequence of the In mathematics, Lagranges theorem states that if G is a finite group and H is a subgroup of G, then the order (that is, the number of elements) of H divides the order of G. This can be shown using the concept of left cosets of H in G...theorem of Lagrange, applied to the group of units of the ring Z/nZ. Euler's theorem provides a means of studying prime numbers; in this context, the group Z/nZ is sometimes called the character group; it is used to define In number theory, a Dirichlet character is a function χ from the positive integers to the complex numbers which has the following properties: There exists a positive integer k such that χ(n) = χ(n + k) for all n. ...Dirichlet characters and thus provides the bridge to the study of prime numbers through the In mathematics, the Riemann zeta function is a function which is of paramount importance in number theory, because of its relation to the distribution of prime numbers. ...Riemann zeta function.
Algorithms In order to compute the value of n mod k, one must perform long division in some fashion or another. That is, n mod k = r where r is the remainder of the integer division a=n/k. That is, n=a k + r. The most famous and very efficient algorithm for computing the modulus of an integer is the The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...Euclidean algorithm. This algorithm is a basic component of modern Cryptography portal Cryptography (from Greek kryptós, hidden, and gráphein, to write) is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — the art of encryption. ...cryptography, and also leads to the study of A fractal is a geometric object which can be divided into parts, each of which is similar to the original object. ...fractals by means of the In mathematics, a continued fraction is an expression such as where a0 is some integer and all the other numbers an are positive integers. ...continued fraction.
Polynomials The relation [a]n + [b]n = [a + b]n is an example of a In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ...polynomial, and specifically of an additive polynomial. If one denotes the free variables by x instead of a, and considers the set of polynomials in x, one finds that this set can be thought of as a The fundamental concept in linear algebra is that of a vector space or linear space. ...vector space, or, more generally, a In abstract algebra, a module is a generalization of a vector space. ...module. For example, Fermat's identity ap = a (mod p) becomes the In mathematics, the n_th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 _ 1754), are complex numbers located on the unit circle. ...cyclotomic polynomial xp − x = 0, whose zeros are the In mathematics, the n_th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 _ 1754), are complex numbers located on the unit circle. ...roots of unity.
The structure of groups, rings, vectors spaces and modules can all be studied by means of polynomials. Sometimes, the term modular arithmetic applies to the branch of mathematics that combines all of these disciplines ( Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers and contains many open problems that are easily understood even by non_mathematicians. ...number theory, Group theory is that branch of mathematics concerned with the study of groups. ...group theory, Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ...abstract algebra) in the study such polynomials. This branch includes the study of In mathematics, elliptic curves are defined by certain cubic (the superscript exponent is three, a. ...elliptic curves, Cryptography portal Cryptography (from Greek kryptós, hidden, and gráphein, to write) is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — the art of encryption. ...cryptography and the In mathematics, the modular group Γ (Gamma) is a group that is a fundamental object of study in number theory, geometry, algebra, and many other areas of advanced mathematics. ...modular group, and is the fruitful source of some of the most astounding results in mathematics today.
History The first encyclopedia entry on modular arithmetic was written by Euclid of Alexandria (Greek: Eukleides) (circa 365–275 BC) was a Greek mathematician, now known as the father of geometry. His most famous work is Elements, widely considered to be historys most successful textbook. ...Euclid, in Book 7 of Euclids Elements ( Greek Στοιχεία) is a mathematical treatise, consisting of 13 books, written by the Greek mathematician Euclid around 300 BC. It comprises a collection of definitions, postulates, and proofs from Euclidean geometry, named after Euclid, and also Euclids account of number theory. ...Euclid's Elements, in 300 B.C. Modular arithmetic was first systematically studied by Johann Carl Friedrich Gauss Johann Carl Friedrich Gauss (Gauß) ( April 30, 1777 _ February 23, 1855) was a legendary German mathematician, astronomer and physicist with a very wide range of contributions; he is considered to be one of the greatest mathematicians of all time. ...Carl Friedrich Gauss at the end of the eighteenth century.
Applications Modular arithmetic is applied in Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers and contains many open problems that are easily understood even by non_mathematicians. ...number theory, Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ...abstract algebra, Cryptography portal Cryptography (from Greek kryptós, hidden, and gráphein, to write) is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — the art of encryption. ...cryptography, and visual and This article needs cleanup. ...musical art.
In music, because of For the numerical computation software, see GNU Octave. ...octave and In music, an enharmonic is a note which is the equivalent of some other note, but spelled differently. ...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 Equal temperament is a scheme of musical tuning in which the octave is divided into a series of equal steps (equal frequency ratios). ...equally tempered scale, especially in Twelve_tone technique is a system of musical composition devised by Arnold Schoenberg. ...twelve tone music. In visual art modular arithmetic can be used to create artistic patterns based on the multiplication and addition tables modulo n (see link below).
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.
External link - Modular Art (http://ccins.camosun.bc.ca/~jbritton/modart/jbmodart.htm)
|
Feeds |
Contact