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 . It is called multiplicative if and whenever . It is called completely multiplicative if for all positive integers . Standard examples are the divisor-counting function (also written or ), the divisor-sum function , Euler's totient , and the Möbius function .
Key Formula
Where:
- = A positive integer greater than 1, written as a product of prime powers
- = The distinct primes that divide n
- = The exponent of the prime in the factorization of n
- = The number of positive divisors of n
- = The sum of the positive divisors of n
Worked Example
Problem: Find the number of divisors and the sum of divisors by using the prime factorization of 72 instead of listing divisors.
Step 1: Write 72 as a product of prime powers. The factors and share no common prime, so the multiplicative property applies to them.
Step 2: A divisor of 72 has the form with and . That gives 4 choices for i and 3 choices for j. This is the same as .
Step 3: Because is multiplicative, sum the powers of each prime separately and then multiply the results.
Answer: and . 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 is central to RSA encryption. RSA chooses its public and private exponents and so that . 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 for every pair m, n.
Correction: Multiplicative only guarantees this when . For example, , but . Split n into prime powers with no shared primes before you multiply.
