Lesson 1 of 8 · Number Theory
Divisibility & Prime Factorization
Every integer greater than 1 has exactly one prime factorization, and that factorization is the key to almost every question you can ask about divisibility, divisors, or the structure of a number. Learn to factor fluently and read a factorization for information, and most of number theory becomes direct computation rather than guesswork.
Mark your status for this lesson:
Learning objectives
- Factor an integer into primes fluently, and use standard divisibility rules to check small divisors quickly.
- Count the divisors of a number directly from its prime factorization, and find its sum or product.
- Find the smallest or largest number satisfying a divisor-count condition.
- Apply Legendre's formula to find the exponent of a prime in n!.
The core idea
The Fundamental Theorem of Arithmetic guarantees every integer greater than 1 factors into primes in exactly one way (up to order). That uniqueness is what makes prime factorization so powerful — once you have it, every divisibility question about that number becomes a direct read-off, not a search.
Counting divisors
n = p₁^e₁p₂^e₂⋯pₖ^eₖ ⟹ number of divisors = (e₁+1)(e₂+1)⋯(eₖ+1)
Each divisor picks an exponent from 0 to eᵢ for each prime independently — that's exactly (e₁+1)(e₂+1)⋯ combinations.
Sum of divisors
σ(n) = (1+p₁+⋯+p₁^e₁)(1+p₂+⋯+p₂^e₂)⋯
Multiply the geometric-series sum for each prime power separately — this is much faster than listing all divisors and adding them by hand.
Legendre's formula
exponent of p in n! = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ⋯
Counts how many multiples of p, p², p³, ... are among 1 through n — the standard tool for trailing-zero and highest-power-dividing-a-factorial questions.
Worked example 1 — Counting divisors
Problem
How many positive divisors does 720 have?
Key insight
Factor completely first, then apply the divisor-counting formula directly.
Solution
720 = 2⁴ × 3² × 5, so the number of divisors is (4+1)(2+1)(1+1) = 30.
Takeaway
Never list divisors by hand once you have the factorization — the formula is exact and instant.
Worked example 2 — Smallest number with a divisor count
Problem
What is the smallest positive integer with exactly 8 divisors?
Key insight
8 factors as 8, 4×2, or 2×2×2 — each corresponds to a different exponent pattern. To minimize the number, assign larger exponents to smaller primes.
Solution
Pattern {7} → p⁷ → 128. Pattern {3,1} → p³q → 2³×3=24. Pattern {1,1,1} → pqr → 2×3×5=30. The smallest is 24.
Takeaway
"Smallest number with N divisors" problems require comparing every way to factor N into (exponent+1) pieces, not just guessing one pattern.
Worked example 3 — Sum of divisors
Problem
Find the sum of all positive divisors of 45.
Key insight
Factor first, then multiply the geometric-series sum for each prime separately.
Solution
45 = 3² × 5. Sum of divisors: (1+3+9)(1+5) = 13 × 6 = 78.
Takeaway
The sum-of-divisors formula multiplies across primes just like the count formula does — same structure, different inner sum.
Worked example 4 — Legendre's formula
Problem
How many trailing zeros does 100! have?
Key insight
Trailing zeros come from factors of 10 = 2×5. Factors of 2 vastly outnumber factors of 5 in 100!, so the count of trailing zeros equals the exponent of 5.
Solution
⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24.
Takeaway
Always count the exponent of the larger prime in a "how many factors of pq" trailing-digit question — it's always the bottleneck.
Strategy notes
Factor completely before applying any formula
Every formula in this lesson — divisor count, divisor sum, gcd/lcm via factorization — requires the complete prime factorization. A partial factorization gives a wrong answer, not a partial one.
"Smallest/largest number with property X" means comparing exponent patterns
For divisor-count problems, list every way to write the target count as a product of (exponent+1) factors, assign the largest exponents to the smallest primes, and compare the resulting numbers directly.
Common mistakes
Stopping factorization at a composite factor
"84 = 4 × 21" is a valid factorization but not a prime factorization — 4 and 21 both still need to be broken down further.
Forgetting the +1 in the divisor-count formula
The formula uses (exponent + 1), not the exponent itself — a divisor can use anywhere from 0 to e copies of a prime, which is e+1 choices.
Using the smaller prime's exponent in a trailing-zero problem
Trailing zeros in n! are limited by the scarcer prime (usually 5, since 2 is far more abundant) — always compute the exponent of the larger prime in the pair, not both.
Practice
20 questions across four difficulty tiers, each with a single numeric answer. Up to three tries per question before the solution is shown.