**Modular arithmetic** (sometimes called **modulo arithmetic**, or **clock arithmetic** because of its use in the 24-hour clock system) 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. Arithmetic or arithmetics (from the Greek word Î±ÏÎ¹Î¸Î¼ÏŒÏ‚ = number) is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple daily counting to advanced science and business calculations. ...
The integers are commonly denoted by the above symbol. ...
(30 April 1777 â€“ 23 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including number theory, analysis, differential geometry, geodesy, magnetism, astronomy, and optics. ...
The Disquisitiones Arithmeticae is a textbook of number theory written by German mathematician Carl Friedrich Gauss and first published in 1801 when Gauss was 24. ...
A familiar use of modular arithmetic is its use in the 24-hour clock: the arithmetic of time-keeping in which the day runs from midnight to midnight and is divided into 24 hours, numbered from 0 to 23. If the time is noted at 7 o'clock in the evening — 19:00 in the 24-hour system — and then again 8 hours later, then rather than the time being 27:00 (as in usual addition: 19 + 8 = 27), the time will actually be denoted as 03:00, albeit in the next day. Likewise, if the clock starts at noon (12:00) and 21 hours elapse, then the time will be 09:00 the next day, rather than 33:00 (as in usual addition). Since the hour number starts over at 00 hours after passing 23 hours, this is arithmetic *modulo* 24 — the hours "wrap around" upon reaching the modulus 24. The 24-hour clock is a convention of time-keeping in which the day runs from midnight to midnight and is divided into 24 hours, numbered from 0 to 23. ...
## The congruence relation
Modular arithmetic can be handled mathematically by introducing a congruence relation on the integers that is compatible with the operations of the ring of integers: addition, subtraction, and multiplication. For a fixed modulus *n*, it is defined as follows. In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ...
The integers are commonly denoted by the above symbol. ...
In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ...
3 + 2 = 5 with apples, a popular choice in textbooks[1] Addition is the mathematical operation of combining or adding two numbers to obtain an equal simple amount or total. ...
5 - 2 = 3 Subtraction is one of the four basic arithmetic operations; it is essentially the opposite of addition. ...
In mathematics, multiplication is an elementary arithmetic operation. ...
Two integers *a* and *b* are said to be **congruent** **modulo** *n*, if their difference (a−b) is an integer multiple of *n*. If this is the case, it is expressed as: A multiple of a number is the product of that number with any integer. ...
The above mathematical statement is read: "*a* is congruent to *b* **modulo** *n*". For example, because 38 − 14 = 24, which is a multiple of 12. For positive *n* and non-negative *a* and *b*, congruence of *a* and *b* can also be thought of as asserting that these two numbers have the same remainder after dividing by the modulus *n*. So, 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. ...
because, when divided by 12, both numbers give 2 as remainder. A remark on the notation: Because it is common to consider several congruence relations for different moduli at the same time, the modulus is incorporated in the notation. In spite of the ternary notation, the congruence relation for a given modulus is binary. This would have been clearer if the notation *a* ≡_{n} *b* had been used, instead of the common traditional notation. In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...
The properties that make this relation a congruence relation (respecting addition, subtraction, and multiplication) are the following. If and , then: ## The ring of congruence classes Like any congruence relation, congruence modulo *n* is an equivalence relation, and the equivalence class of the integer *a*, denoted by , is the set . This set, consisting of the integers congruent to *a* modulo *n*, is called the **congruence class** or **residue class** of *a* modulo *n*. Another notation for this congruence class, which requires that in the context the modulus is known, is . In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ...
In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x âˆˆ X | x ~ a } The notion of equivalence classes is useful for constructing sets out...
The set of congruence classes modulo *n* is denoted as and defined by: When *n* ≠ 0, has *n* elements, and can be written as: When *n* = 0, does not have zero elements; rather, it is isomorphic to , since . In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...
We can define addition, subtraction, and multiplication on by the following rules: The verification that this is a proper definition uses the properties given before. In this way, becomes a commutative ring. For example, in the ring , we have In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ...
as in the arithmetic for the 24-hour clock. The notation is used, because it is the factor ring of by the ideal containing all integers divisible by *n*, where is the singleton set . In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...
In mathematics, a singleton is a set with exactly one element. ...
In terms of groups, the residue class is the coset of *a* in the quotient group , a cyclic group. 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...
In mathematics, given a group G and a normal subgroup N of G, the quotient group, or factor group, of G over N is intuitively a group that collapses the normal subgroup N to the identity element. ...
In group theory, 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, when written multiplicatively, every element of the group is a power of a (or na...
The set has a number of important mathematical properties that are foundational to various branches of mathematics. Rather than excluding the special case *n* = 0, it is more useful to include (which, as mentioned before, is isomorphic to the ring of integers), for example when discussing the characteristic of a ring. In mathematics, the characteristic of a ring R with identity element 1R is defined to be the smallest positive integer n such that n1R = 0, where n1R is defined as 1R + ... + 1R with n summands. ...
In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ...
## 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. 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. ...
In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication. ...
In computing, the modulo operation finds the remainder of division of one number by another. ...
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
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. In arithmetic, long division is a procedure for calculating the division of one integer, called the dividend, by another integer called the divisor, to produce a result called the quotient. ...
## Applications Modular arithmetic is referenced in number theory, group theory, ring theory, abstract algebra, cryptography, computer science, chemistry and the visual and musical arts. Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ...
Group theory is that branch of mathematics concerned with the study of groups. ...
In mathematics, ring theory is the study of rings, algebraic structures in which addition and multiplication are defined and have similar properties to those familiar from the integers. ...
Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ...
The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek ÎºÏÏ…Ï€Ï„ÏŒÏ‚ kryptÃ³s hidden, and the verb Î³ÏÎ¬Ï†Ï‰ grÃ¡fo write) is the study of message secrecy. ...
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
This article or section includes a list of works cited or a list of external links, but its sources remain unclear because it lacks in-text citations. ...
The Mona Lisa is one of the most recognizable artistic paintings in the Western world. ...
For other uses, see Music (disambiguation). ...
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 a variety of symmetric key algorithms including AES, IDEA, and RC4. This article or section does not adequately cite its references or sources. ...
In cryptology, RSA is an algorithm for public-key encryption. ...
Diffie-Hellman (D-H) key exchange is a cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. ...
In abstract algebra, a finite field or Galois field (so named in honor of Ã‰variste Galois) is a field that contains only finitely many elements. ...
In mathematics, an elliptic curve is a plane curve defined by an equation of the form y2 = x3 + a x + b, which is non-singular; that is, its graph has no cusps or self-intersections. ...
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related cryptographic keys for both decryption and encryption. ...
In cryptography, the Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the U.S. government. ...
In cryptography, the International Data Encryption Algorithm (IDEA) is a block cipher designed by Xuejia Lai (ä¾†å¸å˜‰) and James L. Massey of ETH Zurich and was first described in 1991. ...
In cryptography, RC4 (also known as ARC4 or ARCFOUR) is the most widely-used software stream cipher and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP (to secure wireless networks). ...
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 computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...
A binary tree, a simple type of branching linked data structure. ...
In computing, the modulo operation finds the remainder of division of one number by another. ...
A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...
A calculator is a device for performing calculations. ...
In chemistry, the last digit of the CAS registry number (a number which is unique for each chemical compound) is a check digit, which is calculated by taking the last digit of the first two parts of the CAS registry number times 1, the next digit times 2, the next digit times 3 etc., adding all these up and computing the sum modulo 10. CAS registry numbers are unique numerical identifiers for chemical compounds, polymers, biological sequences, mixtures and alloys. ...
A check digit is a form of redundancy check used for error detection, the decimal equivalent of a binary checksum. ...
CAS registry numbers are unique numerical identifiers for chemical compounds, polymers, biological sequences, mixtures and alloys. ...
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, arithmetic modulo 12 is used in the consideration of the system of twelve-tone equal temperament, where octave and enharmonic equivalency occurs (that is, pitches in a 1∶2 or 2∶1 ratio are equivalent, and C-sharp is considered the same as D-flat). An equal temperament is a musical temperament â€” that is, a system of tuning intended to approximate some form of just intonation â€” in which an interval, usually the octave, is divided into a series of equal steps (equal frequency ratios). ...
In music, an octave (sometimes abbreviated 8ve or 8va) is the interval between one musical note and another with half or double the frequency. ...
In music, an enharmonic is a note which is the equivalent of some other note, but spelled differently. ...
The word sharp or acronym SHARP has several uses: Look up sharp in Wiktionary, the free dictionary. ...
Figure 1. ...
The method of casting out nines offers a quick check of decimal arithmetic computations performed by hand. It is based on modular arithmetic modulo 9, and specifically on the crucial property that 10 ≡ 1 (**mod** 9). Casting out nines is a sanity check of the validity of hand computations on integer numbers using +,-,×. It is based on modular arithmetic. ...
More generally, modular arithmetic also has application in disciplines such as law (see e.g., apportionment), economics, (see e.g., game theory) and other areas of the social sciences, where proportional division and allocation of resources plays a central part of the analysis. Lady Justice or Justitia is a personification of the moral force that underlies the legal system (particularly in Western art). ...
The membership of the United States House of Representatives changes each decade following the decennial United States Census. ...
Face-to-face trading interactions on the New York Stock Exchange trading floor. ...
Game theory is often described as a branch of applied mathematics and economics that studies situations where players choose different actions in an attempt to maximize their returns. ...
This article or section does not adequately cite its references or sources. ...
In problems of fair division, and allocation is proportional if, in a game of players, each player believes he or she received at least of the cake. ...
Some neurologists (see e.g., Oliver Sacks) theorize that so-called autistic savants utilize an "innate" modular arithmetic to compute such complex problems as what day of the week a distant date will fall on. Oliver Sacks Oliver Wolf Sacks (born July 9, 1933, London) is a neurologist who has written popular books about his patients. ...
An autistic savant (historically described as idiot savant) is a person with both autism and Savant Syndrome [1]. Savant Syndrome describes a person having both a severe developmental or mental handicap and extraordinary mental abilities not found in most people. ...
## Computational complexity Since modular arithmetic has such a wide range of applications, it is important to know how hard it is to solve a system of congruences. A linear system of congruences can be solved in polynomial time with a form of Gaussian elimination, for details see the linear congruence theorem. In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
In mathematics, Gaussian elimination (not to be confused with Gaussâ€“Jordan elimination), named after Carl Friedrich Gauss, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ...
In modular arithmetic, the question of when a linear congruence can be solved is answered by the linear congruence theorem. ...
Solving a system of non-linear modular arithmetic equations is NP-complete. For details, see for example M. R. Garey, D. S. Johnson: *Computers and Intractability, a Guide to the Theory of NP-Completeness*, W. H. Freeman 1979. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
## See also In mathematics, a number q is called a quadratic residue modulo p if there exists an integer x such that: Otherwise, q is called a quadratic non-residue. ...
The Legendre symbol is a number theory concept. ...
In number theory, the law of quadratic reciprocity connects the solvability of two related quadratic equations in modular arithmetic. ...
A primitive root modulo n is a concept from modular arithmetic in number theory. ...
In abstract algebra, a finite field or Galois field (so named in honor of Ã‰variste Galois) is a field that contains only finitely many elements. ...
In group theory, 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, when written multiplicatively, every element of the group is a power of a (or na...
In mathematics, the multiplicative group of integers modulo n is the group defined by multiplication of the units (that is, the numbers relatively prime to ) in the ring for a given integer . ...
In number theory, Eulers theorem (also known as the Fermat-Euler theorem or Eulers totient theorem) states that if n is a positive integer and a is coprime to n, then aÏ†(n) â‰¡ 1 (mod n) where Ï†(n) is Eulers totient function and mod denotes the congruence...
Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you start with a number, initialized to 1, and repeatedly multiply, for a total of p multiplications, that number by...
Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem. ...
Lagranges theorem, in the mathematics of group theory, 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. It is named after Joseph Lagrange. ...
## References Tom Apostol is an analytic number theorist who teaches at California Institute of Technology. ...
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ...
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ...
Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...
Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...
## External links |