4.6: Exercise

Exercise \(\PageIndex{1}\)

Decide which functions are not multiplicative, multiplicative, or completely multiplicative (see Definition 4.2).

1. \(f(n) = 1\).
2. \(f(n) = 2\).
3. \(f(n) = \sum_{i=1}^{n} i\).
4. \(f(n) = \prod_{i=1}^{n} i\).
5. \(f(n) = n\).
6. \(f(n) = nk\).
7. \(f(n) = \sum_{d|n} d\).
8. \(f(n) = \prod_{d|n} d\).

Exercise \(\PageIndex{2}\)

1. Let \(h(n) = 0\) when \(n\) is even, and \(1\) when \(n\) is odd. Show that \(h\) is multiplicative.
2. Now let \(H(n) = \sum_{d|n} h(d)\). Show without using Proposition 4.3 that \(H\) is multiplicative. (Hint: write \(a = 2^{k} \prod_{i=1}^{r} p_{i}^{l_{i}}\) by unique factorization, where the \(p_{i}\) are odd primes. Similarly for b.)
3. What does Proposition 4.3 say?

Exercise \(\PageIndex{3}\)

1. Compute the numbers \(\sigma_{1} (n) = \sigma (n)\) of Definition4.4 for \(n \in \{1, \cdots , 30\}\) without using Theorem 4.5.
2. What is the only value \(n\) for which \(\sigma (n) = n\)?
3. Show that \(\sigma (p) = p+1\) whenever \(p\) is prime.
4. Use (c) and multiplicativity of \(\sigma\) to check the list obtained in (a).
5. For what values of \(n\) in the list of (a) is \(n | \sigma (n)\)? (Hint: 6 and 28.)

Exercise \(\PageIndex{4}\)

1. Compute the numbers \(\sigma_{0} (n) = \tau (n)\) of Definition 4.4 for \(n \in \{1, \cdots , 30\}\) without using Theorem 4.5.
2. What is the only value \(n\) for which \(\tau (n) = 1\)?
3. Show that \(\tau (p) = 2\) whenever \(p\) is prime.
4. Use (c) and multiplicativity of \(\tau\) to check the list obtained in (a).

Exercise \(\PageIndex{5}\)

1. Compute the numbers \(\varphi\) of Definition 4.9 for \(n \in \{1, \cdots , 30\}\) without using Theorem 4.16.
2. What is \(\varphi (p)\) when \(p\) is a prime?
3. How many positive numbers less than \(pn\) are not divisible by \(p\)?
4. Use (c) and multiplicativity of \(\varphi\) to check the list obtained in (a).

Exercise \(\PageIndex{6}\)

1. Compute the numbers \(\mu (n)\) of Definition 4.6 for \(n \in \{1, \cdots , 30\}\).
2. What is \(\mu (p)\) when \(p\) is a prime?
3. Use (c) and multiplicativity of \(\mu\) to check the list obtained in (a).

Exercise \(\PageIndex{7}\)

Let \(\tau (n)\) be the number of distinct positive divisors of \(n\). Answer the following question without using Theorem 4.5.

1. Show that \(\tau\) is multiplicative.
2. If \(p\) is prime, show that \(\tau (p^k) = k+1\).
3. Use the unique factorization theorem, to find an expression for \(\tau (n)\) for \(n \in \mathbb{N}\).

Exercise \(\PageIndex{8}\)

Two positive integers \(a\) and \(b\) are called amicable if \(\sigma (a)= \sigma (b) = a+b\). The smallest pair of amicable numbers is is formed by \(220\) and \(284\).

1. Use Theorem 4.5 to show that \(220\) and \(284\) are amicable.
2. The same for \(1184\) and \(1210\).

Exercise \(\PageIndex{9}\)

A positive integer \(n\) is called perfect if \(\sigma (n) = 2n\).

