Arithmetic functions and perfect numbers

The Pythagoreans called 6 perfect because it equals the sum of its proper divisors, \(1 + 2 + 3\). The next perfect number is \(28 = 1 + 2 + 4 + 7 + 14\), then 496 and 8128. Euclid found a recipe that produces perfect numbers, and two thousand years later Euler proved that it produces every even one. Whether an odd perfect number exists is still unknown, one of the oldest open problems in mathematics. To discuss such questions we need functions that measure the divisors of \(n\): how many there are, what they add up to, and how many numbers below \(n\) are coprime to it. This lesson studies these arithmetic functions and the property that makes them computable, multiplicativity.

Arithmetic functions

An arithmetic function is any function defined on the positive integers. The three most important ones are:

• \(\tau(n)\), the number of positive divisors of \(n\) (also written \(d(n)\)). For example \(\tau(12) = 6\).

• \(\sigma(n)\), the sum of the positive divisors of \(n\). For example \(\sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28\).

• \(\varphi(n)\), Euler's function from lesson 6. For example \(\varphi(12) = 4\).

In the notation \(\sum_{d \mid n}\) for a sum over the positive divisors \(d\) of \(n\), we have \(\tau(n) = \sum_{d \mid n} 1\) and \(\sigma(n) = \sum_{d \mid n} d\). Their values jump around irregularly: \(\tau(p) = 2\) for every prime, while \(\tau(720720) = 240\). Yet they are entirely determined by the prime factorization of \(n\), through formulas that are simple once we know the right structural property.

Multiplicative functions

Definition. An arithmetic function \(f\) is multiplicative if \(f(1) = 1\) and \(f(mn) = f(m)f(n)\) whenever \(\gcd(m, n) = 1\). It is completely multiplicative if \(f(mn) = f(m)f(n)\) for all \(m, n\).

The functions \(n \mapsto n^k\) are completely multiplicative. The functions \(\tau\), \(\sigma\) and \(\varphi\) are multiplicative but not completely: \(\tau(4) = 3\) while \(\tau(2)^2 = 4\). A multiplicative function is determined by its values at prime powers: if \(n = p_1^{e_1}\cdots p_r^{e_r}\), then \(f(n) = f(p_1^{e_1})\cdots f(p_r^{e_r})\), since distinct prime powers are coprime.

Lemma. If \(\gcd(m, n) = 1\), every positive divisor \(d\) of \(mn\) can be written uniquely as \(d = d_1d_2\) with \(d_1 \mid m\) and \(d_2 \mid n\), namely \(d_1 = \gcd(d, m)\) and \(d_2 = \gcd(d, n)\). Conversely every such product divides \(mn\). Proof: by unique factorization, the primes of \(m\) and of \(n\) are disjoint, and a divisor of \(mn\) splits its prime powers between them in exactly one way.

Theorem. If \(f\) is multiplicative, then so is \(F(n) = \sum_{d \mid n} f(d)\). Proof: for coprime \(m, n\), by the lemma \[F(mn) = \sum_{d_1 \mid m}\sum_{d_2 \mid n} f(d_1d_2) = \sum_{d_1 \mid m} f(d_1)\sum_{d_2 \mid n} f(d_2) = F(m)F(n).\]

Applying this to the multiplicative functions \(f(n) = 1\) and \(f(n) = n\) shows that \(\tau\) and \(\sigma\) are multiplicative. That \(\varphi\) is multiplicative was shown with the Chinese remainder theorem in lessons 5 and 6.

Formulas from the factorization

At a prime power the divisors are \(1, p, \ldots, p^e\), so \[\tau(p^e) = e + 1, \qquad \sigma(p^e) = 1 + p + \cdots + p^e = \frac{p^{e+1} - 1}{p - 1}, \qquad \varphi(p^e) = p^e - p^{e-1}.\] By multiplicativity, for \(n = \prod p_i^{e_i}\), \[\tau(n) = \prod (e_i + 1), \qquad \sigma(n) = \prod \frac{p_i^{e_i+1} - 1}{p_i - 1}, \qquad \varphi(n) = n\prod\Big(1 - \frac{1}{p_i}\Big).\]

The figure shows why the divisor count is a product. Each divisor of \(60 = 2^2 \cdot 3 \cdot 5\) is \(2^a3^b5^c\) with \(a \in \{0, 1, 2\}\), \(b, c \in \{0, 1\}\), a point in a \(3 \times 2 \times 2\) box. In the same way \(\sigma(60)\) factors as \((1 + 2 + 4)(1 + 3)(1 + 5) = 168\): expanding the product produces each divisor exactly once.

