Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers 'wrap around' upon reaching a certain value—the modulus (plural moduli). The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.Modular arithmetic can be handled mathematically by introducing a congruence relation on the integers that is compatible with the operations on integers: addition, subtraction, and multiplication. For a positive integer n, two numbers a and b are said to be congruent modulo n, if their difference a − b is an integer multiple of n (that is, if there is an integer k such that a − b = kn). This congruence relation is typically considered when a and b are integers, and is denoted The congruence relation satisfies all the conditions of an equivalence relation:Like any congruence relation, congruence modulo n is an equivalence relation, and the equivalence class of the integer a, denoted by an, is the set {… , a − 2n, a − n, a, a + n, a + 2n, …}. This set, consisting of the integers congruent to a modulo n, is called the congruence class or residue class or simply residue of the integer a, modulo n. When the modulus n is known from the context, that residue may also be denoted .Each residue class modulo n may be represented by any one of its members, although we usually represent each residue class by the smallest nonnegative integer which belongs to that class (since this is the proper remainder which results from division). Any two members of different residue classes modulo n are incongruent modulo n. Furthermore, every integer belongs to one and only one residue class modulo n.The set of all congruence classes of the integers for a modulus n is called the ring of integers modulo n, and is denoted Z / n Z {displaystyle mathbb {Z} /nmathbb {Z} }  , Z / n {displaystyle mathbb {Z} /n}  , or Z n {displaystyle mathbb {Z} _{n}}  . The notation Z n {displaystyle mathbb {Z} _{n}}   is, however, not recommended because it can be confused with the set of n-adic integers. The ring Z / n Z {displaystyle mathbb {Z} /nmathbb {Z} }   is fundamental to various branches of mathematics (see Applications below).In theoretical mathematics, modular arithmetic is one of the foundations of number theory, touching on almost every aspect of its study, and it is also used extensively in group theory, ring theory, knot theory, and abstract algebra. In applied mathematics, it is used in computer algebra, cryptography, computer science, chemistry and the visual and musical arts.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 linear congruence theorem. Algorithms, such as Montgomery reduction, also exist to allow simple arithmetic operations, such as multiplication and exponentiation modulo n, to be performed efficiently on large numbers.Below are three reasonably fast C functions, two for performing modular multiplication and one for modular exponentiation on unsigned integers not larger than 63 bits, without overflow of the transient operations.