Number Theory

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: include $n!,\varphi (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(mn)=f(m)f(n)$ whenever $\gcd (m,n)=1$, and totally multiplicative (or completely multiplicative) if this holds for any $m,n$. Note this implies $f(1)=1$ unless $f$ is the zero function. Also, a multiplicative function is completely determined by its behaviour on the prime powers.

Examples: We have seen that the Euler totient function $\varphi$ is mulitplicative but not totally multiplicative (this is one reason it is convenient to have $\varphi (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\mid 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{array}{ccccc}F(mn)& =& \sum _{d\mid mn}f(d)& =& \sum _{r\mid m,s\mid n}f(rs)\\ & =& \sum _{r\mid m,s\mid n}f(r)f(s)& =& \sum _{r\mid m}f(r)\sum _{s\mid n}f(s)\\ & =& F(m)F(n)\end{array}$$

since $r\mid m$ and $s\mid n$ implies $(r,s)=1$. $\blacksquare$

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 $\varphi$ is multiplicative, we have that

Theorem:

$$\sum _{d\mid n}\varphi (n)=n$$

This theorem can also be proved using basic facts about cyclic groups.

Examples: The divisors of $12$ are $\mathrm{1,2,3,4,6,12}$. Their totients are $\mathrm{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\mid 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\mid n}n$ we see that $\sigma (n)$ is multiplicative. In general, we can apply this trick to any power of $n$.

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=2n=\sigma (n)=\sigma (2^{q-1})\sigma (m)=(2^q-1)\sigma (m)$$

hence $2^q\mid \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\mid q$ implies $2^d-1\mid 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 $\mathrm{2,3,5,7,13,17,19,31,67,127,257}$. He made five mistakes: $\mathrm{67,257}$ should not be on the list, and he missed $\mathrm{61,89,107}$.

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=\mathrm{0,...,4}$ (which give the primes $\mathrm{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.