Mathwords logoMathwords

Arithmetic Function — Definition, Formula & Example

An arithmetic function is a rule that takes a positive integer n and returns a number that usually describes some property of n. Examples include how many divisors n has, the sum of its divisors, and how many smaller integers share no factor with it.

An arithmetic (or number-theoretic) function is any function f:Z+→Cf: \mathbb{Z}^{+} \to \mathbb{C}. It is called multiplicative if f(1)=1f(1) = 1 and f(mn)=f(m)f(n)f(mn) = f(m)f(n) whenever gcd⁡(m,n)=1\gcd(m, n) = 1. It is called completely multiplicative if f(mn)=f(m)f(n)f(mn) = f(m)f(n) for all positive integers m,nm, n. Standard examples are the divisor-counting function d(n)d(n) (also written τ(n)\tau(n) or σ0(n)\sigma_0(n)), the divisor-sum function σ(n)\sigma(n), Euler's totient φ(n)\varphi(n), and the Möbius function μ(n)\mu(n).

Key Formula

n=p1a1p2a2⋯pkak  ⟹  d(n)=∏i=1k(ai+1),σ(n)=∏i=1kpiai+1−1pi−1n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \;\Longrightarrow\; d(n) = \prod_{i=1}^{k} (a_i + 1), \qquad \sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1}
Where:
  • nn = A positive integer greater than 1, written as a product of prime powers
  • pip_i = The distinct primes that divide n
  • aia_i = The exponent of the prime pip_i in the factorization of n
  • d(n)d(n) = The number of positive divisors of n
  • σ(n)\sigma(n) = The sum of the positive divisors of n

Worked Example

Problem: Find the number of divisors d(72)d(72) and the sum of divisors σ(72)\sigma(72) by using the prime factorization of 72 instead of listing divisors.
Step 1: Write 72 as a product of prime powers. The factors 232^3 and 323^2 share no common prime, so the multiplicative property applies to them.
72=23⋅3272 = 2^3 \cdot 3^2
Step 2: A divisor of 72 has the form 2i3j2^i 3^j with 0≤i≤30 \le i \le 3 and 0≤j≤20 \le j \le 2. That gives 4 choices for i and 3 choices for j. This is the same as d(8)⋅d(9)d(8) \cdot d(9).
d(72)=(3+1)(2+1)=4⋅3=12d(72) = (3+1)(2+1) = 4 \cdot 3 = 12
Step 3: Because σ\sigma is multiplicative, sum the powers of each prime separately and then multiply the results.
σ(72)=(1+2+4+8)(1+3+9)=15⋅13=195\sigma(72) = (1 + 2 + 4 + 8)(1 + 3 + 9) = 15 \cdot 13 = 195
Answer: d(72)=12d(72) = 12 and σ(72)=195\sigma(72) = 195. You can confirm this by listing the divisors 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72: there are 12 of them, and they add to 195.

Why It Matters

Euler's totient φ(n)\varphi(n) is central to RSA encryption. RSA chooses its public and private exponents ee and dd so that ed≡1(modφ(n))ed \equiv 1 \pmod{\varphi(n)}. In analytic number theory, arithmetic functions become coefficients of Dirichlet series such as the Riemann zeta function, which links divisor sums to the distribution of primes.

Common Mistakes

Mistake: Assuming a multiplicative function satisfies f(mn)=f(m)f(n)f(mn) = f(m)f(n) for every pair m, n.
Correction: Multiplicative only guarantees this when gcd⁡(m,n)=1\gcd(m, n) = 1. For example, d(4)=3d(4) = 3, but d(2)⋅d(2)=2⋅2=4d(2) \cdot d(2) = 2 \cdot 2 = 4. Split n into prime powers with no shared primes before you multiply.

Related Terms