Arithmetic Functions and Perfect Numbers
The number of divisors of an integer, their sum, and Euler's totient can all be read off the factorization, because each of them is multiplicative. This unit proves that divisor sums preserve multiplicativity, introduces the Möbius function and the inversion formula that undoes a divisor sum, shows that the integers up to N have about ln N divisors on average, and proves the Euclid-Euler theorem that ties the even perfect numbers to the Mersenne primes. It ends with amicable numbers, aliquot sequences, and two questions open since antiquity.
The number \(720\) has \(30\) divisors, and they add up to \(2418\). Nobody needs to list them to know this: both numbers can be read off the factorization \(720 = 2^{4} \cdot 3^{2} \cdot 5\) in a few seconds, and the reason is a property, called multiplicativity, that the most useful functions of number theory share. This unit develops that property, introduces the Möbius function, which undoes sums over divisors the way subtraction undoes addition, estimates how many divisors a typical number has, and then turns to the oldest question in the subject that is still open: which numbers equal the sum of their own divisors other than themselves.
1 Arithmetic functions
An arithmetic function is a function \(f\) defined on the positive integers \(1, 2, 3, \ldots\), with real or complex values. The subject is built on a handful of particular functions, each of which records something about how its argument \(n\) is put together from primes, and three of them run through the whole unit:
- \(d(n)\), the number of divisors of \(n\), counting \(1\) and \(n\) itself;
- \(\sigma(n)\), the sum of divisors of \(n\), again including \(1\) and \(n\);
- \(\varphi(n)\), Euler’s totient function of Unit 5, the number of integers from \(1\) to \(n\) that are coprime to \(n\).
In symbols, with \(\sum_{d \mid n}\) denoting a sum over all positive divisors \(d\) of \(n\), \[ d(n) = \sum_{d \mid n} 1 , \qquad \sigma(n) = \sum_{d \mid n} d . \] For example, the divisors of \(12\) are \(1, 2, 3, 4, 6, 12\), so \(d(12) = 6\) and \(\sigma(12) = 28\). A fourth function, the sum of the proper divisors (all divisors except \(n\) itself), is written \[ s(n) = \sigma(n) - n , \] and it governs Sections 5 and 6. Table 1 lists the four functions for \(n\) up to \(20\), together with the Möbius function \(\mu(n)\) of Section 3; the reader can check any row by listing divisors.