Multiplicative Functions

An arithmetical function, or number-theoretic function is a complex-valued function defined for all positive integers. It can be viewed as a sequence of complex numbers.

Examples: \(n!, \phi(n), \pi(n)\) which denotes the number of primes less than or equal to \(n\).

An arithmetical function is multiplicative if \(f(m n) = f(m)f(n)\) whenever \(\gcd(m,n)=1\), and totally multiplicative or completely multiplicative if this holds for any \(m, n\). Thus \(f(1) = 1\) unless \(f\) is the zero function, and a multiplicative function is completely determined by its behaviour on the prime powers.

Examples: We have seen that the Euler totient function \(\phi\) is multiplicative but not totally multiplicative (this is one reason it is convenient to have \(\phi(1) = 1\)). The function \(n^2\) is totally multiplicative. The product of (totally) multiplicative functions is (totally) multiplicative.

Theorem: Let \(f(n)\) be a multiplicative function, and define

\[ F(n) = \sum_{d|n} f(d) .\]

Then \(F(n)\) is also a multiplicative function.

Proof: Let \(m,n\) be positive integers with \(\gcd(m,n)=1\). Then

\[ \begin{aligned} F(m n) &=& \sum_{d| m n} f(d) \\ &=& \sum_{ r | m , s | n } f(r s) \\ &=& \sum_{ r | m , s | n } f(r) f(s) \\ &=& \sum_{ r | m } f(r) \sum_{ s | n } f(s) \\ &=& F(m) F(n) \end{aligned} \]

since \(r | m\) and \(s | n\) implies \((r,s) = 1\).∎

We just wrote \(F(n)\) in terms of \(f(d)\). Can we do the reverse? That is, write \(f(n)\) in terms of \(F(d)\)? Yes; this is known as Möbius inversion.

Since \(\phi\) is multiplicative, we have that

Theorem:

\[ \sum_{d|n} \phi(n) = n \]

This theorem can also be proved using basic facts about cyclic groups.

Examples: The divisors of \(12\) are \(1,2,3,4,6,12\). Their totients are \(1,1,2,2,2,4\) which sum to \(12\).

The function \(f(n) = 1\) is (totally) multiplicative. Let \(d(n)\) be the number of divisors of \(n\). Then since \( d(n) = \sum_{d|n} 1 \) we see that \(d(n)\) is multiplicative.

The function \(f(n) = n\) is (totally) multiplicative. Let \(\sigma(n)\) be the sum of divisors of \(n\). Then since \( \sigma(n) = \sum_{d|n} n \) we see that \(\sigma(n)\) is multiplicative. In general, we can apply this trick to any power of \(n\).

Perfect Numbers

A positive integer \(n\) is a perfect number if \(\sigma(n) = 2n\). The first perfect numbers are \(6, 28, 496, 8128\).

It is not known if any odd perfect numbers exist.

Let \(n\) be an even perfect number, so \(n = 2^{q-1} m\) for some \(q> 1\) and odd \(m\). Since \(\sigma\) is multiplicative,

\[ 2^q m = 2 n = \sigma(n) = \sigma(2^{q-1})\sigma(m) = (2^q - 1)\sigma(m) \]

hence \(2^q | \sigma(m)\), so write \(\sigma(m) = 2^q s\) for some \(s\) and hence \((2^q - 1)s = m\).

Thus two of the divisors of \(m\) are \(s\) and \(m = (2^q -1)s\). But these already sum to \(2^q s\), hence \(m\) can have no other divisors, implying that \(s = 1\) and \(m = 2^q - 1\) is prime. The converse is clear, thus \(n\) is an even perfect number if and only if

\[ n = 2^{q-1}(2^q - 1) \]

with \(2^q -1\) prime.

This implies \(q\) is prime as \(d |q\) implies \(2^d - 1 | 2^q - 1\). The converse is unsurprisingly false. A number of the form \(2^q -1\) is called a Mersenne number, and if it is prime, then it is called a Mersenne prime.

Mersenne conjectured that for \(q\le 257\) the only primes \(q\) which yielded primes \(2^q - 1\) were \(2,3,5,7,13,17,19,31,67,127,257\). He made five mistakes: \(67,257\) should not be on the list, and he missed \(61,89,107\).

Modulo 10, the powers of 2 cycle through 2, 4, 8, 6, hence \(n = 2^{q-1} (2^q - 1)\) cycles through \(2(4-1), 4(8-1), 8(6-1), 6(2-1)\). The third of these is 0, implying 5 divides \(n\) which means \(n\) cannot be perfect, because 5 is not one below a power of 2. The other possibilities imply every even perfect number ends with 6 or 8.

Applying a similar but more exhausting calculation modulo 100 for \(q > 2\), we find even perfect numbers other than 6 must end with 28 or an odd digit followed by 6.

Fermat Numbers

What about numbers of the form \(2^r + 1\)?

It is not hard to see that if \(2^r + 1\) is prime then \(r\) must be a power of 2. Numbers of the form \(2^{2^m}+1\) are called Fermat numbers, and are called Fermat primes if prime. Fermat conjectured that all Fermat numbers are prime, and he was right for \(m = 0,...,4\) (which give the primes \(3,5,17,257,65537\)), but wrong for \(m = 5\) (which is divisible by 641) and other values of \(m\). In fact no other Fermat primes are known.

It can be shown that a regular \(n\)-gon that can be constructed using a ruler and compass if and only if

\[ n = 2^k p_1 ... p_m \]

where each \(p_i\) is a distinct Fermat prime and \(k\) is some nonnegative integer. In 1796, Gauss proved the sufficiency of this condition (though not the necessity) when he was only 19.


Ben Lynn blynn@cs.stanford.edu 💡