# 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

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

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

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**:

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,

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

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

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.

*blynn@cs.stanford.edu*💡