Exercise 4.2.23* (Sum of the odd divisors of $n$)

Proof.

(a)

For every positive integer $n$, we define $$S(n)=\underset{d\mid n,2\nmid d}{\sum }d$$

the sum of odd divisors of $n$, and

$$T(n)=-\underset{d\mid n}{\sum }{(-1)}^{n∕d}d.$$

We show that $S$ and $T$ are multiplicative functions.

• Let $n$ be a positive integer. We write $n$ in the form $n=2^{\alpha }{n}^{\prime }$, where $\alpha \ge 0$ and $n^{\prime }$ is an odd integer.

  Every divisor of $n^{\prime }$ is odd, so is an odd divisor of $n$. Conversely, every odd divisor $d$ of $n$ satisfies $d\mid 2^{\alpha }{n}^{\prime },d\wedge 2^{\alpha }=1$, thus $d\mid n^{\prime }$. This shows that the set of odd divisors of $n$ is the set of divisors of $n^{\prime }$, therefore

  $$S(n)=\sigma (n^{\prime }),(n=2^{\alpha }{n}^{\prime },2\nmid n^{\prime }).$$

  If $n=2^{\alpha }{n}^{\prime }$ and $m=2^{\beta }{m}^{\prime }$ are such that $m\wedge n=1$ (so $\alpha =0$ or $\beta =0$), then $\mathit{nm}=2^{\alpha +\beta }{m}^{\prime }{n}^{\prime }$, where $m^{\prime }{n}^{\prime }$ is odd and $m^{\prime }\wedge n^{\prime }=1$, thus

  $$\begin{array}{llll}\hfill S(n)S(m)& =\sigma (n^{\prime })\sigma (m^{\prime })& \hfill & \\ \hfill & =\sigma (n^{\prime }{m}^{\prime })& \hfill & \\ \hfill & =S(\mathit{nm}).& \hfill & \end{array}$$

  So $S$ is a multiplicative function.

• By definition,

  $$T(n)=-\underset{d\mid n}{\sum }{(-1)}^{n∕d}d=-\underset{\delta \mid n}{\sum }{(-1)}^{\delta }\frac{n}{d}(\delta =n∕d).$$

  If $n\wedge m=1$,

  $$\begin{array}{lll}\hfill T(n)T(m)& =\underset{d_1\mid n}{\sum }{(-1)}^{d_1}\frac{n}{d_1}\underset{d_2\mid n}{\sum }{(-1)}^{d_2}\frac{m}{d_2}& \hfill \text{(1)}\\ \hfill & =\underset{d_1\mid n,d_2\mid m}{\sum }{(-1)}^{d_1+d_2}\frac{\mathit{nm}}{d_1{d}_2}.& \hfill \text{(2)}\end{array}$$

  The following array compares the values ${(-1)}^{d_1+d_2}$ and $-{(-1)}^{d_1{d}_2}$ in every case.

  $d_1\mathit{mod}2$	$d_2\mathit{mod}2$	$d_1+d_2\mathit{mod}2$	$d_1{d}_2\mathit{mod}2$	${(-1)}^{d_1+d_2}$	$-{(-1)}^{d_1{d}_2}$
  0	0	0	0	1	-1
  0	1	1	0	-1	-1
  1	0	1	0	-1	-1
  1	1	0	1	1	1

  This shows that ${(-1)}^{d_1+d_2}=-{(-1)}^{d_1{d}_2}$, except if $d_1,d_2$ are both even. But $d_1\mid n$ and $d_2\mid m$, where $m,n$ are relatively prime, thus $d_1,d_2$ are not both even, so ${(-1)}^{d_1+d_2}=-{(-1)}^{d_1{d}_2}$ for every such pair of divisors in (2). Therefore

  $$\begin{array}{llll}\hfill T(n)T(m)& =-\underset{d_1\mid n,d_2\mid m}{\sum }{(-1)}^{d_1{d}_2}\frac{\mathit{nm}}{d_1{d}_2}& \hfill & \\ \hfill & =-\underset{d\mid \mathit{nm}}{\sum }{(-1)}^d\frac{\mathit{nm}}{d}& \hfill & \\ \hfill & =T(\mathit{nm}).& \hfill & \end{array}$$

  (Since $n\wedge m=1$, every divisor $d$ of $\mathit{nm}$ is in an unique way the product $d=d_1{d}_2$, where $d_1\mid n,d_2\mid m$.)

  So $T$ is a multiplicative functions.

