Modular arithmetic

The formula

The whole subject rests on one definition:

a ≡ b (mod n)   ⇔   n divides (a − b)

Read: a and b are "the same number" as far as n is concerned — they leave the same remainder. 38 ≡ 14 (mod 12) because 38 − 14 = 24, and a 12-hour clock genuinely cannot tell 38 o'clock from 14 o'clock.

The rule that makes it useful in a machine:

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n

Read: reduce early, reduce often. Reduced operands stay below n, which is how a streaming checksum runs over a gigabyte file in a single register. One caveat: the product of two reduced residues can reach (n−1)² before you reduce it, so the multiply itself needs double-width headroom — do (a*b) % n with 32-bit residues in a 32-bit register and the overflow is silent and the checksum is wrong.

Every N-bit unsigned integer in every processor you own obeys:

result = (true result) mod 2^N

Read: fixed-width binary arithmetic is not an approximation of integer arithmetic that sometimes "overflows" — it is exact arithmetic mod 2^N, all the time.

Two theorems carry all of public-key cryptography. Fermat, for prime p and a not divisible by p:

a^(p−1) ≡ 1 (mod p)

and Euler's generalization to any modulus, where φ(n) counts the integers below n sharing no factor with it:

a^φ(n) ≡ 1 (mod n)     when gcd(a, n) = 1

Read: raise a number to a high enough power mod n and it cycles back to 1 — exponents themselves behave "mod φ(n)", which is the trapdoor RSA is built on.

Where you meet it

The soak test that fails on day 50. A 32-bit free-running millisecond counter wraps at 2^32 ms ≈ 49.7 days. Firmware that computes elapsed time as if (now > then) dies at the wrap; firmware that computes (uint32_t)(now − then) survives it, because unsigned subtraction is already arithmetic mod 2^32 and gives the right elapsed count straight across the rollover. Half the "reboot it every month" folklore in fielded test equipment traces to somebody getting this wrong in 1998.
The DDS on your RF bench. A direct digital synthesizer is nothing but a phase accumulator adding a tuning word every clock, mod 2^32: f_out = FTW · f_clk / 2^32. The wraparound isn't a defect — the wrap is the cycle of the sine wave. Same story for NCOs in every SDR and every phase-continuous frequency hop you've ever tested.
Sequence counters in telemetry. The CCSDS space packet header carries a 14-bit sequence count that wraps mod 16384. Gap detection on the ground is a modular difference, and the frame-accounting review question — "how do you know you dropped two packets and not 16386?" — is a question about the modulus.
Checksums at the design review. ISBN check digits work mod 11, credit-card Luhn digits mod 10, IBAN validation mod 97, and a CRC is long division of polynomials whose coefficients are handled mod 2. When the board asks how the link detects a corrupted word, the answer is modular arithmetic wearing four different badges. And every TLS session on the test network runs RSA or Diffie-Hellman underneath — modular exponentiation with 2048-bit numbers, thousands of times a second.

How it works

Mod n sorts every integer into one of n buckets by remainder. The theorems above say addition and multiplication respect the buckets — you can reduce any intermediate result at any time and the final answer doesn't change. That license is the entire trick. The IBAN mod-97 check runs over a 30-digit number no register can hold by carrying only the running remainder; a CRC engine holds 16 or 32 bits of state over an unbounded message for the same reason.

What does not respect the buckets is division. 4·2 ≡ 4·5 (mod 12) — both sides are 8 — yet 2 ≢ 5 (mod 12). You cancelled a 4, and 4 shares a factor with 12. A factor can only be cancelled, and an inverse a⁻¹ with a·a⁻¹ ≡ 1 (mod n) only exists, when gcd(a, n) = 1. Mod 7, the inverse of 3 is 5 (15 ≡ 1); mod 12, the number 4 has no inverse at all. The extended Euclidean algorithm finds inverses when they exist, and prime moduli are popular precisely because everything nonzero is invertible there.

The mistake people actually make: the % operator in C, C++, and most C descendants is remainder, not mathematical mod. C truncates toward zero, so -7 % 3 is -1 in C and +2 in Python. Wrap a buffer index or an angle with a possibly-negative operand in C and you index one element off the front of the array — a bug that only fires when the encoder runs backward through zero, which is to say, only during the demo. The portable fix is ((x % n) + n) % n.

Three more things worth knowing before you lean on it:

Power-of-two moduli are free. x mod 2^k is x & (2^k − 1), one AND gate. Any other modulus costs a divide. This is why ring buffers, FIFOs, and hash tables are sized in powers of two, and why hardware counters wrap where they wrap.
Never compute the big number first. 7^1000000007 mod 13 is 2, reachable in about thirty squarings by reducing after every multiply (square-and-multiply, pow(a, b, n) in Python). Computing 7^1000000007 and then reducing is not slow — it is impossible.
Wraparound ordering has a horizon. Two counter values can only be ordered if they're within half the modulus of each other; (uint16_t)(a − b) < 32768 means a is ahead, otherwise behind — and at exactly half the range the question has no answer. Sequence-number comparison in protocols lives inside this half-modulus window, and so does your dropped-frame accounting.
The Chinese remainder theorem stitches moduli together. Know a number mod 3, mod 5, and mod 7, and you know it mod 105 exactly. RSA implementations use it to work mod two primes separately instead of mod their product, which is markedly faster — and it's the right tool any time two counters with coprime periods have to be reconciled.

History

The oldest surviving statement of the subject is a word problem. The Sunzi Suanjing, a Chinese text dated somewhere between the 3rd and 5th centuries, asks for a number that leaves remainder 2 counted by threes, 3 by fives, and 2 by sevens — answer 23 — and this is the problem the Chinese remainder theorem is named for ^[1]^[2]. In 1247 Qin Jiushao's Shushu Jiuzhang gave a general procedure for such systems, handling even moduli that share factors, centuries before anyone in Europe had a method ^[1]^[3].

Europe came at it through primes. On 18 October 1640, Pierre de Fermat wrote to Bernard Frénicle de Bessy stating what we now call his little theorem — that p divides a^(p−1) − 1 for prime p — and, characteristically, did not include the proof ^[4]^[5]. Euler later took the result further, introducing the totient function φ(n) and extending the theorem to arbitrary moduli ^[4]^[6].

The subject became a discipline in 1801, when Carl Friedrich Gauss — who had written the manuscript at 21 — published the Disquisitiones Arithmeticae and opened it by defining congruence, coining the term modulus, and introducing the three-bar ≡ notation still in use ^[7]^[8]^[9]. An English reviewer in 1808 grumbled that he could not "forbear expressing our wish that M. Gauss had not been tempted into the invention of new names and new signs" ^[9]. The names and signs won.

The engineering payoff took another 177 years. In 1977 Ron Rivest, Adi Shamir, and Leonard Adleman built a public-key cryptosystem directly on Euler's theorem — pick e·d ≡ 1 (mod φ(n)) and (x^e)^d ≡ x (mod n) follows — published in the Communications of the ACM in February 1978 ^[10]^[11]. Gauss's clock arithmetic now authenticates essentially every encrypted link on the planet.

Related tools

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →