The Mathematics of Modular Arithmetic

What's the last digit of 3¹⁰⁰? The full number has 48 digits, far beyond what a pocket calculator shows. But you can find the last digit in your head in about ten seconds.

The trick is modular arithmetic, the mathematics of remainders. It's the reason your credit card number can catch typos, the reason ISBNs have check digits, and the foundation of the encryption behind every secure website.

You Can Throw Away Almost All of a Number and Still Get the Right Answer

Normally, to compute something about a huge number, you need the huge number. Modular arithmetic says: if you only care about the remainder, you can reduce at every step and never deal with large values.

Watch the last digits of powers of 3:

3¹ = 3
3² = 9
3³ = 27   → 7
3⁴ = 81   → 1
3⁵ = 243  → 3   (the cycle repeats)

The last digits cycle 3, 9, 7, 1 with period 4. Since 100 is divisible by 4, the last digit of 3¹⁰⁰ is the same as that of 3⁴: 1. No 48-digit number required.

Congruence: The Core Idea

We say a is congruent to b modulo n, written:

a ≡ b (mod n)

if a and b leave the same remainder when divided by n. Equivalently, n divides a − b.

17 ≡ 2 (mod 5)     because 17 − 2 = 15 is divisible by 5
38 ≡ 14 (mod 12)   because 38 − 14 = 24 is divisible by 12
−1 ≡ 6 (mod 7)     because −1 − 6 = −7 is divisible by 7

The notation was introduced by Carl Friedrich Gauss in his 1801 book Disquisitiones Arithmeticae, written when he was 21. It turned a collection of tricks into a systematic branch of mathematics.

The Rules That Make It Work

If a ≡ b and c ≡ d (mod n), then:

a + c ≡ b + d   (mod n)
a − c ≡ b − d   (mod n)
a × c ≡ b × d   (mod n)
aᵏ ≡ bᵏ         (mod n)

That means you can reduce before you add, subtract, multiply or raise to powers. The answer's remainder stays the same. This is exactly why the divisibility rule for 9 works: 10 ≡ 1 (mod 9), so every power of 10 is ≡ 1, and a number is ≡ its digit sum (mod 9). See the rules on the number theory formulas page.

Division Is Different

Division is the one operation that doesn't carry over automatically. In ordinary arithmetic, dividing by 3 means multiplying by 1/3. In modular arithmetic, you need a modular inverse: a number x with

3x ≡ 1 (mod 7)

Try values: 3 × 5 = 15 = 2 × 7 + 1. So 5 is the inverse of 3 mod 7.

An inverse of a exists mod n only when gcd(a, n) = 1. For example, 2 has no inverse mod 6, because 2x is always even and can never be 1 more than a multiple of 6. When n is prime, every non-zero number has an inverse. Check common factors with the GCF calculator.

Fermat's Little Theorem

In 1640, Pierre de Fermat stated a result that now underpins primality testing and cryptography:

If p is prime and a is not divisible by p, then  a^(p−1) ≡ 1 (mod p)

For example, with p = 7 and a = 3: 3⁶ = 729 = 104 × 7 + 1. ✓

This makes huge powers easy. What's 3¹⁰⁰ mod 7? Since 3⁶ ≡ 1, and 100 = 16 × 6 + 4:

3¹⁰⁰ = (3⁶)¹⁶ × 3⁴ ≡ 1 × 81 ≡ 4 (mod 7)

Read more about Fermat in Pierre de Fermat: The Enigmatic Prince of Number Theory.

An Insider Reference: The Chinese Remainder Theorem

A problem from the Chinese text Sunzi Suanjing, written sometime between the 3rd and 5th centuries AD, asks:

There are certain things whose number is unknown. Counted by threes, 2 remain. Counted by fives, 3 remain. Counted by sevens, 2 remain. How many things are there?

In modern notation:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

The smallest answer is 23. The Chinese remainder theorem guarantees that when the moduli share no common factors, there's exactly one solution modulo their product (here 3 × 5 × 7 = 105). So 23, 128, 233, … all work. The LCM calculator finds that combined period.

Today the theorem is used to speed up RSA decryption by roughly a factor of four, and to perform arithmetic on very large numbers in parallel.

Where Modular Arithmetic Protects You

ISBN Check Digits

A 13-digit ISBN multiplies its digits alternately by 1 and 3, and the check digit makes the total ≡ 0 (mod 10). For 978-0-306-40615-?, the weighted sum of the first 12 digits is 93, so the check digit is 7 (93 + 7 = 100).

Credit Card Numbers

The Luhn algorithm, patented by IBM scientist Hans Peter Luhn in 1960, doubles every second digit and checks that the total is ≡ 0 (mod 10). It catches every single-digit typo and most swaps of adjacent digits.

Cryptography and Hashing

RSA, Diffie–Hellman and elliptic curve cryptography all do their arithmetic mod large numbers. Hash tables use mod to map keys into a fixed number of slots.

Two Concepts Worth Knowing

Residue Classes

Mod n, every integer falls into one of n residue classes: those with remainder 0, 1, …, n − 1. Arithmetic mod n is arithmetic on these classes.

Cyclic Groups

The numbers 0 through n − 1 under addition mod n form a cyclic group, one of the simplest structures in abstract algebra. It's the mathematical model for anything that wraps around.

Quick Answer: What Is Modular Arithmetic?

Modular arithmetic is arithmetic with remainders, where numbers wrap around after reaching a modulus n. Two numbers are congruent mod n if they have the same remainder when divided by n. Addition, subtraction and multiplication can be done on remainders, which makes it possible to work with huge numbers and underpins check digits and cryptography.

Try Them Yourself

• Number Theory Formulas: congruence rules and theorems
• GCF Calculator: check whether a modular inverse exists
• LCM Calculator: combine periods in the Chinese remainder theorem
• Division Tables: quotients and remainders
• Number 23: the answer to Sunzi's puzzle
• Real-Life Uses of LCM and GCF: more practical number theory

Find the last digit of 7²⁰²⁶ in your head. (Hint: the last digits of powers of 7 cycle with period 4.)