Divisor Function Examples

Number Theory · Axiom Academy

EXAMPLE Divisor Function Examples Computing τ(n) and σ(n) using prime factorization formulas Excellent work! You've completed this divisor function example. Here's what we learned: Prime Factorization First: Always start by finding the prime factorization of n. For n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ, this is the foundation for both formulas. Divisor Count Formula: τ(n) = (a₁ + 1)(a₂ + 1)...(aₖ + 1). The number of divisors is multiplicative and depends only on the exponents in the prime factorization. Sum of Divisors Formula: σ(n) = [(p₁^(a₁+1) - 1)/(p₁ - 1)] · [(p₂^(a₂+1) - 1)/(p₂ - 1)] · ... · [(pₖ^(aₖ+1) - 1)/(pₖ - 1)]. Each factor represents the sum of all powers of that prime from 0 to aᵢ. Multiplicative Functions: Both τ(n) and σ(n) are multiplicative functions, meaning if gcd(a,b) = 1, then τ(ab) = τ(a)·τ(b) and σ(ab) = σ(a)·σ(b). These formulas provide efficient ways to compute divisor properties without listing all divisors. Practice with different composite numbers to build confidence!

This is the written version of the interactive lesson above. See the full Number Theory course.