# 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 💡