Divisibility & Prime Numbers

Explore the building blocks of integers: divisibility, primes, and the Fundamental Theorem of Arithmetic

The Building Blocks of Integers

Number theory begins with the simplest question: how do integers relate to each other through division? The prime numbers are the atoms of arithmetic — every integer greater than 1 can be written uniquely as a product of primes.

This is the Fundamental Theorem of Arithmetic, and it underpins everything in number theory. In this section, you'll explore divisibility structures, watch prime factorization unfold step by step, and discover the mysterious patterns that primes create.

Demo 1: Divisor Lattice Explorer

Every integer has a structured hierarchy of divisors. The Hasse diagram shows this hierarchy as a graph: divisors are nodes, and edges connect each divisor to its immediate multiples. Click any node to see its relationships.

Divisor Lattice Explorer

12 = 2^2 × 3

1234612

Demo 2: Prime Factorization Step by Step

Watch trial division break any number into its prime building blocks. The algorithm divides by the smallest prime factor at each step until only 1 remains. The result is always unique — that's the Fundamental Theorem of Arithmetic in action.

Prime Factorization Animator

Press Set to begin.

Demo 3: The Sieve of Eratosthenes

The oldest algorithm in mathematics (circa 240 BC). Starting from 2, cross off all multiples of each prime. What remains are the primes. Watch the beautiful wave patterns emerge as composites are eliminated.

Grid size:
Primes found: 0
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Demo 4: The Ulam Spiral

Discovered by Stanislaw Ulam while doodling in a lecture: write integers in a spiral and highlight the primes. Unexpectedly, primes cluster along diagonal lines. This mystery — why diagonals? — hints at deep patterns in prime distribution that motivate the rest of this module.

Ulam Spiral Explorer

Each dot is an integer spiraling outward from the center. Amber dots are primes — notice the diagonal alignments.

Foundation Laid!

You now understand the fundamental structures of number theory:

  • Divisibility forms a lattice structure on the integers
  • Every integer has a unique prime factorization
  • The Sieve of Eratosthenes efficiently identifies primes
  • Primes exhibit mysterious geometric patterns like the Ulam spiral

Next: We'll study the Euclidean algorithm — the oldest and most elegant method for computing greatest common divisors.