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:

enter image description here

  • $\begingroup$ Since $\sigma_0(N)$ is multiplicative, have you tried establishing the result for $N=p$ (prime)? $\endgroup$ – Alex R. Jun 20 '16 at 19:06
  • 1
    $\begingroup$ @AlexR. but how to prove the other side is multiplicative? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.