Is there any usage of this sum formula?

134 Views Asked by At

Let $\phi$ be the Euler phi function, then $$n=\sum_{d|n}\phi(d)$$

It is one of the most famous formulas in number theory. It can be generalized by using groups.

Let $G$ be a group of order $n$ and $t_i$ be number of cyclic subgroups of order $d_i$ then,

$$|G|=n=\sum_{d_i|n}t_i\phi(d_i)$$

This formula can be easily proved by setting equivalence relation if $<x>=<y> \ then \ x\sim y $ The above formula is a general form since if you take $G=\mathbb Z_n$ i.e a cyclic group, it has a unique subgroup of every possible order which means $t_i=1$ as a result we will get the first result.

I can see that if $s_i$ is number of the elements of order $d_i$ in $G$ then $s_i=t_i\phi(d_i)$. But I did not know whether it has some application or usage in group theory or number theory, even if the result seems nice.

Any further result related the this formula would be appreciated.

2

There are 2 best solutions below

0
On

You can use this result to compute : $$ \det((\gcd(i, j))_{1 \leqslant i, j \leqslant n}) $$

Writing $\gamma_{i,j}$ the $\gcd$ of $i$ and $j$.

We have $$\gamma_{i,j}=i\wedge j=\sum_{k|i\wedge j}\phi(k)=\sum_{k=1}^n[\Phi]_{i,k}[A^t]_{k,j}=[\Phi A^t]_{i,j}$$ where

$$[\Phi]_{p,q} = \left\{ \begin{array}{ll} \phi(q) & \mbox{if}\quad q\vert p \\ 0 & \mbox{otherwise} \end{array} \right. $$

Then $\det((\gcd(i, j))_{1 \leqslant i, j \leqslant n})=\prod_{k=1}^n \phi(k)$

0
On

There is a series of papers by Gian-Carlo Rota: On the foundations of combinatorial theory. The first paper in this series is I. Theory of Moebius functions, Zeitschrift für Wahrscheinlichkeitstheorie, 2 (1964), 349–368.

Rota is looking at a generalization of the number theory formula in the framework of partially ordered sets.