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
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\).∎
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:
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,
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\).
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
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.