From the definition of Euler’s phi function, we see that the cardinality \(|S(d,n)|\) of \(S(d, n)\) is given by \(\varphi(\frac{n}{d})\). \[n = \sum_{d|n} |S(d,n)| = \sum_{d|n} \varphi(\frac{d}{n}) \...From the definition of Euler’s phi function, we see that the cardinality \(|S(d,n)|\) of \(S(d, n)\) is given by \(\varphi(\frac{n}{d})\). \[n = \sum_{d|n} |S(d,n)| = \sum_{d|n} \varphi(\frac{d}{n}) \nonumber\] \[\varphi (n) = \sum_{d|n} \mu (d) \frac{n}{d} = n \sum_{d|n} \frac{\mu (d)}{d} \nonumber\] \[\varphi (\prod_{i=1}^{r} p_{i}^{l_{i}} = \prod_{i=1}^{r} \varphi (p_{i}^{l_{i}}) \nonumber\] \[\varphi (p^l) = p^{l} \sum_{j=0}^{l} \frac{\mu (p^j)}{p^j} = p^{l} (1-\frac{1}{p}) \nonumber\]
