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)\) (the last example \(\pi(n)\) is 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 mulitplicative 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

\[ \array { 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) } \]

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

Above we have written \(F(n)\) in terms of \(f(d)\). One question that naturally arises is this: can we do the reverse? That is, write \(f(n)\) in terms of \(F(d)\)? 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\gt 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\).

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 💡