1. Show that \(n\) is perfect if and only if the sum of its positive divisors less than \(n\) equals \(n\).
2. Show that if \(p\) and \(2^{p}-1\) are primes, then \(n = 2^{p-1}(2^{p}-1)\) is perfect. (Hint: use Theorem 4.5 and exercise 4.3(c).)
3. Use exercise 1.14 to show that if \(2^{p}-1\) is prime, then \(p\) is prime, and thus \(n = 2^{p-1} (2^{p}-1)\) is perfect.
4. Check that this is consistent with the list in exercise 4.3.

Exercise \(\PageIndex{10}\)

Draw the following directed graph \(G\): the set of vertices \(V\) represent \(0\) and the natural numbers between \(1\) and \(50\). For \(a, b \in V\), a directed edge \(ab\) exists if \(\sigma (a)-a = b\). Finally, add a loop at the vertex representing \(0\). Notice that every vertex has \(1\) outgoing edge, but may have more than \(1\) incoming edge.

1. Find the cycles of length \(1\) (loops). The non-zero of these represent perfect numbers.
2. Find the cycles of length \(2\) (if any). A pair of numbers \(a\) and \(b\) that form a cycle of length \(2\) are called amicable numbers. Thus for such a pair, \(\sigma (b)-b = a\) and \(\sigma (a)-a = b\).
3. Find any longer cycles. Numbers represented by vertices in longer cycles are called sociable numbers.
4. Find numbers whose path ends in a cycle of length \(1\). These are called aspiring numbers.
5. Find numbers (if any) that have no incoming edge. These are called untouchable numbers.
6. Determine the paths starting at \(2193\) and at \(562\). (Hint: both end in a cycle (or loop).)

A path through this graph is called an aliquot sequence. The so-called Catalan-Dickson conjecture says that every aliquot sequence ends in some finite cycle (or loop). However, even for a relatively small number such as 276, it is unknown (in 2017) whether its aliquot sequence ends in a cycle.

Exercise \(\PageIndex{11}\)

In this exercise, we give a different proof of Theorem 4.16. It uses the principle of inclusion-exclusion [21]. We state it here for completeness. Let \(S\) be a finite set with subsets \(A_{1}, A_{2}\), and so on through \(A_{r}\). Then, if we denote the cardinality of a set \(A\) by \(|A|\),

\[|S- \bigcup_{i=1}^{r} A_{i}| = |S|-|S_{1}|+|S_{2}|-\cdots+(-1)^{r}|S_{r}| \nonumber\]

where \(|S_{l}|\) is the sum of the sizes of all intersections of \(l\) members of \(\{A_{1}, \cdots, A_{r}\}\).

Now, in the following we keep to the following conventions. Using prime factorization, write

\[n = \prod_{i=1}^{r} p_{i}^{k_{i}} \nonumber\]

\[A_{i} = \{z \in S | p_{i} \mbox{ divides } z\} \nonumber\]

\[S = \{1, 2 \cdots n\} \mbox{ and } R = \{1,2 \cdots r\} \nonumber\]

\[ I_{l} \subseteq R \mbox{ such that } |I_{l}| = l \nonumber\]

1. Show that \(\varphi (n) = |S-\bigcup_{i=1}^{r} A_{i}\). (Hint: any number that is not co-prime with \(n\) is a multiple of at least one of the \(p_{i}\).)
2. Show that \(|A_{i}| = \frac{n}{p_{i}}\)
3. Show that \(|\bigcap_{i \in I_{l}} A_{i}| = n \prod_{i \in I_{l}} \frac{1}{p_{i}}\). (Hint: use Corollary 3.7.)
4. Showthat \(|S_{l}| = n \sum_{I_{l} \subseteq R} \prod_{i \in I_{l}} \frac{1}{p_{i}}\).
5. Show that the principle of inclusion-exclusion implies that \(|S-\bigcup_{i=1}^{r} A_{i}| = n+n \sum_{l=1}^{r} (-1)^{l} \sum_{I_{l} \subseteq R} \prod_{i \in I_{l}} \frac{1}{p_{i}}\).
6. Show that \(n+n \sum_{l=1}^{r} (-1)^{l} \sum_{I_{l} \subseteq R} \prod_{i \in I_{l}} \frac{1}{p_{i}} = n \prod_{i=1}^{r} (1-\frac{1}{p_{i}})\). Notice that this implies Theorem 4.16. (Hint: write out the product \(\prod_{i=1}^{r} (1-\frac{1}{p_{i}})\).)

