Arithmetic Functions Summary

Number Theory · Axiom Academy

Let's review the key concepts from Unit 7: Arithmetic Functions in Number Theory. Divisor Count Function τ(n): Counts the total number of positive divisors of n . For example, τ(12) = 6 since 12 has divisors 1, 2, 3, 4, 6, 12. Divisor Sum Function σ(n): Sums all positive divisors of n . For example, σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28. Formula for Prime Powers: If n = p k , then τ( p k ) = k + 1 and σ( p k ) = 1 + p + ... + p k . Why It Matters: These functions reveal the divisor structure of integers and are fundamental in studying perfect and amicable numbers. Definition: A function f is multiplicative if f (1) = 1 and f ( mn ) = f ( m ) · f ( n ) whenever gcd( m, n ) = 1. Key Examples: Both τ and σ are multiplicative functions, as is Euler's totient function φ. Computing Values: For n = p 1 k 1 · p 2 k 2 · ... · p r k r , we have f ( n ) = f ( p 1 k 1 ) · f ( p 2 k 2 ) · ... · f ( p r k r ). Power of Multiplicativity: Reduces complex calculations to evaluating the function on prime powers. Example Recap: Computing σ(180) Step 1 - Prime Factorization: Write 180 = 2 2 · 3 2 · 5 1 . Step 2 - Use Multiplicativity: Since σ is multiplicative, σ(180) = σ(2 2 ) · σ(3 2 ) · σ(5 1 ). Step 3 - Calculate Each Factor: σ(2 2 ) = 1 + 2 + 4 = 7, σ(3 2 ) = 1 + 3 + 9 = 13, σ(5) = 1 + 5 = 6. Step 4 - Multiply: σ(180) = 7 · 13 · 6 = 546. This is much faster than adding all 18 divisors of 180 individually!

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