Now we compare $S(p^{\alpha })$ and $T(p^{\alpha })$, where $p$ is a prime number.

• If $p\ne 2$,

  $$S(p^{\alpha })=\sigma (p^{\alpha })=\frac{p^{\alpha +1}-1}{p-1},$$

  and

  $$\begin{array}{llll}\hfill T(n)& =-\underset{i=0}{\overset{\alpha }{\sum }}{(-1)}^{p^{\alpha -i}}{p}^i& \hfill & \\ \hfill & =\underset{i=0}{\overset{\alpha }{\sum }}{p}^i& \hfill & \\ \hfill & =\frac{p^{\alpha +1}-1}{p-1}& \hfill & \end{array}$$

• If $p=2$,

  $$S(n)=1,$$

  and

  $$\begin{array}{llll}\hfill T(n)& =-\underset{i=0}{\overset{\alpha }{\sum }}{(-1)}^{2^{\alpha -i}}{2}^i& \hfill & \\ \hfill & =2^{\alpha }-\underset{i=0}{\overset{\alpha -1}{\sum }}{2}^i& \hfill & \\ \hfill & =1,& \hfill & \end{array}$$

  because ${(-1)}^{2^{\alpha -i}}=-1$ if $\alpha =i$ and ${(-1)}^{2^{\alpha -i}}=1$ if $0\le i\le \alpha -1$.

In both cases, $S(p^{\alpha })=T(p^{\alpha })$. Since $S$ and $T$ are multiplicative functions $,S(n)=T(n)$ for every positive integer $n$, so

$$S(n)=\underset{d\mid n,2\nmid d}{\sum }d=-\underset{d\mid n}{\sum }{(-1)}^{n∕d}d.$$

(b)

We write $n=2^{\alpha }{n}^{\prime }$, where $n^{\prime }$ is an odd integer.

• If $n$ is odd, then $\alpha =0$, and $S(n)=\sigma (n^{\prime })=\sigma (n)$. Here $n∕2$ is not an integer, so $\sigma (n∕2)=0$, and

  $$S(n)=\sigma (n)-2\sigma (n∕2).$$

• If $n$ is even, then $\alpha \ge 1$, and since $\sigma$ is a multiplicative function,

  $$\begin{array}{llll}\hfill \sigma (n)-2\sigma (n∕2)& =\sigma (2^{\alpha }{n}^{\prime })-2\sigma (2^{\alpha -1}{n}^{\prime })& \hfill & \\ \hfill & =(2^{\alpha +1}-1)\sigma (n^{\prime })-2(2^{\alpha }-1)\sigma (n^{\prime })& \hfill & \\ \hfill & =\sigma (n^{\prime })& \hfill & \\ \hfill & =S(n).& \hfill & \end{array}$$

In both cases,

$$S(n)=\sigma (n)-2\sigma (n∕2).$$

(Alternatively, if $n$ is even,

$$\begin{array}{llllll}\hfill S(n)& =\underset{d\mid n,2\nmid d}{\sum }d& \hfill & & \hfill & \\ \hfill & =\underset{d\mid n}{\sum }d-\underset{d\mid n,2\mid d}{\sum }d& \hfill & & \hfill & \\ \hfill & =\underset{d\mid n}{\sum }d-\underset{\delta \mid \frac{n}{2}}{\sum }(2\delta )& \hfill (d=2\delta )& & \hfill & & \hfill \\ \hfill & =\sigma (n)-2\sigma (n∕2),& \hfill & & \hfill & \end{array}$$

and if $n$ is odd

$$S(n)=\underset{d\mid n,2\nmid d}{\sum }d=\underset{d\mid n}{\sum }d=\sigma (n).$$

In both cases,

$$S(n)=\sigma (n)-2\sigma (n∕2).)$$