Exercise \(\PageIndex{12}\)

Let \(F(n) = n = \sum_{d|n} f(n)\). Use the Mobius inversion formula(or \(f(n) = \sum_{d|n} \mu (d) F(\frac{n}{d})\)) to find \(f(n)\). (Hint: substitute the Mobius function of Definition 4.6 and use multiplicativity where needed.)

Exercise \(\PageIndex{13}\)

1. Compute the sets \(S_{n}\) and \(T_{n}\) of Lemma 4.13 explicitly for \(n = 4\) and \(n = 12\).
2. Perform the resummation done in equations 4.1 and 4.2 explicitly for \(n = 4\) and \(n = 12\).

Exercise \(\PageIndex{14}\)

Recall the definition of Dirichlet convolution \(f \ast g\) of the arithmetic functions \(f\) and \(g\). (Definition 4.18)

1. Show that Dirichlet convolution is commutative, that is \[f \ast g = g \ast f \nonumber\]
2. Show that Dirichlet convolution is associative, that is \[(f \ast g) \ast h = g \ast (f \ast h) \nonumber\]
3. Show that Dirichlet convolution is distributive, that is \[(f \ast (g+h) = f \ast g + f \ast h) \nonumber\]
4. The binary operation Dirichlet convolution has an identity \(\epsilon\), defined by \[f \ast \epsilon = \epsilon \ast f = f \nonumber\] Show that the function \(\epsilon\) of Lemma 4.12 is the identity of the convolution.

Exercise \(\PageIndex{15}\)

Use exercise 4.14 to prove the following:

1. Show that the Dirichlet convolution of two multiplicative functions is multiplicative.
2. Show that the sum of two multiplicative functions is not necessarily multiplicative. (Hint: \(\epsilon+\epsilon\)).

Exercise \(\PageIndex{16}\)

See Definition 4.11. Definr \(f(n) \equiv \tau (n^2)\) and \(g(n) \equiv 2^{\omega (n)}\)

1. Compute \(\omega(n), f(n),\) and \(g(n)\) for \(n\) equals \(10^n\) and \(6!\).
2. For \(p\) prime, show that \(\tau (p^{2k}) = \sum_{d|p^k} 2^{\omega(d)} = 2k+1\). (Hint: use Theorem 4.5.)
3. Show that \(f\) is multiplicative. (Hint: use that \(\tau\) is multiplicative.)
4. Use (d) to show that \(g\) is multiplicative.
5. Show that \[\tau (n^{2}) = \sum_{d|n} 2^{\omega(d)} \nonumber\]

Exercise \(\PageIndex{17}\)

Let \(S(n)\) denote the number of square free divisors of \(n\) with \(S(1) = 1\) and \(\omega(n)\) the number of distinct prime divisors of \(n\). See also Definition 4.11.

1. Show that \(S(n) = \sum_{d|n} |\mu(d)|\). (Hint: use definition 4.6)
2. Show that \(S(n) = 2^{\omega(n)}\). (Hint: let \(W\) be the set of prime divisors of \(n\). Then every square free divisor corresponds to a subset -product- of those primes. How many subsets of primes are there in \(W\)?)
3. Conclude that \[\sum_{d|n} |\mu (d)| = 2^{\omega(n)} \nonumber\]

Exercise \(\PageIndex{18}\)

