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