This question already has an answer here:

Let $n$ be a positive integer. Then $$ \sum_{d|n} \phi(d) = n$$

Where $\phi$ is the euler totient function.

The first step in a proof of this is to define a set $S_d$, for each divisor $d$ of $n$; $S_d={\{1 \leq a \leq n : gcd(a,n) = d}\}$.

It then states that it is "obvious" that $\sum_{d|n} |S_d| = n$, however this isn't remotely obvious to me?

Could anyone explain it to me please?

This has been flagged for a duplicate but the duplicate question doesn’t specifically tackle the step in the proof that is troubling me.


marked as duplicate by Parcly Taxel, Jose Arnaldo Bebita-Dris, The Phenotype, Namaste, Ethan Bolker Mar 13 '18 at 17:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Each $a \in \{1, \ldots, n\}$ belongs to $S_{\gcd(a,n)}$ and to no other $S_d$. $\endgroup$ – dxiv Mar 13 '18 at 2:54

Take an example: Let $n = 10$
The divisors of $n$ are $1,2,5,10$
$S_1 = {1,3,7,9}$
$S_2 = {2,4,6,8}$
$S_5 = {5}$
$S_{10} = {10}$

We have two prove two things: 1. All numbers from $\{1, \ldots, n\}$ are included and 2. there are no repeats.

  1. All $a \in \{1, \ldots, n\}$ have a $gcd(a,n)$ equal to either $1,2,5,$ or $10$. (the divisors of $n$).

  2. If a number $a$ is in two of the sets, this would imply it has two different $gcd(a,n)$. Violates the definition of $gcd(a,n)$.


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