Modular Arithmetic

Enter the world of clock arithmetic: congruences, modular operations, and the Chinese Remainder Theorem

Clock Arithmetic

Modular arithmetic is the mathematics of remainders. When we say a ≡ b (mod n), we mean a and b leave the same remainder when divided by n. It's like a clock: after 12 comes 1 again.

Far from being a curiosity, modular arithmetic is the foundation of modern cryptography, computer science, and much of algebraic number theory. The integers modulo n form rich algebraic structures that connect directly to group theory.

Demo 1: The Modular Clock

Visualize modular arithmetic as positions on a clock face. Addition moves you clockwise, and when you pass the modulus, you wrap back around to 0. Multiplication creates interesting patterns of jumps around the dial.

Modular Clock Visualizer

3 + 5 = 8 ≡ 8 (mod 12)
01234567891011mod 12

Positions 0 to 11 around the clock. Blue = operand a, Gold = result. The arc traces b steps clockwise from a.

Demo 2: Congruence Classes

Modular arithmetic partitions the integers into congruence classes. Every integer belongs to exactly one class mod n. This partition is compatible with addition and multiplication — you can compute with classes instead of individual numbers.

Congruence Class Explorer

[0]
[1]
[2]
[3]
[4]

Each integer is colored by its residue class mod 5. Numbers with the same color are congruent.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Grouped by residue class

[0]{ 0, 5, 10, 15, 20, 25, 30, 35, 40 }
[1]{ 1, 6, 11, 16, 21, 26, 31, 36 }
[2]{ 2, 7, 12, 17, 22, 27, 32, 37 }
[3]{ 3, 8, 13, 18, 23, 28, 33, 38 }
[4]{ 4, 9, 14, 19, 24, 29, 34, 39 }
Notation: [a] = { x ∈ ℤ : x ≡ a (mod 5) } denotes the congruence class of a modulo 5.

Demo 3: Modular Multiplication Table

The multiplication table mod n reveals the algebraic structure. The units (elements with multiplicative inverses) form a group under multiplication — this is (Z/nZ)*, a central object in number theory and a direct connection to Group Theory.

Modular Multiplication Table

×0123456
00000000
10123456
20246135
30362514
40415263
50531642
60654321
Units (invertible): 1, 2, 3, 4, 5, 6Zero divisors: —
Group Theory: The 6 invertible elements form the multiplicative group (Z/7Z)*. Every unit has a unique inverse, and the group is closed under multiplication mod 7.

Cell colors use HSL hues proportional to the result value. Filter rows/columns by choosing a highlight mode above.

Demo 4: The Chinese Remainder Theorem

Given a system of congruences with coprime moduli, there is always a unique solution modulo the product. This ancient result (attributed to Sun Tzu, ~3rd century) is both theoretically deep and computationally essential.

Chinese Remainder Theorem

x ≡(mod)
x ≡(mod)
x ≡ 8 (mod 15)

Number line (0–60):

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

Solutions in range: 8, 23, 38, 53. The pattern repeats every 15 integers.

The CRT guarantees a unique solution modulo the product of pairwise coprime moduli. Highlighted cells on the number line show all solutions in the displayed range.

Demo 5: Fast Modular Exponentiation

Computing ab mod m naively requires b multiplications. The repeated squaring algorithm uses the binary expansion of b to do it in only log(b) steps — essential for cryptography where exponents have hundreds of digits.

Modular Exponentiation (Repeated Squaring)

Binary expansion of 13: 11012(4 bits)
bit[0]=1base=3result*=3r=3next base=9
bit[1]=0base=9skip multiplyr=3next base=13
bit[2]=1base=13result*=13r=5next base=16
bit[3]=1base=16result*=16r=12next base=1
313 mod 17 = ?

Repeated squaring computes be mod m in O(log e) multiplications by scanning the binary digits of the exponent from least to most significant.

Modular Mastery!

You now have a solid grasp of modular arithmetic:

  • Congruences and the clock metaphor for modular operations
  • Congruence classes as a partition of the integers
  • The group structure of units (Z/nZ)* under multiplication
  • The Chinese Remainder Theorem for solving systems of congruences
  • Fast modular exponentiation via repeated squaring

Next: We'll discover Fermat's Little Theorem, Euler's totient function, and the fascinating world of multiplicative arithmetic functions.