1
1 is not prime, by decision
Because uniqueness of factorisation would fail: 6 = 2·3 = 1·2·3 = 1·1·2·3. The definition is chosen to make the theorem true.
Lesson · Number Theory and Cryptography · Divisibility
Primes and Unique Factorisation
The fundamental theorem of arithmetic. Primes are the multiplicative atoms, there are infinitely many, and the uniqueness of the factorisation is what makes almost every later argument possible.
prime: exactly two positive divisors, 1 and itself. 1 is NOT prime.
every n > 1 is a product of primes, uniquely up to order
there are infinitely many primes (Euclid)
if n is composite it has a prime factor ≤ √n
The atoms of multiplication
Core ideas
What this lesson establishes
Existence of a factorisation is easy; uniqueness is the theorem, and it is what everything else uses.
2
Uniqueness is the substantive half
Existence follows from strong induction in three lines. Uniqueness needs Euclid's lemma, which needs Bézout.
3
Trial division stops at √n
A composite n has a factor at most √n, so testing beyond that is unnecessary — and it is why the sieve of “The Sieve of Eratosthenes” stops where it does.
The material
Primes
The definition, both halves of the fundamental theorem, and Euclid's proof.
Definition · Prime and composite
An integer p > 1 is prime if its only positive divisors are 1 and p. An integer n > 1 that is not prime is composite. The number 1 is neither.
Excluding 1 is a convention chosen to make the fundamental theorem clean. If 1 were prime, 6 would factor as 2·3, 1·2·3, 1·1·2·3 and so on, and uniqueness would need an awkward qualification.
Theorem · Fundamental theorem of arithmetic
Every integer n > 1 can be written as a product of primes, and the factorisation is unique up to the order of the factors.
Existence, by strong induction (“Strong Induction” in Induction and Recursion). If n is prime it is a product of one prime. Otherwise n = ab with 1 < a, b < n, and by the inductive hypothesis both factor into primes; concatenating the two factorisations gives one for n.
Uniqueness requires Euclid's lemma (“Bézout's Identity and Modular Inverses”): if a prime p divides ab then p | a or p | b. Given two factorisations of n, the first prime of one divides the product forming the other, hence divides one of its primes, hence equals it. Cancelling and repeating matches the factorisations term by term.
□
Uniqueness is not obvious and it is not universal. In the number system {a + b√−5} the number 6 factors as 2 · 3 and as (1 + √−5)(1 − √−5), with all four factors irreducible. Unique factorisation is a property of ℤ, and it is what Number Theory and Cryptography relies on throughout.
Theorem · Euclid: infinitely many primes
For any finite list of primes there is a prime not on it.
Given primes p₁, …, p_k, let N = p₁p₂⋯p_k + 1. Since N > 1 it has a prime factor q.
If q were some pᵢ, it would divide both p₁⋯p_k and N, hence their difference 1 — impossible for a prime. So q is not on the list.
□
N itself need not be prime: 2·3·5·7·11·13 + 1 = 30031 = 59 · 509. The proof produces a prime not on the list, not necessarily N, and misremembering that is the standard error.
Theorem · Trial division bound
If n > 1 is composite, it has a prime factor p ≤ √n.
Write n = ab with 1 < a ≤ b < n. If both exceeded √n their product would exceed n, so a ≤ √n. Any prime factor of a is a prime factor of n and is at most a ≤ √n.
□
So testing 101 for primality needs only the primes up to 10: 2, 3, 5, 7. None divides it, so it is prime. That is four divisions rather than ninety-nine.
How the primes are distributed
There are 25 primes below 100, 168 below 1000, and 78 498 below a million. The prime number theorem says the count below n is approximately n / ln n, so primes thin out slowly — near 10¹⁰⁰ roughly one number in 230 is prime. That density is what makes RSA key generation practical: random large numbers can be tested until one is prime.
Interactive
Number theory workbench
Algorithms with their traces
Method
Factoring and testing
Small primes first, stop at the square root.
1
Divide out the small primes in order
2, then 3, then 5, and so on, taking each as many times as it goes.
2
Stop when the divisor exceeds √(remaining)
Whatever is left is then prime. This is the bound above, and it is what keeps hand factorisation feasible.
3
Count divisors from the exponents
If n = p₁^{e₁}⋯p_k^{e_k} then n has (e₁+1)⋯(e_k+1) positive divisors, since each exponent is chosen independently from 0 to eᵢ.
4
To test primality, divide by primes up to √n
If none divides, it is prime. For large numbers this is hopeless and probabilistic tests are used instead.
Primes
Score 0 / 0Choose the answer you can justify.
Factor 360 and count its divisors
Trial division, then the divisor formula.
360 / 2 = 180 360 / 4 = 90 360 / 8 = 45
45 / 3 = 15 45 / 9 = 5
5 is prime, and 5 > √5 stops the search
360 = 2³ · 3² · 5
Divisors: (3+1)(2+1)(1+1) = 4 · 3 · 2 = 24
Check by listing: 1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,
60,72,90,120,180,360 — 24 of them ✓
The divisor count is a product rule application: a divisor is determined by choosing an exponent for each prime independently, from 0 up to its exponent in n. “The Sum and Product Rules” in Combinatorics and Counting is doing the work, and the fundamental theorem is what guarantees the choice determines the divisor uniquely.
Common mistakes
1
Calling 1 primeIt is neither prime nor composite, and the exclusion is what makes unique factorisation stateable.
2
Believing Euclid's N is always primeIt has a prime factor outside the list, which is all the proof needs and all it claims.
3
Trial dividing past the square rootUnnecessary. If nothing up to √n divides n, nothing above it does either.
Check your understanding
✓
Finish when you can factor a four-digit number and count its divisors.
Factor 2520 completely and predict its divisor count from the exponents before listing anything. 2520 = 2³·3²·5·7, so there are 4·3·2·2 = 48 divisors.
Note: Factoring is easy for small numbers and believed hard for large ones, and that asymmetry is the entire basis of RSA in “RSA Encryption”. The best known general algorithms are sub-exponential but not polynomial, and no proof exists that factoring is genuinely hard.