Mathematics.

elementary number theory

Arithmetic Functions

Number Theory30 minDifficulty6 out of 10

You should know: mobius function, eulers totient function

Overview

An arithmetic function is simply a function defined on the positive integers, usually capturing something about a number's divisors or prime factorization: the divisor-counting function d(n) (also written τ(n)), the divisor-sum function σ(n), and Euler's totient φ(n) are the classic examples, alongside the Möbius function μ(n). What makes this family so useful is that most of them are multiplicative — f(mn) = f(m)f(n) whenever gcd(m, n) = 1 — which means each one is completely determined by its values on prime powers, and those values are easy to write down from a number's prime factorization. This turns hard-looking questions ('how many divisors does 360 have?') into quick prime-factorization exercises, and the same multiplicative structure underlies deep results like the Möbius inversion formula, Dirichlet convolution, and the study of perfect numbers (n with σ(n) = 2n).

Intuition

Every divisor of n = p₁^{a₁} ⋯ p_k^{a_k} is obtained by picking, independently for each prime pᵢ, an exponent between 0 and aᵢ — so the divisors are in bijection with the (a₁+1)(a₂+1)⋯(a_k+1) possible exponent-tuples, which is exactly d(n). σ(n) uses the same independence: summing over all divisors factors into a product of separate geometric sums 1 + pᵢ + pᵢ² + ⋯ + pᵢ^{aᵢ}, one per prime, because a divisor's total is the product of independently-chosen prime-power pieces. Multiplicativity for coprime m, n is the formal statement of this independence — the divisor structure of m and n don't interact at all when they share no prime factors, so any 'divisor-counting-and-summing' function built this way factors cleanly.

Formal Definition

Definition

For a positive integer n with prime factorization n = p₁^{a₁} p₂^{a₂} ⋯ p_k^{a_k}, the key multiplicative arithmetic functions are:

d(n)=τ(n)=∏i=1k(ai+1)d(n) = \tau(n) = \prod_{i=1}^{k} (a_i + 1)
Number-of-divisors function
σ(n)=∏i=1kpiai+1−1pi−1\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1}-1}{p_i - 1}
Sum-of-divisors function
f(mn)=f(m)f(n)whenever gcd⁡(m,n)=1f(mn) = f(m) f(n) \quad \text{whenever } \gcd(m,n) = 1
Multiplicativity (shared by d, \sigma, \varphi, \mu)

Worked Examples

  1. Factor 12 = 2² · 3.

    12=22⋅3112 = 2^{2} \cdot 3^{1}

  2. d(12) = (2+1)(1+1) = 6.

    d(12)=3⋅2=6d(12) = 3 \cdot 2 = 6

  3. σ(12) = (2³−1)/(2−1) · (3²−1)/(3−1) = 7·4 = 28.

    σ(12)=7⋅4=28\sigma(12) = 7 \cdot 4 = 28

Answer: d(12) = 6 (divisors 1,2,3,4,6,12); σ(12) = 28 (their sum: 1+2+3+4+6+12=28).

Practice Problems

Difficulty 4/10

Compute d(28), the number of divisors of 28.

Difficulty 7/10

Verify that 28 is a perfect number by computing σ(28) and checking σ(28) = 2·28.

Difficulty 5/10

Compute φ(28) using multiplicativity, given φ(4) = 2 and φ(7) = 6.

Quiz

A function f on positive integers is called multiplicative if:
For n = p^a q^b (p, q distinct primes), the divisor-counting function d(n) equals:
A perfect number n is one satisfying:

Summary

  • Arithmetic functions like d(n) (divisor count), σ(n) (divisor sum), and φ(n) (Euler's totient) are determined entirely by n's prime factorization when they are multiplicative.
  • For n = p₁^{a₁}⋯p_k^{a_k}, d(n) = ∏(aᵢ+1) and σ(n) = ∏(pᵢ^{aᵢ+1}−1)/(pᵢ−1), each factoring over the distinct primes.
  • Multiplicativity (f(mn)=f(m)f(n) for coprime m,n) is the structural reason these functions reduce to easy prime-power computations, and underlies deeper tools like Möbius inversion.

References

  1. WebsiteWikipedia — Arithmetic function