These formulas make the functions fast to evaluate once \(n\) is factored, and essentially impossible to evaluate otherwise. That asymmetry matters in cryptography: knowing \(\varphi(n)\) for \(n = pq\) is equivalent to knowing the factors, since \(\varphi(n) = n - (p + q) + 1\) gives \(p + q\), and with \(pq\) that determines \(p\) and \(q\) as the roots of a quadratic.

Gauss's identity

Theorem (Gauss). For every positive integer \(n\), \[\sum_{d \mid n}\varphi(d) = n.\]

Proof. Sort the numbers \(1, 2, \ldots, n\) according to their gcd with \(n\). The number \(k\) has \(\gcd(k, n) = g\) exactly when \(k = gj\) with \(1 \le j \le n/g\) and \(\gcd(j, n/g) = 1\). So exactly \(\varphi(n/g)\) of the numbers have gcd \(g\). Summing over all divisors \(g\), \(n = \sum_{g \mid n}\varphi(n/g) = \sum_{d \mid n}\varphi(d)\), since \(n/g\) runs through the divisors of \(n\) as \(g\) does.

For \(n = 12\): \(\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12\). Another way to see it: the fractions \(\frac{1}{12}, \frac{2}{12}, \ldots, \frac{12}{12}\), written in lowest terms, have denominators \(d \mid 12\), and exactly \(\varphi(d)\) of them have denominator \(d\). Lesson 8 uses this identity to prove that primitive roots exist.

The Möbius function and inversion

Gauss's identity expresses \(n\) in terms of \(\varphi\). Can we turn it around and express \(\varphi\) in terms of \(n\)? The tool is the Möbius function, \[\mu(n) = \begin{cases} 1 & n = 1, \\ (-1)^r & n \text{ is a product of } r \text{ distinct primes}, \\ 0 & p^2 \mid n \text{ for some prime } p. \end{cases}\] So \(\mu(1) = 1\), \(\mu(2) = \mu(3) = -1\), \(\mu(4) = 0\), \(\mu(6) = 1\), \(\mu(30) = -1\). It is multiplicative.

Lemma. \(\sum_{d \mid n}\mu(d)\) is 1 if \(n = 1\) and 0 if \(n > 1\). Proof: the sum is multiplicative, so check prime powers: \(\mu(1) + \mu(p) + \mu(p^2) + \cdots = 1 - 1 + 0 + \cdots = 0\).

Theorem (Möbius inversion). If \(F(n) = \sum_{d \mid n} f(d)\) for all \(n\), then \(f(n) = \sum_{d \mid n}\mu(d)F(n/d)\).

Proof. Substitute: \(\sum_{d \mid n}\mu(d)\sum_{e \mid n/d} f(e) = \sum_{e \mid n} f(e)\sum_{d \mid n/e}\mu(d)\), exchanging the order of summation over pairs with \(de \mid n\). By the lemma the inner sum is 0 unless \(n/e = 1\), leaving \(f(n)\).

Applied to Gauss's identity, inversion gives \(\varphi(n) = \sum_{d \mid n}\mu(d)\frac{n}{d}\), which is the inclusion–exclusion count of numbers not divisible by any prime factor of \(n\), and multiplying out \(n\prod(1 - 1/p)\) gives exactly this sum. Möbius inversion appears throughout mathematics: it counts irreducible polynomials over finite fields, necklaces with a given number of beads, and, in its analytic form, connects the primes with the zeros of the Riemann zeta function.

Perfect numbers

Definition. A positive integer \(n\) is perfect if \(\sigma(n) = 2n\), that is, if \(n\) is the sum of its proper divisors.

Theorem (Euclid, Elements IX.36). If \(2^k - 1\) is prime, then \(n = 2^{k-1}(2^k - 1)\) is perfect.

Proof. Let \(q = 2^k - 1\), an odd prime. By multiplicativity, \(\sigma(n) = \sigma(2^{k-1})\sigma(q) = (2^k - 1)(q + 1) = (2^k - 1)2^k = 2n\).

Theorem (Euler). Every even perfect number has this form.

Proof. Let \(n = 2^{k-1}m\) be perfect with \(k \ge 2\) and \(m\) odd. Then \(\sigma(n) = (2^k - 1)\sigma(m)\), and this equals \(2n = 2^km\). Since \(2^k - 1\) is odd and divides \(2^km\), it divides \(m\); write \(m = (2^k - 1)M\). Substituting, \(\sigma(m) = 2^kM = m + M\). But \(m\) and \(M\) are both divisors of \(m\), and \(M < m\) since \(k \ge 2\). If \(M > 1\), then 1 is a third divisor, making \(\sigma(m) \ge m + M + 1\). So \(M = 1\), and \(\sigma(m) = m + 1\), which means \(m\) is prime. Thus \(n = 2^{k-1}(2^k - 1)\) with \(2^k - 1\) prime.