Define the Liouville \(\lambda\)-function by \(\lambda (1) = 1\) and \(\lambda (n) = (-1)^{\Omega(n)}\).

1. Compute \(\lambda (10n)\) and \(\lambda (6!)\).
2. Show that \(\lambda\) is multiplicative. (Hint: \(\Omega(n)\) is completely additive.)
3. Use Proposition 4.3 to show that \(F(n) = \sum_{d|n} \lambda (d)\) is multiplicative.
4. For \(p\) prime, show that \[\sum_{d|p^k} \lambda (d) = \sum_{i=0}^{k} (-1)^i \nonumber\] which equals \(1\) if \(k\) is even and \(0\) if \(k\) is odd.
5. Use (c) and (d) to conclude that \[F(n) = \sum_{d|n} \lambda (d)= \left \{ \begin{array} {cc} {1}&{\mbox{if } n = m^2}\\ {0}&{\mbox{else}} \end{array} \right. \nonumber\]

Exercise \(\PageIndex{19}\)

Let \(f\) be a multiplicative function.
Define \(q(n) \equiv \sum_{d|n} \mu (d)f(d)\), where \(\mu\) is the Mobius function.

1. Show that \(f(1)=1\).
2. Show that \(f \mu\) (their product) is multiplicative.
3. Use Proposition 4.3 to show that \(q(n)\) is multiplicative.
4. Show that if \(p\) is prime, then \(q(p^k) = f(1)-f(p) = 1-f(p)\).
5. Use (c) and (d) to show that \[q(n) = \sum_{d|n} \mu (d) f(d)= \prod_{p prime, p|n} (1-f(p)) \nonumber\]

Exercise \(\PageIndex{20}\)

Use exercise 4.19 (e) and the definition of \(\omega\) in exercise 4.16 and \(\lambda\) in exercise 4.18 to show that

\[\sum_{d|n} \mu (d) \lambda (d) = 2 \omega (n) \nonumber\]

Exercise \(\PageIndex{21}\)

1. Show that for all \(n \in \mathbb{N}, \mu (n) \mu (n+1) \mu (n+2) \mu (n+3)= 0\). (Hint: divisibility by 4.)
2. Show that for any integer \(n \ge 3\), \(\sum^{n}_{k = 1} \mu (k!) = 1\). (Hint: use (a).)

Exercise \(\PageIndex{22}\)

1. Use Euler’s product formula and the sequence \(\mu\) of Definition 4.6 to show that \[\frac{1}{\zeta (s)} = \prod_{p prime} (1-p^{-s}) = \prod_{p prime} (\sum_{i \ge 0} \mu (p^{i})p^{-is} \nonumber\]
2. Without using equation (4.7), prove that the expression in (a) equals \(\sum_{n \ge 1} \mu (n) n^{-s}\). (Hint: since \(\mu\) is multiplicative, you can write a proof re-arranging terms as in the first proof of Euler’s product formula.)

Exercise \(\PageIndex{23}\)

1. Use equation (4.8) to show that \[\zeta (s-1) = \sum_{a \ge 1} \frac{a}{a^s} \sum_{b \ge 1} \frac{\mu (b)}{b^s} \nonumber\]
2. Use Lemma 4.23 and the first equality of equation (4.3) to show that \[\frac{\zeta (s-1)}{\zeta (s)} = \sum_{n \ge 1} \varphi (n^s) \nonumber\]

Exercise \(\PageIndex{24}\)

1. Use Corollary 4.22 to show that \[\zeta (s-k) = \sum_{a \ge 1} \frac{\sigma_{k} (a)}{a^s} \sum_{b \ge 1} \frac{\mu (b)}{b^s} \nonumber\]
2. Show that \[\zeta (s-k) = \sum_{n \ge 1} (\sigma_{k} \ast \mu) (n) n^{-s} \nonumber\] where \(\ast\) means the Dirichlet convolution (Definition 4.18).