Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a cute question that I found in ML. I thought a little bit about it and couldn't complete it to a solution.

Let $G$ be a non-cyclic finite group of order $n.$ Let $S(G)=\sum_{g \in G} o(g)$ where $o(g)$ is the order of $g$ in $G.$ Prove that $S(G)<S(\mathbb{Z}/n\mathbb{Z}).$

My thoughts:

For any $d|n,$ there is a unique cyclic subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d,$ and the number of generators of such a cyclic subgroup is $\varphi(d).$ Therefore, $S(\mathbb{Z}/n\mathbb{Z})=\sum_{d|n} \varphi(d)d.$

Let $s_d$ be the number of elements of $G$ of order $d.$ Then $S(G)=\sum_{d|n}s_dd.$ By Frobenius theorem, the number of elements $g \in G$ s.t. $g^d=1$ is a multiple of $d,$ thus $0 \leq s_d \leq dk_d$ for some non-negative integer $k_d.$

Case 1: If for some divisor $d$ we have $dk_d=n,$ then $S(G) \leq 1+(n-1)d<1+n(n-1)/2.$

Case 2: If $dk_d \neq n$ for all divisors $d,$ then $k_d \leq \frac{n}{d}-1$ and $dk_d \leq n-d.$ Hence, $S(G) \leq \sum_{d|n}nd-d^2.$

Now we have to show that $\sum_{d|n} \varphi(d)d$ is strictly greater than the maximum of both cases 1, 2, which I couldn't prove. (I tried induction on $n,$ but it was unsuccessful!)

  1. How should one prove the inequalities?

  2. Is there any closed/simplified form for $\sum_{d|n} \varphi(d)d?$


What is $\lim_{n \to \infty} \frac{S(G)}{S(\mathbb{Z}/n\mathbb{Z})}?$

Added: I must confess that I came up with the last question without any thinking when I was writing the whole question, which the limit, of course, is absurd if one doesn't specify a group!

share|cite|improve this question
Surely $\lim\limits_{n\to\infty}\frac{S(G)}{S({\bf Z}/n{\bf Z})}$ is going to depend on choices of $G$? – anon Apr 6 '13 at 2:25
Nice Question Ehsan $+^+$ – Babak S. Apr 6 '13 at 6:55
up vote 4 down vote accepted

This is quite a difficult problem! There are two published solutions of which I am aware.


The first is the answer to AMM 6636(ii) by F. Schmidt. (The problem proposer submitted this second part without solution!)

The citation is:

F. Schmidt, Richard Stong and John H. Lindsey. The American Mathematical Monthly , Vol. 98, No. 10 (Dec., 1991), pp. 970-972.



The second is in the paper whose citation is:

Amiri, H., Jafarian Amiri, S. M., & Isaacs, I. M. (2009). Sums of element orders in finite groups. Communications in Algebra, 37(9), 2978-2980.


FYI: I became aware of these solutions in trying to figure out this MO problem. (As evidenced by the comment I left there.)

share|cite|improve this answer
Oh! I thought it is an elementary problem. I wasn't aware of them at all. Thank you btw. – Ehsan M. Kermani Apr 6 '13 at 2:35
You're welcome! – Benjamin Dickman Apr 6 '13 at 2:40
@B.D Ah! I thought immediately of that MO problem too. – Alexander Gruber Apr 6 '13 at 4:34
@AlexanderGruber I'm waiting somewhat impatiently for that problem to be resolved. I am quite sure it will be true, but I don't have the tools at my disposal to make a serious attack. Perhaps you do! – Benjamin Dickman Apr 6 '13 at 4:39

Answers to the two easier parts of the problem:

$f(n) = \sum_{d\mid n} d\phi(d)$ is the sum of a multiplicative function over all divisors of $n$; this is itself a multiplicative function of $n$. Thus if the prime-power factorization of $n$ is $n=p_1^{r_1}\cdots p_k^{r_k}$, we know that $f(n) = f(p_1^{r_1})\cdots f(p_k^{r_k})$. Therefore it suffices to calculate $f(p^k)$ for any prime power $p^k$, and that is not difficult: the answer is $f(p^k) = 1 + (p^{2k}-1)p/(p+1)$.

$\lim_{n\to\infty} S(G)/S(\mathbb Z/n\mathbb Z)$ doesn't exist. When $G = \mathbb Z/2\mathbb Z \times \mathbb Z/2\mathbb Z \times \mathbb Z/p\mathbb Z$ (where $p$ always denotes a prime), the ratio is $7/11$, while when $G = \mathbb Z/p\mathbb Z \times \mathbb Z/p\mathbb Z$, the ratio is $(p^3-p+1)/(p^4-p^3+p^2-p+1)$ which tends to $0$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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