Modular Arithmetic

Arithmetic where numbers wrap around after reaching the modulus. Walk around a clock, draw multiplication as a curve, and see which numbers have inverses.

Intermediate

Clock arithmetic

Numbers mod n live on a clock with n positions. Going past n − 1 wraps back to 0.

Modulus n12a9b7

9 + 7 = 16

16 = 1 × 12 + 4

9 + 7 ≡ 4 (mod 12)

Start at 0, take 9 single steps (blue), then 7 more (orange). Each full lap of the clock is a multiple of 12 that the remainder forgets.

Step 16 of 16 single steps, running total 16 ≡ 4

Times-table circle

Place n points around a circle and draw a line from every k to k·m mod n. Multiplication mod n turns into a curve.

Points n120Multiplier m2

Line k connects point k to point k × 2 mod 120. For example, point 7 connects to 14.

With m = 2 the envelope of the lines is a cardioid (one cusp). In general m gives m − 1 cusps.

Interesting coincidences appear when m is close to n or to a simple fraction of n, for example m = 121 would look exactly like m = 1 because 121 ≡ 1 (mod 120).

Congruence classes and inverses

Every integer falls into exactly one class [r], the numbers that leave remainder r when divided by n.

Modulus n10

Class	Some members	gcd(r, 10)	Inverse r⁻¹
[0]	…, -20, -10, 0, 10, 20, …	10	none
[1]	…, -19, -9, 1, 11, 21, …	1	1 (1·1 ≡ 1)
[2]	…, -18, -8, 2, 12, 22, …	2	none
[3]	…, -17, -7, 3, 13, 23, …	1	7 (3·7 ≡ 1)
[4]	…, -16, -6, 4, 14, 24, …	2	none
[5]	…, -15, -5, 5, 15, 25, …	5	none
[6]	…, -14, -4, 6, 16, 26, …	2	none
[7]	…, -13, -3, 7, 17, 27, …	1	3 (7·3 ≡ 1)
[8]	…, -12, -2, 8, 18, 28, …	2	none
[9]	…, -11, -1, 9, 19, 29, …	1	9 (9·9 ≡ 1)

A class r has a multiplicative inverse exactly when gcd(r, n) = 1. Here 4 of the 10 classes are invertible.

What modular arithmetic is

Fix a positive integer n, the modulus. Two integers are congruent mod n when they leave the same remainder after division by n, or equivalently when their difference is a multiple of n. So 17 ≡ 5 (mod 12) because 17 − 5 = 12.

Every integer belongs to exactly one of the n congruence classes [0], [1], …, [n − 1]. You can add and multiply classes: take any member of each, do the ordinary arithmetic, and reduce. The answer does not depend on which members you picked, which is why the clock picture works.

Division is the subtle part. A class a has a modular inverse a⁻¹ (a number with a·a⁻¹ ≡ 1) exactly when gcd(a, n) = 1. When n is prime every non-zero class is invertible, so you can divide by anything except 0.

Key formulas

Congruence

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

n: the modulus, a positive integer
a mod n: the remainder in 0, 1, …, n − 1

Arithmetic on remainders

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

(a × b) mod n = ((a mod n) × (b mod n)) mod n

Modular inverse

a·x + n·y = gcd(a, n) = 1 ⇒ a⁻¹ ≡ x (mod n)

x, y: integers found by the extended Euclidean algorithm

Times-table circle

k → k·m mod n, for k = 0, 1, …, n − 1

m: multiplier; the curve has m − 1 cusps

How to use this visualizer

1
Pick addition or multiplication and set the modulus n with the slider.
2
Choose a and b. Values larger than n show how the walk wraps around the clock more than once.
3
Press Animate steps to watch the marker move. Addition walks one step at a time; multiplication makes b jumps of size a.
4
In the times-table circle, start with m = 2 to see the cardioid, then raise m and n to explore other curves.
5
Use the congruence table to see each class, its gcd with n, and its inverse when one exists. Compare prime and composite n.

Where it is used

Clocks and calendars

15:00 is 3 o’clock because 15 mod 12 = 3. Weekdays repeat mod 7.

Check digits

ISBN and IBAN numbers include a digit chosen so a weighted sum is 0 mod 11 or mod 97, catching typos.

Hashing

Hash tables map a large key to a bucket with key mod table size.

Cryptography

RSA and Diffie–Hellman are built on exponentiation and inverses mod large numbers.

Practice problems

Problem 1: What day will it be?

Today is Wednesday. What day of the week will it be 100 days from now?

Show solution

Weekdays repeat every 7 days, so work mod 7.

100 = 14 × 7 + 2, so 100 ≡ 2 (mod 7).

Moving 100 days is the same as moving 2 days.

Wednesday + 2 days = Friday

Problem 2: Find an inverse

Find the inverse of 7 modulo 26, then solve 7x ≡ 3 (mod 26).

Show solution

gcd(7, 26) = 1, so an inverse exists. Run Euclid:

26 = 3 × 7 + 5, 7 = 1 × 5 + 2, 5 = 2 × 2 + 1

Back-substitute: 1 = 5 − 2·2 = 5 − 2(7 − 5) = 3·5 − 2·7

= 3(26 − 3·7) − 2·7 = 3·26 − 11·7

So 7 × (−11) ≡ 1, and −11 ≡ 15 (mod 26). Check: 7 × 15 = 105 = 4 × 26 + 1.

x ≡ 15 × 3 = 45 ≡ 19 (mod 26).

7⁻¹ ≡ 15 and x ≡ 19 (mod 26)

Discussion

Questions, ideas or a different approach? Join the conversation.