Modular arithmetic
The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods.
Similarly, 8:00 represents a period of 8 hours, and twice this would give 16:00, which reads as 4:00 on the clock face, written as 2 × 8 ≡ 4 (mod 12).
Congruence modulo m is denoted The parentheses mean that (mod m) applies to the entire equation, not just to the right-hand side (here, b).
The congruence relation may be rewritten as explicitly showing its relationship with Euclidean division.
We recover the previous relation (a − b = k m) by subtracting these two expressions and setting k = p − q.
The modular multiplicative inverse is defined by the following rules: The multiplicative inverse x ≡ a−1 (mod m) may be efficiently computed by solving Bézout's equation a x + m y = 1 for x, y, by using the Extended Euclidean algorithm.
Each residue class modulo m contains exactly one integer in the range
Some other complete residue systems modulo 4 include: Some sets that are not complete residue systems modulo 4 are: Given the Euler's totient function φ(m), any set of φ(m) integers that are relatively prime to m and mutually incongruent under modulus m is called a reduced residue system modulo m.[5] The set {5, 15} from above, for example, is an instance of a reduced residue system modulo 4.
for some m.[8] The ring of integers modulo m is a field if and only if m is prime (this ensures that every nonzero element has a multiplicative inverse).
If m = pk is a prime power with k > 1, there exists a unique (up to isomorphism) finite field
A very practical application is to calculate checksums within serial number identifiers.
Likewise, International Bank Account Numbers (IBANs), for example, make use of modulo 97 arithmetic to spot user input errors in bank account numbers.
In cryptography, modular arithmetic directly underpins public key systems such as RSA and Diffie–Hellman, and provides finite fields which underlie elliptic curves, and is used in a variety of symmetric key algorithms including Advanced Encryption Standard (AES), International Data Encryption Algorithm (IDEA), and RC4.
In computer algebra, modular arithmetic is commonly used to limit the size of integer coefficients in intermediate calculations and data.
It is used in polynomial factorization, a problem for which all known efficient algorithms use modular arithmetic.
It is used by the most efficient implementations of polynomial greatest common divisor, exact linear algebra and Gröbner basis algorithms over the integers and the rational numbers.
As posted on Fidonet in the 1980s and archived at Rosetta Code, modular arithmetic was used to disprove Euler's sum of powers conjecture on a Sinclair QL microcomputer using just one-fourth of the integer precision used by a CDC 6600 supercomputer to disprove it two decades earlier via a brute force search.
The modulo operation, as implemented in many programming languages and calculators, is an application of modular arithmetic that is often used in this context.
The use of long division to turn a fraction into a repeating decimal in any base b is equivalent to modular multiplication of b modulo the denominator.
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).
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).
Arithmetic modulo 7 is used in algorithms that determine the day of the week for a given date.
In particular, Zeller's congruence and the Doomsday algorithm make heavy use of modulo-7 arithmetic.
More generally, modular arithmetic also has application in disciplines such as law (e.g., apportionment), economics (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.
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.
Algorithms, such as Montgomery reduction, also exist to allow simple arithmetic operations, such as multiplication and exponentiation modulo m, to be performed efficiently on large numbers.
Some operations, like finding a discrete logarithm or a quadratic congruence appear to be as hard as integer factorization and thus are a starting point for cryptographic algorithms and encryption.
Solving a system of non-linear modular arithmetic equations is NP-complete.
