# Show that $\sigma_0(N) = \frac{1}{N}\sum_{d|N} \sum_{l=1}^d \mathrm{gcd}(d,l)$

Here is a result I found in a textbook:

$$\sigma_0(N) = \boxed{\sum_{d|N} 1 = \frac{1}{N}\sum_{d|N} \sum_{l=1}^d \mathrm{gcd}(d,l) }$$

How does this follow from the basic results of number theory? I tried Bezout's theorem:

$$\mathrm{gcd}( x,y) = \min \big\{ ax + by > 0 : a,b \in \mathbb{Z} \big\}$$

but now we are adding all the GCD's.

I am really trying to think of this as an elementary school student using the divisor tree:

• Since $\sigma_0(N)$ is multiplicative, have you tried establishing the result for $N=p$ (prime)? – Alex R. Jun 20 '16 at 19:06
• @AlexR. but how to prove the other side is multiplicative? – cactus314 Jun 20 '16 at 19:11

Hint: Show that $$\sum_{l=1}^d\,\gcd(l,d)=d\,\sum_{t\mid d}\,\frac{\phi(t)}{t}$$ for every positive integer $d$, and that $$\left(\phi*\sigma_1\right)(n)=n\,\sigma_0(n)$$ for every positive integer $n$, where $\phi$ is Euler's totient function, $\sigma_1$ is the divisor-sum function, and $*$ is the Dirichlet convolution.
For the first hint, we count the number of $l\in\{1,2,\ldots,d\}$ with $\gcd(l,d)=\tau$ for a particular $\tau\mid d$. It is easily seen that there are $\phi\left(\frac{d}{\tau}\right)$ such integers $l$, whence $$\sum_{l=1}^d\,\gcd(l,d)=\sum_{\tau \mid d}\,\tau\,\phi\left(\frac{d}{\tau}\right)=d\,\sum_{t\mid d}\,\frac{\phi(t)}{t}\,.$$ Then, we get \begin{align}\sum_{d\mid n}\,\sum_{l=1}^d\,\gcd(l,d)&=\sum_{d\mid n}\,d\,\sum_{t\mid d}\,\frac{\phi(t)}{t}=\sum_{t\mid n}\,\phi(t)\,\sum_{\delta\mid\frac{n}{t}}\,\delta\\&=\sum_{t\mid n}\,\phi(t)\,\sigma_1\left(\frac{n}{t}\right)=\left(\phi*\sigma_1\right)(n)\,.\end{align} To show the second hint, we simply verify the equality when $n$ is a prime power, as the Dirichlet convolution preserves multiplicativity. You can also show that $\text{id}=\phi*1$ and $\sigma_1=1*\text{id}$, where $\text{id}$ is the identity function $n\mapsto n$ and $1$ is the constant function $n\mapsto1$. Ergo, $$\phi*\sigma_1=\phi*(1*\text{id})=(\phi*1)*\text{id}=\text{id}*\text{id}=\text{id}\cdot\sigma_0\,.$$
Fix $D$, some positive divisor of $N$. We will show that in the sum $$\sum_{d\mid n} \sum_{l=1}^d \gcd(l,d)$$ there are exactly $N/D$ terms with $\gcd(l,d)=D$. This will imply the problem statement because $$\sum_{d\mid n} \sum_{l=1}^d \gcd(l,d)=\sum_{D\mid N}D\cdot(N/D)=N\sigma_0(N).$$
Indeed, any pair $(l,d)$ such that $\gcd(l,d)=D$ must be of the form $l=mD,d=kD$ for some integers $k,m$ with $1\le k\le N/D$ and $1\le m\le k$. Hence the number of such pairs $(l,d)$ are the number of $m,k$'s in the aforementioned range with $\gcd(mD,kD)=D$, i.e. $\gcd(m,k)=1$. There are thus $$\sum_{k\mid N/D}\varphi(k)=N/D$$ such pairs.