The integers up to 100,000 wound into a spiral on a dark ground, each drawn as a dot whose size grows with its number of divisors, so that numbers with many divisors form bright diagonal lines
Unit 06 · All masterclasses · 65 min

Arithmetic Functions and Perfect Numbers

Counting and adding divisors, multiplicative functions, Möbius inversion, and the perfect numbers
Image: Cortexd, Wikimedia Commons, CC BY-SA 3.0

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.

Preview: the beginning of the unit

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.

The full unit is part of the program

Want to see a complete unit first? Unit 3, Prime Numbers and Unique Factorization, is free to read.