What Is Modular Arithmetic? Counting That Wraps Around
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Adding four hours to eleven o'clock gives three, not fifteen, because the clock wraps. Formalising that idea produces a system of arithmetic on remainders that underpins error detection, cryptography, calendars and a substantial part of number theory.
The basic idea
Two numbers are congruent modulo some value if they leave the same remainder when divided by it, so seventeen and five are congruent modulo twelve since both leave five. Arithmetic then proceeds on the remainders, and the key fact is that addition, subtraction and multiplication all behave properly, meaning that the remainder of a sum is the sum of the remainders reduced again, so calculations can be done entirely in the small set of possible remainders rather than on the original numbers. Division is the exception and is where the subject becomes interesting, since dividing is only possible when the divisor shares no factor with the modulus, and when the modulus is prime every non-zero remainder has an inverse, which makes the system behave like ordinary arithmetic in a finite setting. That distinction between prime and composite moduli is not a technicality, since almost every application depends on which case applies.
Where it turns up
The applications are numerous and mostly invisible:
- •Clocks and calendars, which are modular by construction, with days of the week working modulo seven and the whole apparatus of leap years being a modular calculation
- •Check digits, including those on bank account numbers, book identifiers and payment cards, which detect most single-digit errors and transpositions by requiring a weighted sum to come out to a fixed remainder
- •Cryptography, since public key methods rest on operations that are easy in one direction and hard to reverse within modular arithmetic, with RSA depending on the difficulty of factoring and on a theorem about exponents modulo a product of primes
- •Hash functions and data structures, which map arbitrary keys into a fixed number of buckets by taking a remainder
- •Random number generation, where linear congruential generators multiply and add modulo a large number to produce a sequence
- •Error-correcting codes, which are built on arithmetic in finite systems of exactly this kind
The theorems that make it work
A small number of results do most of the heavy lifting. Fermat's little theorem states that raising any number not divisible by a prime to the power one less than that prime gives a remainder of one, which constrains how exponents behave and is the foundation of several primality tests. Euler's generalisation extends it to composite moduli using a count of how many numbers below the modulus share no factor with it, and that generalisation is precisely what makes public key encryption work. The Chinese remainder theorem states that a system of congruences with pairwise coprime moduli has a unique solution modulo their product, which was known in Chinese mathematics by the third century and which is used constantly in computation to break a large calculation into several small ones performed in parallel. Together these turn a simple idea about remainders into a substantial and practically indispensable body of technique.
Why it suits computers
Computers work in modular arithmetic whether or not anyone intends it. A fixed-width integer has a limited range, and exceeding it wraps around, which is arithmetic modulo a power of two and which is the cause of overflow bugs when the wrapping is unintended. That behaviour has produced serious failures, including a rocket destroyed shortly after launch when a conversion overflowed and the aircraft that had to be restarted periodically because a counter would overflow after a number of days of continuous operation. Cryptographic implementations rely on modular arithmetic deliberately and must guard against side channels, since the time a modular operation takes can leak information about the values involved, which has been exploited in practice. Hashing distributes keys by taking remainders, and choosing a modulus badly clusters the results, which is why prime table sizes are recommended. Understanding the wrapping is therefore practical rather than theoretical, since it is happening constantly beneath any program.
The takeaway
Working with remainders keeps addition, subtraction and multiplication well behaved, and division works only when the divisor shares no factor with the modulus, which is why prime moduli are special. Check digits, hashing, calendars and public key encryption all rest on it. Fixed-width computer integers wrap by construction, so overflow bugs are modular arithmetic happening without anyone asking for it.