Exercise :

Using the fact that the number of the generators of $\mathbb Z_d$ is $\phi(d)$, show that : $$n = \sum_{d|n} \phi(d)$$ where $\phi$ is Euler's function which is defined for every positive integer $n$ from the formula $\phi(n)=s$, where $s$ is the number of positive integers less or equal of $n$ which are prime to $n$.

QUESTION : I have proved the given relation the following way, whilst studying but I am not sure whether it could be smaller or alternated, using the fact given in the exercise about $\mathbb Z_d$. I would appreciate any clarification or hint given.

Let $S_d = \left\{{m \in \mathbb Z: 1 \le m \le n, \gcd \left\{{m, n}\right\} = d}\right\}$. That is, $S_d$ is all the numbers less than or equal to $n$ whose $\text{gcd}$ with $n$ is $d$.

Now from Divide by $\text{gcd}$ for Coprime Integers we have:

$$\gcd \left\{{m, n}\right\} = d \iff \dfrac m d, \dfrac n d \in \mathbb Z: \dfrac m d \perp \dfrac n d$$

So the number of integers in $S_d$ equals the number of positive integers no bigger than $n/d$ which are prime to $n/d$.

By definition of the Euler function stated in the exercise, this is :

$$|S_d| = \phi\bigg(\frac{n}{d}\bigg)$$

From the definition of the $S_d$, it follows that for all $1≤m≤n$ :

$$\exists d | n: m \in S_d$$

which leads to :

$$\displaystyle \left\{{1, \ldots, n}\right\} = \bigcup_{d |n} S_d$$

From the way I defined $S_d$ though, it also follows that they are pairwise disjoint.

Now from Corollary to Cardinality of Set Union, it follows that :

$$n=\sum_{d|n} |S_d| = \sum_{d|n} \phi \left({\dfrac n d}\right)$$

But using the fact that the sum over divisors equals the sum over quotients, we derive the formula wanted :

$$\sum_{d | n} \phi \left({\dfrac n d}\right) = \sum_{d |n} \phi \left({d}\right)$$


The idea is you want to count the elements in $\mathbb{Z}_{n}$ in two ways. First, we note that $|\mathbb{Z}_{n}| = n$. We now count in a second way. Recall that for every $1\leq d|n$, there exists a unique subgroup of order $d$ in $\mathbb{Z}_{n}$, which is precisely $\mathbb{Z}_{d}$. Furthermore, these are the only subgroups of $\mathbb{Z}_{n}$. Now count the generators of $\mathbb{Z}_{d}$; there are $\phi(d)$ such generators. By Lagrange's Theorem, we have that $\langle a \rangle$ is a subgroup of $\mathbb{Z}_{n}$ for every $a \in \mathbb{Z}_{n}$. So in fact:

$$\sum_{1 \leq d|n} \phi(d) = n$$

  • $\begingroup$ There was a separate exercise linked to this one posted (hence the fact we were being asked to use) and it seems like what you've stated is way more like what the exercise wanted us to do in our way to prove the formula. It was also way faster and compact in your way taking advantage of the fact given that me elaborating a complete proof, so thanks a lot ! $\endgroup$ – Rebellos Dec 30 '17 at 19:52
  • 1
    $\begingroup$ I'm glad I could help! :-) $\endgroup$ – ml0105 Dec 30 '17 at 19:53

Sorry I'm just going to suggest a different method of proof.

Every element of $Z_n$ generates exactly one cyclic subgroup of some order $d\mid n$ for some $d$. Additionally $Z_n$ has a unique subgroup of order $d$ for each $d\mid n$. Then let $D_n$ be the set of divisors of $n$. Now we can say that if $\alpha(a,d) : Z_n \times D_n$ is the indicator function that is 1 when $a$ generates a subgroup of order $d$ and 0 otherwise, then $$ n=\sum_{a\in Z_n}1 = \sum_{a\in Z_n}\sum_{d\in D_n}\alpha(a,d) = \sum_{d\in D_n}\sum_{a\in Z_n} \alpha(a,d) = \sum_{d\mid n} \phi(d).$$

  • $\begingroup$ Cool short proof, got a bit complicated with the indicator function stuff though, not very used to it ! $\endgroup$ – Rebellos Dec 30 '17 at 19:54
  • $\begingroup$ @Rebellos sure, I just personally find indicator functions make arguments that involve counting something in two different ways more clear to me. $\endgroup$ – jgon Dec 30 '17 at 19:55

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.