Multiplicative Arithmetical Functions

Show that

are multiplicative arithmetical functions.

Let $n = p_1^{k_1}p_2^{k_2}\cdots p_\nu^{k_\nu }$, where $p_1,p_2,\ldots ,p_\nu$ are distinct prime numbers. Then we have

for example

The values of the quotient

can be arranged in a two-way classification table (rows indexed by the prime $p$, columns by the exponent $k$). Determine all $n$ for which $\tau (n) \geq \varphi (n)$.

Let $a,b,c,d,\ldots ,k,l$ be positive integers, $M$ their least common multiple, let $(a,b), (a,c), \ldots , (a,b,c), \ldots$ denote as usual the greatest common divisors of $a$ and $b$, $a$ and $c, \ldots , a, b$ and $c, \ldots$ respectively. If $f(n)$ is a multiplicative function, then we have

Let $f(n)$ be a multiplicative arithmetical function. Then we have

where the infinite product is extended over all prime numbers $p$ and formed by taking products only of finitely many factors different from $1^{-s}$.

Show that

Let $a(n)$ be the greatest odd divisor of $n$. Then we have

Prove that

Consider all possible factorizations of an even integer of the form $n=\alpha \beta$, such that $\alpha$ is odd (possibly 1) and $\beta$ is even. Then

is equal to the sum of the divisors of $n/2$.

Let $P(n,k)$ denote the number of decompositions of $n$ into a product of $k$ factors; only positive integers greater than 1 are admissible as factors, and two decompositions are regarded as equal if, and only if, they involve the same factors in the same order. For instance, $P(12,2)=4$ and $P(12,3)=3$ since

Show that, for $n\geq 2$,

the difference between the number of even'' and odd'' decompositions, that is, decompositions into an even and an odd number of factors, respectively. For instance

(continued). Show that

equals $1/m$ if $n=p^m$, the $m$th power of a prime number $p$, but equals 0 if $n$ is divisible by more than one prime. In the case $n=12$ we have

(continued). If $n$ is the product of $m$ different prime factors, then

(cf. the introduction to Problem 186 of Part I).

If $p$ is a prime and $m$ a positive integer, then

(For this particular case, verify 58.1 by using the binomial theorem; also cf. 58.2 with Problem 38 of Part I.)

For $n>1$ let $Q(n)$ denote the number of different decompositions of the integer $n$ into a product of integers greater than 1; two decompositions are not regarded as different if they involve the same factors, and so the order of factors does not matter (in contrast to 58.1); define $Q(1)=1$. For instance $Q(12)=4$. If $n$ is the product of $m$ different prime factors, then

(cf. the introduction to Problem 186 of Part I).

(continued). Show that

Let $n$ be a positive integer,

where $2, p_1,\ldots ,p_\mu ,q_1,\ldots ,q_\nu$ are distinct primes, $p_1\equiv \cdots \equiv p_\mu \equiv 1$, $q_1\equiv \cdots \equiv q_\nu \equiv 3 \pmod4$. Set

if $l_1,l_2,\ldots ,l_\nu$ are all even, and $\delta (n)=0$ otherwise. Show that $\delta (n)$ is, in fact, the difference between the numbers of two different kinds of divisors of $n$:

where the summation is extended over the odd divisors $t'$ of $n$.

($4\delta (n)$ is the number of lattice points on the circle $x^2+y^2=n$. This fact was discovered by Gauss.)

Which of the functions $P(n,2), P(n,3), \ldots , Q(n)$ and $\delta (n)$ are multiplicative?

Let $f(n)$ and $g(n)$ be multiplicative arithmetical functions. Then the arithmetical function

is also multiplicative.

The number of different kinds of regular $n$-gons, one convex, the others self-intersecting, is equal to $\tfrac 12\varphi (n)$.

The sum of all positive proper fractions that, when reduced to their lowest terms, have denominator $n$, is equal to $\tfrac 12\varphi (n)$, $n\geq 2$.

Let $a,b,c$ be positive integers. Among the $c$ fractions

there are $\varphi (bc)/\varphi (b)$ irreducible fractions, if $(a,b,c)=1$. If $(a,b,c)>1$, then they are of course all reducible.

How many irreducible fractions are there among the following $n^2$ fractions:

Let $\Phi (n)$ be the number of irreducible fractions among the following $n^2$ fractions:

($i=\sqrt{-1}$; the fraction $(a+ib)/n$ is called reducible if $(a,b,n)>1$, irreducible if $(a,b,n)=1$.) The function $\Phi (n)$ has the following properties: