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.