📋 Prerequisites

• GCD, LCM & Factorization
• Advanced Modular Arithmetic

Number-theoretic functions take integers as input and spit out integers. The big ones — tau (divisor count), sigma (divisor sum), and phi (Euler's totient) — are all multiplicative, meaning you can compute them from prime factorizations by multiplying per-prime values. We unify everything under the multiplicative function framework, then introduce the Möbius function and its surprising role.

📚 Key Concepts

Multiplicative Functions

A function $f$ is multiplicative if whenever gcd(m, n) = 1:

\[ f(mn) = f(m) \cdot f(n) \]

Completely multiplicative: $f(mn) = f(m)f(n)$ for ALL m, n (no gcd condition).

Why this matters: if you know the prime factorization $n = \prod p_i^{a_i}$, then for any multiplicative function:

\[ f(n) = \prod f(p_i^{a_i}) \]

Just compute f on each prime power and multiply! This is why prime factorization is the universal key.

τ(n) — Number of Divisors

Also written d(n) or τ(n). Counts positive divisors of n.

\[ \tau(n) = \prod_{i=1}^{k} (a_i + 1) \quad \text{where } n = \prod p_i^{a_i} \]

On prime powers: $ \tau(p^a) = a + 1 $

Multiplicative: Yes, τ is multiplicative (but not completely).

Example: τ(12) = τ\(((2^{2} \\times 3^{1})\) = (2+1)(1+1) = 6. Divisors: {1,2,3,4,6,12}\) ✓

σ(n) — Sum of Divisors

Sum of all positive divisors of n.

\[ \sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i + 1} - 1}{p_i - 1} \]

On prime powers: $ \sigma(p^a) = 1 + p + p^2 + ... + p^a = \frac{p^{a+1}-1}{p-1} $ (geometric series)

Multiplicative: Yes, σ is multiplicative.

Example: σ(12) = σ\(((2^{2}) \\times\)\) σ\(((3^{1}) = (1+2+4)(1+3) = 7 \\times\) 4 = 28\) ✓

φ(n) — Euler's Totient Function

Counts integers from 1 to n that are coprime to n.

\[ \varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) \]

On prime powers: $ \varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1) = p^a(1 - 1/p) $

Multiplicative: Yes, φ is multiplicative.

Example: φ(12) = φ\(((2^{2}) \\times\)\) φ\(((3^{1}) = 2 \\times\) 2 = 4. Coprime to 12: {1, 5, 7, 11}\) ✓

Perfect, Abundant, Deficient Numbers

Classify n based on σ(n) vs 2n (or equivalently, sum of proper divisors vs n):

• Perfect: σ(n) = 2n (sum of proper divisors = n). Examples: 6, 28, 496
• Abundant: σ(n) > 2n. Example: 12 (σ=28 > 24)
• Deficient: σ(n) < 2n. Example: 8 (σ=15 < 16)

Euclid-Euler Theorem: Every even perfect number has the form $ 2^{p-1}(2^p - 1) $ where $2^p - 1$ is a Mersenne prime. No odd perfect numbers are known.

Möbius Function μ(n)

Defined as:

• $ \mu(n) = 1 $ if n is a square-free positive integer with an even number of prime factors
• $ \mu(n) = -1 $ if n is a square-free positive integer with an odd number of prime factors
• $ \mu(n) = 0 $ if n has a squared prime factor

Examples:

• μ(1) = 1 (zero primes, even)
• μ(6) = μ\((2 \\times 3) = 1 (two primes, even, square-free)\)
• μ(30) = μ\((2 \\times 3 \\times 5) = -1 (three primes, odd, square-free)\)
• μ(12) = μ\(((2^{2} \\times 3) = 0 (has 2^{2})\)\)

Multiplicative: Yes, μ is multiplicative.

Möbius Inversion (Intro)

If $ g(n) = \sum_{d|n} f(d) $ for all n, then:

\[ f(n) = \sum_{d|n} \mu(d) \cdot g\left(\frac{n}{d}\right) \]

This is the "inclusion-exclusion of number theory." It lets you invert sum-over-divisors relationships.

Example: since $ n = \sum_{d|n} \varphi(d) $, Möbius inversion gives $ \varphi(n) = \sum_{d|n} \mu(d) \cdot \frac{n}{d} $.

Important Summatory Relationships

• $ \sum_{d|n} \mu(d) = 1 $ if n = 1, and 0 otherwise (fundamental Möbius sum)
• $ \sum_{d|n} \varphi(d) = n $ (partition 1..n by gcd with n)
• $ \sum_{d|n} \tau(d) = $ not simple, but $ \sum_{k=1}^n \tau(k) = \sum_{k=1}^n \lfloor n/k \rfloor $

✏️ Example Problems