Modular arithmetic explained

Everyone already does modular arithmetic: 10 hours after 8 o'clock is 6 o'clock, and the day after Sunday is Monday. Counting that starts again from 0 after n steps turns out to have its own complete arithmetic, with rules, surprises and a central place in number theory and in the cryptography that protects the internet.

A clock with twelve positions numbered 0 to 11 and a spiral path that winds once round the dial from 9 to 2
A clock with twelve positions numbered 0 to 11 and a spiral path that winds once round the dial from 9 to 2

Remainders and congruence

Divide a by n and keep only the remainder: that is a mod n, a number from 0 to n − 1. 26 mod 7 = 5, because 26 = 3 × 7 + 5. Numbers with the same remainder behave the same way mod n, so we call them congruent: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss introduced this notation in his Disquisitiones Arithmeticae of 1801, and it made the old observations of Fermat and Euler into an arithmetic of its own. On a clock with n positions, every whole number lands on its remainder; the full turns are forgotten.

Carl Friedrich Gauss, in an 1840 portrait by Christian Albrecht Jensen. He introduced the congruence notation a ≡ b (mod n) in his Disquisitiones Arithmeticae of 1801.
Carl Friedrich Gauss, in an 1840 portrait by Christian Albrecht Jensen. He introduced the congruence notation a ≡ b (mod n) in his Disquisitiones Arithmeticae of 1801.

Adding, subtracting and multiplying

The three ordinary operations work as usual, and you may reduce mod n whenever you like: the remainder of a sum is the remainder of the sum of the remainders, and the same goes for differences and products. To find the last digit of 37 × 48, multiply only the last digits: 7 × 8 = 56, so it ends in 6. This is what makes modular arithmetic so useful for computers: however large the numbers, the working values never exceed n².

Division needs an inverse

Division is the exception. 2 × 3 ≡ 2 × 8 (mod 10), since both are 6 mod 10, yet 3 and 8 are different, so you cannot simply cancel the 2. Dividing by a means multiplying by its inverse, the number x with a × x ≡ 1, and that exists exactly when a and n have no common factor. The extended Euclidean algorithm finds it: it runs Euclid's division steps for the greatest common divisor and keeps track of a multiplier at each step, so that when the remainder reaches 1, the multiplier is the inverse. When n is prime, every number except 0 has an inverse, and division always works.

Powers, Fermat and Euler

Powers repeat. Take the powers of 3 mod 7: 3, 2, 6, 4, 5, 1, and then 3 again. The length of that cycle is the order of 3. In 1640 Pierre de Fermat noticed that for a prime p, a^(p − 1) ≡ 1 (mod p) whenever p does not divide a, so every order divides p − 1. Leonhard Euler proved it and extended it to any n, with p − 1 replaced by the number of values coprime to n. Huge powers are computed by repeated squaring: a, a², a⁴, a⁸ … each the square of the one before, reduced mod n, then multiplied for the binary digits of the exponent.

Portrait of Pierre de Fermat
Portrait of Pierre de Fermat
Portrait of Leonhard Euler
Portrait of Leonhard Euler

Check digits and calendars

Modular arithmetic catches mistakes. The last digit of an ISBN-10 is chosen so that a weighted sum of all ten digits is a multiple of 11, so any single wrong digit and any swap of two neighbours is detected. Bank card numbers use the Luhn check mod 10, and IBANs a check mod 97. Calendars run mod 7: the weekday of any date can be worked out with a few remainders, which is how perpetual calendars and the doomsday rule work.

Cryptography

Modern cryptography is built on modular powers that are easy to compute and hard to undo. In the Diffie–Hellman key exchange of 1976, two people agree on a shared secret over an open line by exchanging powers mod a large prime. RSA, published in 1977 by Rivest, Shamir and Adleman, encrypts a message m as m^e mod n, where n is the product of two large primes, and decrypts with a second exponent d that only someone who knows the two primes can compute. In the textbook example, n = 3233 = 61 × 53, e = 17 and d = 413: 65 becomes 2790, and 2790 becomes 65 again.

Explore it

Open the modular clock to compute a mod n, sums, differences, products, powers, inverses and quotients mod n, for numbers of up to 30 digits. Every answer comes with its steps: the division with remainder, the powers from repeated squaring, or the table of the extended Euclidean algorithm. The clock draws how the answer is reached, from the spiral of an addition to the cycle of powers, and for small n the table of the operation shows all the answers at once.

Frequently asked questions

What does the symbol ≡ mean?

a ≡ b (mod n) says that a and b leave the same remainder when divided by n, or equivalently that n divides a − b. 38 ≡ 2 (mod 12), because 38 − 2 = 36 is a multiple of 12.

Is mod the same as the % operator in programming?

For positive numbers, yes. For negative numbers many languages, such as C, Java and JavaScript, return a negative remainder: −7 % 3 is −1 there, while −7 mod 3 = 2. Python's % follows the mathematical convention for a positive n.

What is the order of a number mod n?

The smallest k > 0 with a^k ≡ 1 (mod n). It exists only when a and n have no common factor. The order of 2 mod 7 is 3, because 2³ = 8 ≡ 1, and the order of 3 mod 7 is 6, so the powers of 3 run through every nonzero remainder: 3 is a primitive root mod 7.

Who invented modular arithmetic?

Remainders were used long before, for example in the Chinese remainder theorem from the 3rd to 5th century, and by Fermat and Euler. Gauss made it a systematic arithmetic, with the notation of congruences, in 1801.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the modular clock