Number Theory · Beginner · 8 min read

Modular Arithmetic for Beginners

Modular arithmetic is the arithmetic of remainders, and it is the language of number theory and cryptography. If you can read a clock, you already understand the central idea.

Congruence

We say a ≡ b (mod m) when m divides a − b, which means a and b leave the same remainder after division by m. On a 12-hour clock, 15 o'clock is the same as 3 o'clock because 15 ≡ 3 (mod 12). The remainder of a divided by m, written a mod m, is the representative between 0 and m − 1.

Arithmetic rules

Congruences behave like equations for addition, subtraction and multiplication: if a ≡ b and c ≡ d (mod m), then a + c ≡ b + d and ac ≡ bd. This lets you reduce numbers at any moment. To find the last digit of 7¹⁰⁰, for instance, you only need to work modulo 10.

Division and inverses

Division is the delicate operation. The number a has an inverse modulo m only when gcd(a, m) = 1; the inverse is the x with ax ≡ 1. Dividing by a then means multiplying by x. To solve ax ≡ b (mod m), multiply both sides by the inverse of a. If gcd(a, m) = g is greater than 1, solutions exist only when g divides b, and then there are g of them.

Fermat's little theorem

If p is prime and p does not divide a, then a^p−1 ≡ 1 (mod p). It gives a quick way to reduce large exponents and to find inverses modulo a prime: a⁻¹ ≡ a^p−2.

Key formulas

• a ≡ b (mod m) ⇔ m | (a − b)
• (a ± b) mod m and (a · b) mod m can be computed from the residues
• a⁻¹ exists ⇔ gcd(a, m) = 1; a^(p−1) ≡ 1 (mod p) for prime p ∤ a

Solved example

Practice questions

Try each question first, then open the answer.