Primes of the form \(2^k - 1\) are called Mersenne primes, after the French friar Marin Mersenne, who studied them in 1644. For \(2^k - 1\) to be prime, \(k\) must itself be prime, because \(2^{ab} - 1\) is divisible by \(2^a - 1\). The converse fails: \(2^{11} - 1 = 2047 = 23 \cdot 89\). The first Mersenne primes come from \(k = 2, 3, 5, 7, 13, 17, 19, 31\), giving the perfect numbers 6, 28, 496, 8128, 33550336, and so on. Only about fifty Mersenne primes are known; the largest have tens of millions of digits and are the largest primes known of any kind, found by the volunteer Great Internet Mersenne Prime Search using a special test due to Lucas and Lehmer.

Odd perfect numbers have never been found, and none exists below \(10^{1500}\). Euler showed that an odd perfect number must have the form \(p^{4a+1}m^2\) with \(p \equiv 1 \pmod 4\) prime, and many further constraints are known, but no proof of nonexistence. Related curiosities are amicable pairs, where each number is the sum of the other's proper divisors, such as 220 and 284, known to Pythagoras, and 1184 and 1210, found by a sixteen-year-old Nicolò Paganini in 1866 after Fermat, Descartes and Euler had all missed it.

Arithmetic functions by computer

The program computes \(\tau\), \(\sigma\), \(\varphi\) and \(\mu\) from factorizations and checks multiplicativity, Gauss's identity and Möbius inversion, then searches for perfect numbers, Mersenne primes and amicable pairs.

import math

def factor(n):
    f, d = {}, 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1; n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

def tau(n):   return math.prod(e + 1 for e in factor(n).values())
def sigma(n): return math.prod((p**(e + 1) - 1) // (p - 1) for p, e in factor(n).items())
def phi(n):   return math.prod(p**e - p**(e - 1) for p, e in factor(n).items())
def mu(n):
    f = factor(n)
    return 0 if any(e > 1 for e in f.values()) else (-1) ** len(f)
def divisors(n): return [d for d in range(1, n + 1) if n % d == 0]

print("n=60: tau", tau(60), "sigma", sigma(60), "phi", phi(60), "mu", mu(60))
print("tau(720720) =", tau(720720))
pairs = [(m, n) for m in range(1, 60) for n in range(1, 60) if math.gcd(m, n) == 1]
print("multiplicative on coprime pairs:", all(f(m * n) == f(m) * f(n) for f in (tau, sigma, phi, mu) for m, n in pairs))
print("sum of phi(d) over d | n equals n, n <= 500:", all(sum(phi(d) for d in divisors(n)) == n for n in range(1, 501)))
print("phi by Mobius inversion, n <= 500:", all(phi(n) == sum(mu(d) * (n // d) for d in divisors(n)) for n in range(1, 501)))
print("mu(1..20):", [mu(n) for n in range(1, 21)])

print("perfect numbers below 10000:", [n for n in range(2, 10000) if sigma(n) == 2 * n])

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, math.isqrt(n) + 1))

def lucas_lehmer(p):
    if p == 2:
        return True
    M, s = 2**p - 1, 4
    for _ in range(p - 2):
        s = (s * s - 2) % M
    return s == 0

exps = [p for p in range(2, 130) if is_prime(p) and lucas_lehmer(p)]
print("Mersenne prime exponents below 130:", exps)
print("perfect number from p = 31:", 2**30 * (2**31 - 1))
print("2^11 - 1 =", 2**11 - 1, factor(2**11 - 1))
amic = [(a, sigma(a) - a) for a in range(2, 20000) if sigma(a) - a > a and sigma(sigma(a) - a) - (sigma(a) - a) == a]
print("amicable pairs below 20000:", amic)

n=60: tau 12 sigma 168 phi 16 mu 0
tau(720720) = 240
multiplicative on coprime pairs: True
sum of phi(d) over d | n equals n, n <= 500: True
phi by Mobius inversion, n <= 500: True
mu(1..20): [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0]
perfect numbers below 10000: [6, 28, 496, 8128]
Mersenne prime exponents below 130: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127]
perfect number from p = 31: 2305843008139952128
2^11 - 1 = 2047 {23: 1, 89: 1}
amicable pairs below 20000: [(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18416)]

The Lucas–Lehmer test used here says that for an odd prime \(p\), \(2^p - 1\) is prime exactly when the sequence \(s_0 = 4\), \(s_{i+1} = s_i^2 - 2\) satisfies \(s_{p-2} \equiv 0 \pmod{2^p - 1}\). It finds the twelve Mersenne prime exponents below 130 in a fraction of a second, while trial division could not even handle \(2^{61} - 1\). The amicable pairs include Paganini's 1184 and 1210.