Exercise 4.2.25* ($\sum_{\underset{(a,n)=1}{a=1}}^n (a-1, n) = d(n) \phi(n)$)

Proof. We note that $\mathit{d\varphi }$ is the product of two multiplicative functions, so is a multiplicative function.

Put

We show that $F$ is also a multiplicative function. Suppose that $n\wedge m=1$, where $n,m$ are positive integers. Let $A_n$ denote the set

Then

so

Consider the map

where $c\in [[1,\mathit{nm}]]$ is the unique integer such that

the existence and unicity of such an integer $c$ being in accordance with the Chinese Remainder Theorem.

• $\phi$ is well defined: since $a\wedge n=1$ and $b\wedge m=1$, using $c=a+\mathit{kn}$ for some integer $k$, $c\wedge n=(a+\mathit{kn})\wedge n=a\wedge n=1$, and similarly $c\wedge m=1$, therefore $c\wedge \mathit{nm}=1$, so $c\in A_{\mathit{nm}}$.
• $\phi$ is injective (one-to-one): if $c=\phi (a,b)=\phi (a^{\prime },b^{\prime })$, then $a\equiv a^{\prime }(\mathit{mod}n)$. Since $1\le a\le n$ and $1\le a^{\prime }\le n$, we obtain $a=a^{\prime }$, and similarly $b=b^{\prime }$.

• $\phi$ is surjective (onto): if $c\in A_{\mathit{nm}}$, we define $a$ as the positive remainder of $c$ modulo $n$, and $b$ as the positive remainder of $c$ modulo $m$, so that

  $$c=\mathit{qn}+a,1\le a\le n,c=q^{\prime }m+b,1\le b\le m.$$

  Since $c\wedge \mathit{nm}=1$, then $a\wedge n=(c-\mathit{qn})\wedge n=c\wedge n=1$, and $b\wedge m=(c-q^{\prime }m)\wedge m=c\wedge m=1$, thus $a\in A_n$ and $b\in B_m$. From $c\equiv a(\mathit{mod}n)$ and $c\equiv b\mathit{mod}m$, we infer $c=\phi (a,b)$, where $(a,b)\in A_n\times A_m$.

In conclusion, $\phi$ is a bijection. Moreover, if $c=\phi (a,b)$,

because $a-1\equiv c-1(\mathit{mod}n),b-1\equiv c-1(modm)$.

Using equality (1), this shows that

(Formally, if we put $f(c)=(c-1)\wedge n$, the bijective change of indices $c=\phi (a,b)$ gives

so that the sums (2) and (3) contain the same terms in different orders.)

It remains to compare $F(p^{\alpha })$ and $d(p^{\alpha })\varphi (p^{\alpha })$, where $\alpha \ge 0$ and $p$ is a prime number.

First $d(p^{\alpha })\varphi (p^{\alpha })=(\alpha +1)(p^{\alpha }-p^{\alpha -1})$.

Next, if we group the terms such that $(a-1)\wedge p^{\alpha }=d$, where $d$ is a divisor of $p^{\alpha }$ (so $d=p^i,0\le i\le \alpha$),

where

• If $i=0$,

  $$\begin{array}{llll}\hfill B_0& =\{a\in [[1,p^{\alpha }]]:p\nmid a,p\nmid a-1\}& \hfill & \\ \hfill & =[[1,p^{\alpha }]]\setminus \left((\{p,2p,\dots ,p^{\alpha -1}\cdot p\}\cup \{1,p+1,2p+1,\dots ,(p^{\alpha +1}-1)\cdot p+1\}\right),& \hfill & \end{array}$$

  so

  $$b_0=p^{\alpha }-2p^{\alpha -1}.$$

• If $i=\alpha$, for every $a\in B_{\alpha }$, $p^{\alpha }\mid a-1$, where $1\le a\le p^{\alpha }$, so $a-1=0$. Therefore $B_{\alpha }=\{1\}$ (since $0\wedge p^{\alpha }=p^{\alpha }$), and

  $$b_{\alpha }=1.$$

• If $0<i<\alpha$, then every $a\in B_i$ satisfies $p^i\mid a-1$, so $a=k{p}^i+1$ for some integer $k$, where $i>0$, thus $p\nmid a$. Therefore

  $$\begin{array}{llll}\hfill B_i& =\{a\in [[1,p^{\alpha }]]:(a-1)\wedge p^{\alpha }=p^i\}& \hfill & \\ \hfill & =\{a\in [[1,p^{\alpha }]]:p^i\mid a-1,p^{i+1}\nmid a-1\}.& \hfill & \end{array}$$

  Taking $b=a-1$

  $$\begin{array}{llllll}\hfill |B_i|& =\mathrm{Card}\{b\in [[0,p^{\alpha }[[:p^i\mid b,p^{i+1}\nmid b\}& \hfill & & \hfill & \\ \hfill & =\mathrm{Card}\{b\in [[0,p^{\alpha }[[:p^i\mid b\}-\mathrm{Card}\{b\in [[1,p^{\alpha }[[:p^{i+1}\mid b\}& \hfill & & \hfill & \\ \hfill & =p^{\alpha -i}-p^{\alpha -i-1}& \hfill (\text{since }i<\alpha ).& & \hfill & & \hfill \end{array}$$

  So

  $$b_i=p^{\alpha -i}-p^{\alpha -i-1}(0<i<\alpha ).$$

Then

Since $F$ and $\mathit{d\varphi }$ are multiplicative functions, for all positive integer $n$, $F(n)=d(n)\varphi (n)$, so

□