Chapter 2. Applications of Unique Factorization
Loading mathematical notation… If it does not load, check your connection or allow the MathJax script.
Page 18 exercise
Let \(a/b\in\mathbb{Z}_p\) be a nonunit. By definition, \(p\nmid b\), and an element \(a/b\in\mathbb{Z}_p\) is a unit exactly when \(p\nmid a\). Hence \(p\mid a\).
We claim that \(p\nmid a+b\). Indeed, if \(p\mid a+b\), then together with \(p\mid a\) we would obtain \[p\mid(a+b)-a=b,\] contradicting \(p\nmid b\). Therefore \[\frac{b}{a+b}\in\mathbb{Z}_p.\] Finally, \[\left(\frac{a}{b}+1\right)\frac{b}{a+b} =\frac{a+b}{b}\frac{b}{a+b}=1.\] Thus \(b/(a+b)\) is the inverse of \(a/b+1\), so \(a/b+1\) is a unit in \(\mathbb{Z}_p\).
Exercise 1
Suppose, toward a contradiction, that \(k[x]\) has only finitely many monic irreducible polynomials, say \[p_1(x),p_2(x),\ldots,p_\ell(x).\] Consider the nonconstant polynomial \[f(x)=p_1(x)p_2(x)\cdots p_\ell(x)+1.\] For every \(i\), \[f(x)\equiv1\pmod{p_i(x)},\] so none of \(p_1(x),\ldots,p_\ell(x)\) divides \(f(x)\).
Since \(k[x]\) is a Euclidean domain, the nonconstant polynomial \(f(x)\) has an irreducible divisor \(q(x)\). Replacing \(q(x)\) by its monic associate, we may assume that \(q(x)\) is monic. It must then be one of the polynomials \(p_1(x),\ldots,p_\ell(x)\), contradicting the fact that none of them divides \(f(x)\). Therefore \(k[x]\) has infinitely many monic irreducible polynomials.
Exercise 2
Discarding repetitions, we may assume that \(p_1,\ldots,p_t\) are distinct. Let \(R\) denote the given set, and for \(r=a/b\in\mathbb{Q}^\times\) define \[v_i(r)=\operatorname{ord}_{p_i}(a)-\operatorname{ord}_{p_i}(b), \qquad i=1,\ldots,t.\] This is independent of the representation \(a/b\), and the defining condition for \(R\) is simply \(v_i(r)\geq0\) for every \(i\). We also put \(v_i(0)=+\infty\).
The valuation identities give \[v_i(rs)=v_i(r)+v_i(s),\qquad v_i(r+s)\geq\min\{v_i(r),v_i(s)\},\qquad v_i(-r)=v_i(r).\] Thus \(R\) contains \(0\) and \(1\) and is closed under addition, multiplication, and additive inverses. Hence \(R\) is a subring of \(\mathbb{Q}\).
For a nonzero \(r\in R\), \[r\in R^\times \quad\Longleftrightarrow\quad r^{-1}\in R \quad\Longleftrightarrow\quad -v_i(r)\geq0\ \text{for every }i \quad\Longleftrightarrow\quad v_i(r)=0\ \text{for every }i.\] In other words, \(r=a/b\) is a unit precisely when the powers of every \(p_i\) in the numerator and denominator cancel completely.
Now let \(0\neq r\in R\), put \(e_i=v_i(r)\), and set \[u=r\,p_1^{-e_1}\cdots p_t^{-e_t}.\] Then \(v_i(u)=0\) for every \(i\), so \(u\) is a unit, and \[r=u p_1^{e_1}\cdots p_t^{e_t}.\]
It remains to identify the prime elements. For \(r\in R\), \[p_i\mid r \quad\Longleftrightarrow\quad \frac{r}{p_i}\in R \quad\Longleftrightarrow\quad v_i(r)\geq1.\] Consequently, if \(p_i\mid rs\), then \(v_i(r)+v_i(s)=v_i(rs)\geq1\). Since \(v_i(r)\) and \(v_i(s)\) are nonnegative integers, one of them is at least \(1\); hence \(p_i\mid r\) or \(p_i\mid s\). Moreover, \(v_i(p_i)=1\), so \(p_i\) is not a unit. Therefore each \(p_i\) is prime in \(R\).
Conversely, let \(\pi\) be a prime element of \(R\). A prime element in an integral domain is irreducible, and the factorization above gives \[\pi=u p_1^{e_1}\cdots p_t^{e_t}.\] Because \(\pi\) is a nonunit, some \(e_i\) is positive. Irreducibility forces exactly one exponent, say \(e_j\), to be \(1\) and all the others to be \(0\); otherwise the displayed product would split \(\pi\) into two nonunits. Thus \(\pi=u p_j\), so \(\pi\) is associated to \(p_j\). Hence, up to associates, \(p_1,\ldots,p_t\) are the only primes of \(R\).
Exercise 3
Suppose, toward a contradiction, that there are only finitely many primes, say \(p_1,\ldots,p_t\), and put \[n=p_1p_2\cdots p_t.\] Every integer \(a\) with \(2\leq a<n\) has a prime divisor \(p_i\). Since \(p_i\mid n\), we have \((a,n)>1\). Thus only \(1\) among \(1,2,\ldots,n-1\) is relatively prime to \(n\), so \[\phi(n)=1.\]
On the other hand, the formula for Euler’s phi function gives \[\phi(n) =n\prod_{p\mid n}\left(1-\frac1p\right) =\prod_{i=1}^t(p_i-1).\] The list contains both \(2\) and \(3\), and therefore \[\phi(n)=\prod_{i=1}^t(p_i-1)\geq(2-1)(3-1)=2,\] contradicting \(\phi(n)=1\). Hence there are infinitely many primes.
Exercise 4
First let \(p\) be an odd prime such that \[p\mid a^{2^m}+1.\] Then \(a^{2^m}\equiv-1\pmod p\). Since \(n>m\), the integer \(2^{n-m}\) is even, and hence \[a^{2^n} =a^{2^m2^{n-m}} =\left(a^{2^m}\right)^{2^{n-m}} \equiv(-1)^{2^{n-m}} \equiv1\pmod p.\] Thus \(p\mid a^{2^n}-1\).
Suppose now that \(p\) divides both \(a^{2^m}+1\) and \(a^{2^n}+1\). The preceding calculation also gives \(p\mid a^{2^n}-1\), so \[p\mid\bigl(a^{2^n}+1\bigr)-\bigl(a^{2^n}-1\bigr)=2.\] This is impossible because \(p\) is odd. Therefore the two given numbers have no common odd prime divisor, and their greatest common divisor is a power of \(2\).
If \(a\) is even, then both \(a^{2^n}+1\) and \(a^{2^m}+1\) are odd. Their greatest common divisor is therefore odd and at the same time a power of \(2\), so it equals \(1\).
If \(a\) is odd, then both numbers are even, so their greatest common divisor is at least \(2\). Moreover, \(n\geq1\) and \[a^{2^n}=\left(a^2\right)^{2^{n-1}}\equiv1\pmod4,\] whence \(a^{2^n}+1\equiv2\pmod4\). Thus their greatest common divisor is not divisible by \(4\). Being a power of \(2\), it must equal \(2\). Therefore \[\left(a^{2^n}+1,a^{2^m}+1\right) = \begin{cases} 1,& a\text{ is even},\\ 2,& a\text{ is odd}. \end{cases}\]
Exercise 5
For \(n\geq0\), set \[N_n=2^{2^n}+1.\] Since \(2\) is even, Exercise 4 shows that \[(N_m,N_n)=1\qquad(m\neq n).\] Thus the integers \(N_0,N_1,N_2,\ldots\) are pairwise relatively prime.
Each \(N_n\) is greater than \(1\), so it has a prime divisor; choose one and call it \(q_n\). If \(q_m=q_n\) for some \(m\neq n\), then this prime would divide both \(N_m\) and \(N_n\), and hence would divide \((N_m,N_n)=1\), which is impossible. Therefore \(q_0,q_1,q_2,\ldots\) are distinct primes, proving that there are infinitely many primes.
Exercise 6
In the product \[n!=1\cdot2\cdots n,\] every multiple of \(p\) contributes at least one factor of \(p\). There are \(\lfloor n/p\rfloor\) such multiples. Among them, the multiples of \(p^2\) contribute one additional factor of \(p\), and there are \(\lfloor n/p^2\rfloor\) of these. Likewise, the multiples of \(p^3\) contribute yet another factor of \(p\), and so on. Adding these successive layers gives \[\operatorname{ord}_p(n!) =\left\lfloor\frac{n}{p}\right\rfloor +\left\lfloor\frac{n}{p^2}\right\rfloor +\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots.\]
Equivalently, this counting can be written compactly as \[\operatorname{ord}_p(n!) =\sum_{j=1}^{n}\operatorname{ord}_p(j) =\sum_{k\geq1}\#\{j\leq n:p^k\mid j\} =\sum_{k\geq1}\left\lfloor\frac{n}{p^k}\right\rfloor.\] When \(p^k>n\), the corresponding summand is zero, so the displayed sum has only finitely many nonzero terms.
Exercise 7
By Exercise 6 and the inequality \(\lfloor x\rfloor\leq x\), \[\begin{aligned} \operatorname{ord}_p(n!) &=\sum_{k\geq1}\left\lfloor\frac{n}{p^k}\right\rfloor\\ &\leq n\sum_{k\geq1}\frac{1}{p^k}\\ &=n\left(\frac1p+\frac1{p^2}+\frac1{p^3}+\cdots\right)\\ &=n\frac{1/p}{1-1/p} =\frac{n}{p-1}. \end{aligned}\]
For the second inequality, use the prime factorization of \(n!\): \[n!=\prod_{p\mid n!}p^{\operatorname{ord}_p(n!)}.\] Taking \(n\)th roots and applying the preceding estimate to each prime gives \[\begin{aligned} \sqrt[n]{n!} &=\prod_{p\mid n!}p^{\operatorname{ord}_p(n!)/n}\\ &\leq\prod_{p\mid n!}p^{1/(p-1)}. \end{aligned}\] Thus the second assertion follows by comparing, prime by prime, the exponents in the factorization of \(n!\).
Exercise 8
First pair the two copies of \(n!\) in opposite orders: \[(n!)^2 =\prod_{k=1}^{n}k(n+1-k).\] For \(1\leq k\leq n\), \[k(n+1-k)-n=(k-1)(n-k)\geq0,\] so every factor in the product is at least \(n\). Hence \[(n!)^2\geq n^n, \qquad\text{and therefore}\qquad \sqrt[n]{n!}\geq\sqrt n.\]
Combining this with Exercise 7 gives \[\sqrt n \leq\sqrt[n]{n!} \leq\prod_{p\mid n!}p^{1/(p-1)} =\prod_{p\leq n}p^{1/(p-1)}.\]
Suppose, toward a contradiction, that there are only finitely many primes, say \(p_1,\ldots,p_t\). For every \(n\geq\max\{p_1,\ldots,p_t\}\), the rightmost product is the fixed constant \[C=\prod_{i=1}^{t}p_i^{1/(p_i-1)}.\] The preceding inequality would then imply \(\sqrt n\leq C\) for arbitrarily large \(n\), which is impossible because \(\sqrt n\to\infty\). Therefore there are infinitely many primes.
Exercise 9
Let \(n>1\). By unique factorization, \[n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r},\] where \(p_1,\ldots,p_r\) are distinct primes. The prime powers in this factorization are pairwise relatively prime, so repeated application of multiplicativity gives \[f(n) =f\left(p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}\right) =\prod_{i=1}^{r}f\left(p_i^{e_i}\right).\] Thus the values of \(f\) on prime powers determine its value at every positive integer. Notice that multiplicativity alone does not imply \(f(p^e)=f(p)^e\), since powers of the same prime are not relatively prime.
Here a multiplicative function is understood in the standard sense as an arithmetic function on the positive integers, with \(f(1)=1\). If “integers” is interpreted literally as all of \(\mathbb{Z}\), then the values on positive prime powers do not by themselves determine \(f(-1)\) or \(f(0)\). Indeed, for \(n>0\) one has \[f(-n)=f(-1)f(n),\] because \((-1,n)=1\), while the value at \(0\) requires a separate convention. Hence the statement for all of \(\mathbb{Z}\) needs these additional data.
Exercise 10
Let \((a,b)=1\). The essential point is the following bijection between divisors: \[\{d:d\mid ab\} \longleftrightarrow \{(d_1,d_2):d_1\mid a,\ d_2\mid b\}, \qquad d=d_1d_2.\] Indeed, \(a\) and \(b\) have disjoint sets of prime divisors. Given \(d\mid ab\), put into \(d_1\) the prime-power factors of \(d\) coming from \(a\), and into \(d_2\) those coming from \(b\). This gives \(d_1\mid a\), \(d_2\mid b\), and \(d=d_1d_2\). Unique factorization makes this decomposition unique. Conversely, every such pair produces a divisor \(d_1d_2\) of \(ab\).
Moreover, \((d_1,d_2)=1\), since \(d_1\mid a\), \(d_2\mid b\), and \((a,b)=1\). Therefore multiplicativity of \(f\) gives \[f(d_1d_2)=f(d_1)f(d_2).\] Using the bijection above, we may now rewrite the divisor sum as \[\begin{aligned} g(ab) &=\sum_{d\mid ab}f(d)\\ &=\sum_{\substack{d_1\mid a\\d_2\mid b}}f(d_1d_2)\\ &=\sum_{\substack{d_1\mid a\\d_2\mid b}}f(d_1)f(d_2)\\ &=\left(\sum_{d_1\mid a}f(d_1)\right) \left(\sum_{d_2\mid b}f(d_2)\right)\\ &=g(a)g(b). \end{aligned}\] Hence \(g\) is multiplicative.
Exercise 11
Define \[h(n)=\frac{\mu(n)}{n}.\] If \((a,b)=1\), then multiplicativity of \(\mu\) gives \[h(ab) =\frac{\mu(ab)}{ab} =\frac{\mu(a)\mu(b)}{ab} =h(a)h(b).\] Thus \(h\) is multiplicative. By Exercise 10, its divisor sum \[H(n)=\sum_{d\mid n}h(d) =\sum_{d\mid n}\frac{\mu(d)}{d}\] is also multiplicative. Since the function \(n\mapsto n\) is completely multiplicative, the pointwise product \[F(n)=nH(n)=n\sum_{d\mid n}\frac{\mu(d)}{d}\] is multiplicative as well.
It remains to compare \(F\) with \(\phi\) on prime powers. For a prime \(p\) and \(e\geq1\), the only divisors of \(p^e\) on which \(\mu\) is nonzero are \(1\) and \(p\). Therefore \[\begin{aligned} F(p^e) &=p^e\sum_{d\mid p^e}\frac{\mu(d)}{d}\\ &=p^e\left(1-\frac1p\right)\\ &=p^e-p^{e-1} =\phi(p^e). \end{aligned}\] Both \(F\) and \(\phi\) are multiplicative and agree on every prime power. Exercise 9 therefore implies that they agree on every positive integer. Consequently, \[\phi(n)=n\sum_{d\mid n}\frac{\mu(d)}{d}.\]
Exercise 12
Write \[n=p_1^{e_1}\cdots p_r^{e_r}.\] If a divisor \(d\) contains the square of a prime, then \(\mu(d)=0\). Consequently, only the squarefree divisors contribute to any of the three sums. These divisors are indexed by subsets \(S\subseteq\{1,\ldots,r\}\): \[d=\prod_{i\in S}p_i,\qquad \mu(d)=(-1)^{|S|},\qquad \phi(d)=\prod_{i\in S}(p_i-1).\]
For the first sum, expansion of a finite product gives \[\begin{aligned} \sum_{d\mid n}\mu(d)\phi(d) &=\sum_{S\subseteq\{1,\ldots,r\}} (-1)^{|S|}\prod_{i\in S}(p_i-1)\\ &=\prod_{i=1}^{r}\bigl(1-(p_i-1)\bigr)\\ &=\prod_{p\mid n}(2-p). \end{aligned}\]
Similarly, \[\begin{aligned} \sum_{d\mid n}\mu(d)^2\phi(d)^2 &=\sum_{S\subseteq\{1,\ldots,r\}} \prod_{i\in S}(p_i-1)^2\\ &=\prod_{p\mid n}\bigl(1+(p-1)^2\bigr)\\ &=\prod_{p\mid n}(p^2-2p+2), \end{aligned}\] and \[\begin{aligned} \sum_{d\mid n}\frac{\mu(d)}{\phi(d)} &=\sum_{S\subseteq\{1,\ldots,r\}} (-1)^{|S|}\prod_{i\in S}\frac{1}{p_i-1}\\ &=\prod_{p\mid n}\left(1-\frac{1}{p-1}\right)\\ &=\prod_{p\mid n}\frac{p-2}{p-1}. \end{aligned}\] The formulas also hold for \(n=1\), with each empty product interpreted as \(1\).
Exercise 13
For a fixed integer \(k\geq0\), let \(f_k(n)=n^k\). Since \[f_k(ab)=(ab)^k=a^kb^k=f_k(a)f_k(b),\] the function \(f_k\) is completely multiplicative. Exercise 10 therefore shows that its divisor sum \[\sigma_k(n)=\sum_{d\mid n}f_k(d)=\sum_{d\mid n}d^k\] is multiplicative.
To obtain the formula, write \[n=p_1^{e_1}\cdots p_r^{e_r}.\] Every divisor of \(n\) has a unique representation \[d=p_1^{j_1}\cdots p_r^{j_r}, \qquad 0\leq j_i\leq e_i.\] Consequently, \[\begin{aligned} \sigma_k(n) &=\sum_{j_1=0}^{e_1}\cdots\sum_{j_r=0}^{e_r} p_1^{kj_1}\cdots p_r^{kj_r}\\ &=\prod_{i=1}^{r} \left(1+p_i^k+p_i^{2k}+\cdots+p_i^{e_i k}\right). \end{aligned}\] Thus \[\sigma_k(n) =\prod_{p^e\parallel n} \left(1+p^k+p^{2k}+\cdots+p^{ek}\right).\] For \(k>0\), the geometric-series formula gives the equivalent expression \[\sigma_k(n) =\prod_{p^e\parallel n} \frac{p^{k(e+1)}-1}{p^k-1}.\] When \(k=0\), one instead obtains the number of positive divisors of \(n\): \[\sigma_0(n)=\prod_{p^e\parallel n}(e+1).\]
Exercise 14
Short proof using Dirichlet convolution. The function in the exercise is precisely the Dirichlet convolution \(h=\mu*f\), since \(h(n)=\sum_{d\mid n}\mu(n/d)f(d)\). Both \(\mu\) and \(f\) are multiplicative, and the Dirichlet convolution of two multiplicative functions is multiplicative. Hence \(h\) is multiplicative.
Direct proof in detail. Let \((a,b)=1\). Because \(a\) and \(b\) have no prime factor in common, every divisor \(d\) of \(ab\) can be written uniquely as \[d=d_1d_2, \qquad d_1\mid a, \qquad d_2\mid b.\] Indeed, the prime-power factors of \(d\) coming from \(a\) form \(d_1\), and those coming from \(b\) form \(d_2\). In particular, \[(d_1,d_2)=1 \qquad\text{and}\qquad \left(\frac{a}{d_1},\frac{b}{d_2}\right)=1.\] Using the multiplicativity of \(f\) and \(\mu\), the required identity \(h(ab)=h(a)h(b)\) follows: \[\begin{aligned} h(ab) &=\sum_{d\mid ab}\mu\left(\frac{ab}{d}\right)f(d)\\ &=\sum_{d_1\mid a}\sum_{d_2\mid b} \mu\left(\frac{a}{d_1}\frac{b}{d_2}\right)f(d_1d_2)\\ &=\sum_{d_1\mid a}\sum_{d_2\mid b} \mu\left(\frac{a}{d_1}\right) \mu\left(\frac{b}{d_2}\right)f(d_1)f(d_2)\\ &=\left(\sum_{d_1\mid a} \mu\left(\frac{a}{d_1}\right)f(d_1)\right) \left(\sum_{d_2\mid b} \mu\left(\frac{b}{d_2}\right)f(d_2)\right)\\ &=h(a)h(b). \end{aligned}\]
Exercise 15
Recall that \(\nu(n)\) denotes the number of positive divisors of \(n\), and \(\sigma(n)\) denotes their sum. Thus, in the notation of Exercise 13, \[\nu(n)=\sum_{d\mid n}1=\sigma_0(n), \qquad \sigma(n)=\sum_{d\mid n}d=\sigma_1(n).\] Both assertions follow directly from Möbius inversion: if \[F(n)=\sum_{d\mid n}f(d),\] then \[f(n)=\sum_{d\mid n}\mu\left(\frac{n}{d}\right)F(d).\]
(a) Taking \(f(n)=1\) for every positive integer \(n\), we have \(F(n)=\nu(n)\). Therefore \[\sum_{d\mid n}\mu\left(\frac{n}{d}\right)\nu(d)=1.\]
(b) Taking \(f(n)=n\), we have \(F(n)=\sigma(n)\). Hence \[\sum_{d\mid n}\mu\left(\frac{n}{d}\right)\sigma(d)=n.\] These identities hold for every positive integer \(n\), including \(n=1\).
Exercise 16
Write \(n=\prod_{i=1}^{r}p_i^{a_i}\). The divisor-counting formula gives \[\nu(n)=\prod_{i=1}^{r}(a_i+1).\] This product is odd if and only if every \(a_i+1\) is odd, or equivalently, every \(a_i\) is even. By unique factorization, this is exactly the condition that \(n\) be a square. The case \(n=1\) is included, since \(\nu(1)=1\) and \(1\) is a square.
Exercise 17
Separate the power of \(2\) in the prime factorization of \(n\): \[n=2^a\prod_{i=1}^{r}p_i^{a_i}, \qquad a\geq0,\] where the \(p_i\) are distinct odd primes. The divisor-sum formula gives \[\sigma(n) =(1+2+\cdots+2^a) \prod_{i=1}^{r}(1+p_i+\cdots+p_i^{a_i}).\] The first factor is always odd, since its constant term is \(1\) and all its other terms are even. For each odd prime \(p_i\), we have \(p_i\equiv1\pmod2\), so \[1+p_i+\cdots+p_i^{a_i} \equiv\underbrace{1+1+\cdots+1}_{a_i+1\text{ terms}} \equiv a_i+1\pmod2.\] Thus \(\sigma(n)\) is odd if and only if every \(a_i\) is even, which is equivalent to \(n=2^a s^2\) for some odd positive integer \(s\). If \(a=2b\), then \(n=(2^b s)^2\); if \(a=2b+1\), then \(n=2(2^b s)^2\).
Conversely, if \(n\) is a square or twice a square, every odd prime occurs in \(n\) to an even exponent. Each factor in the displayed formula for \(\sigma(n)\) is therefore odd, so \(\sigma(n)\) is odd. The empty-product convention includes \(n=1\) and all powers of \(2\).
Exercise 18
Let \(P\) be the set of primes dividing \(mn\), and write \[m=\prod_{p\in P}p^{a_p}, \qquad n=\prod_{p\in P}p^{b_p},\] where zero exponents are allowed. Then \[(m,n)=\prod_{p\in P}p^{\min(a_p,b_p)}, \qquad [m,n]=\prod_{p\in P}p^{\max(a_p,b_p)}.\] For each \(p\), the numbers \(\min(a_p,b_p)\) and \(\max(a_p,b_p)\) are simply \(a_p\) and \(b_p\) in some order. Consequently, \[\phi(p^{a_p})\phi(p^{b_p}) =\phi(p^{\min(a_p,b_p)})\phi(p^{\max(a_p,b_p)}).\] Multiplying over \(p\in P\) and using the multiplicativity of \(\phi\) gives \[\begin{aligned} \phi(m)\phi(n) &=\prod_{p\in P}\phi(p^{a_p})\phi(p^{b_p})\\ &=\left(\prod_{p\in P}\phi(p^{\min(a_p,b_p)})\right) \left(\prod_{p\in P}\phi(p^{\max(a_p,b_p)})\right)\\ &=\phi((m,n))\phi([m,n]). \end{aligned}\] Here \(\phi(p^0)=\phi(1)=1\). Each use of multiplicativity separates powers of distinct primes, which are pairwise coprime.
The function \(\phi\) is multiplicative, but not completely multiplicative: for example, \(\phi(4)=2\neq\phi(2)^2=1\). The proof above uses only ordinary multiplicativity.
Exercise 19
Set \(d=(m,n)\) and \(L=[m,n]\). Since \(mn=dL\), and \(mn\) and \(L\) have exactly the same prime divisors, Euler’s formula yields \[\begin{aligned} \phi(mn) &=mn\prod_{p\mid mn}\left(1-\frac1p\right)\\ &=dL\prod_{p\mid L}\left(1-\frac1p\right)\\ &=d\,\phi(L). \end{aligned}\] Multiplying by \(\phi(d)\) and applying Exercise 18, we obtain \[\phi(mn)\phi(d) =d\,\phi(L)\phi(d) =d\,\phi(m)\phi(n).\] Substituting \(d=(m,n)\) proves the desired identity. This argument does not require \(d\) and \(L\) to be coprime.
Exercise 20
The key observation is that each positive divisor \(d\) of \(n\) pairs with the positive divisor \(n/d\), and their product is \(n\). Set \[P=\prod_{d\mid n}d.\] The map \(d\mapsto n/d\) is a bijection on the positive divisors of \(n\) (indeed, applying it twice returns \(d\)). It therefore merely reorders the factors, so \[P=\prod_{d\mid n}\frac nd.\] Multiplying these two expressions for \(P\), we obtain \[\begin{aligned} P^2 &=\left(\prod_{d\mid n}d\right) \left(\prod_{d\mid n}\frac nd\right)\\ &=\prod_{d\mid n}\left(d\cdot\frac nd\right)\\ &=\prod_{d\mid n}n\\ &=n^{\nu(n)}. \end{aligned}\] The last equality holds because there are exactly \(\nu(n)\) positive divisors of \(n\), hence exactly \(\nu(n)\) factors equal to \(n\). Since \(P>0\), taking the positive square root gives \[\prod_{d\mid n}d=n^{\nu(n)/2}.\] This argument also covers square \(n\): the divisor \(\sqrt n\) is paired with itself, and the bijection remains valid.
Exercise 21
The function in this exercise, called the von Mangoldt function, is defined by \[\Lambda(n)= \begin{cases} \log p,& n=p^j \text{ for a prime }p\text{ and an integer }j\geq1,\\ 0,& \text{otherwise}. \end{cases}\] In particular, \(\Lambda(1)=0\).
Following the hint, first compute \(\sum_{d\mid n}\Lambda(d)\). For \(n>1\), write \[n=p_1^{a_1}\cdots p_r^{a_r}.\] Only divisors that are prime powers contribute to this sum. For each \(p_i\), the powers of \(p_i\) dividing \(n\) are exactly \(p_i,p_i^2,\ldots,p_i^{a_i}\). Each has value \(\Lambda(p_i^j)=\log p_i\), so together they contribute \(a_i\log p_i\). Consequently, \[\begin{aligned} \sum_{d\mid n}\Lambda(d) &=\sum_{i=1}^{r}\sum_{j=1}^{a_i}\Lambda(p_i^j)\\ &=\sum_{i=1}^{r}a_i\log p_i\\ &=\log\left(p_1^{a_1}\cdots p_r^{a_r}\right)\\ &=\log n. \end{aligned}\] This also holds for \(n=1\), since both sides are zero. Applying Möbius inversion to \(\log n=\sum_{d\mid n}\Lambda(d)\) now gives \[\Lambda(n)=\sum_{d\mid n}\mu\left(\frac nd\right)\log d,\] as required for every positive integer \(n\).
Exercise 22
Assume \(n>1\). The key is to pair each integer \(t\) coprime to \(n\) with \(n-t\), so that the two terms sum to \(n\). Set \[R=\{t\in\mathbb{Z}:1\leq t\leq n,\ (t,n)=1\}, \qquad S=\sum_{t\in R}t.\] Since \((n,n)=n>1\), every \(t\in R\) satisfies \(1\leq t<n\). Moreover, \[(n-t,n)=(t,n)=1.\] Thus \(n-t\) also belongs to \(R\). The map \(t\mapsto n-t\) is a bijection of \(R\) onto itself, because applying it twice returns \(t\). Consequently, \[S=\sum_{t\in R}(n-t).\] Adding this expression to the original sum gives \[\begin{aligned} 2S &=\sum_{t\in R}t+\sum_{t\in R}(n-t)\\ &=\sum_{t\in R}\bigl(t+(n-t)\bigr)\\ &=\sum_{t\in R}n\\ &=n\phi(n), \end{aligned}\] since \(R\) has exactly \(\phi(n)\) elements. Dividing by \(2\) proves \[\sum_{\substack{1\leq t\leq n\\(t,n)=1}}t =\frac{n\phi(n)}2.\] The argument includes \(n=2\), when the sole element \(t=1\) is paired with itself.
The hypothesis \(n>1\) is necessary. For \(n=1\), the sum equals \(1\), whereas \(n\phi(n)/2=1/2\), so the stated identity does not hold.