Peter wrote: Show that for all $n \in \mathbb{N}$, \[n = \sum^{}_{d \vert n}\phi(d).\] The problem is obvious in case when $n=1$. Let's suppose that we have proved the desired identity for all $s<n$. We have that $n=p^{t}m$ for a positive integer $m$ and a prime $p$ so that $gcd(m;p)=1$. We know that $\phi(mn)=\phi(m)\phi(n)$ when $gcd(m;n)=1$. => \[m=\sum^{}_{d|m}\phi(m)\] => \[n = \sum^{}_{d \vert n}\phi(d)=\sum^{}_{d|m}\phi(m)+\sum^{t}_{i=1}\sum^{}_{d|m}{\phi(dp^{i})}=\sum^{}_{d|m}\phi(m)+\sum^{}_{d|m}\phi(m)(\sum^{t}_{i=1}\phi(p^{t}))=\sum^{}_{d|m}\phi(m)(1+(p-1)(\sum^{t-1}_{i=1}p^{i}))=\sum^{}_{d|m}\phi(m)(p^{t})=p^{t}m\] We are done! :razz:

The following proof may be folklore, however I thought it is nice to be mentioned here just in case there are users who don't have knowledge of this idea. Let's consider the set $ S = \left\{ \frac{k}{n} : k \in \overline{1, n} \right\}$. Simplifying all the fractions we conclude that $ S$ coincides with the union of the disjoint sets $ S_d = \left\{ \frac{k}{d} : k \in \overline{1, d}, (k, d) = 1 \right\}$, defined for all $ d | n$. Expressing the number of elements of $ S$ in two ways, by its definition and as the sum of the number of elements of all the $ S_d$'s yields exactly the desired equality, since $ |S_d| = \varphi(d)$.

Another classic proof is by considering the degrees of the terms in Dedekind's formula: \[ x^{n} - 1 = \prod_{d| n}{\phi_{d}(x)}, \] where $ \phi_{k}(x) = \prod_{\zeta \in P_{k}}(x - \zeta)$ and $ P_{k}$ is the set of the primitive roots of $ z^{k} = 1$.

pohoatza wrote: Another classic proof is done by considering the degrees of the terms in Dedekind's formula: $ x^n - 1 = \prod_{d|n} \Phi_{d}(x)$, where $ \Phi_{k}(x) = \prod_{\zeta \in P_k}(x - \zeta)$ is the $ k$-th cyclotomic polynomial (with $ P_k$ representing the set of the $ k$-th primitive roots of unity, $ |P_k| = \varphi(k)$). That's true, however the idea for proving your formula is actually the same - we can write $ x^n - 1 = \prod_{k=1}^n (x - e^{2\pi ik/n}) = \prod_{d|n} \ \prod_{k \in \overline{1, d}, (k, d) = 1} (x - e^{2\pi ik/d}) = \prod_{d|n} \Phi_d (x)$, because each fraction $ \frac{2\pi ik}{n}$ is simplified uniquely as $ \frac{2\pi ik'}{d}$, where $ k', d$ are coprime and $ d$ is a divisor of $ n$.

The ideas in Tiks' proof can be generalized using the concept of Dirichlet convolution. In particular, we are proving that $ n = \varphi(n) * 1$.

It has to be noted that there is a quick proof of this identity that relies solely on results related to properties of the finite cyclic groups. I suppose that proof has already been posted in the forum, but I can't find an explicit reference now. Can any of you guys throw me a bone here?

I wonder why nobody mentions the following proof, based on Mobius' inversion formula. For $ f$ a multiplicative arithmetic function, one has $ \sum_{d \mid n} \mu(d)f(d) = \prod_{\textrm{prime } p \mid n} (1-f(p))$. For $ f(x) = \frac {1} {x}$ therefore $ \sum_{d \mid n} \frac {\mu(d)} {d} = \prod_{\textrm{prime } p \mid n} (1-\frac {1} {p}) = \frac {\phi(n)} {n}$. So $ \sum_{d \mid n} \mu(d) \frac {n} {d} = \phi(n)$, and now the inversion formula yields $ n = \sum_{d \mid n} \phi(d)$.

Let $G=\mathbb{Z}/ n\mathbb{Z}$ be the cyclic group of order $n$. Since all of its subgroups are of the form $k \mathbb{Z} /n \mathbb{Z}$ with $k |n$ we know that $\forall$ $d|n$ there is a unique subgroup $H \leq G$ with $|H|=d$; If $A_d=\{x \in G : \text{ord}(x)=d \}$, then from the above observation and the fact that $ord(x^s)=\frac{ord(x)}{(ord(x),s)}$, we deduce that $|A_d|=\varphi(d)$.Since $G$ is the disjoint union of all the sets $A_d$, the conclusion follows.

mavropnevma wrote: For $ f$ a multiplicative arithmetic function, one has $ \sum_{d \mid n} \mu(d)f(d) = \prod_{\textrm{prime } p \mid n} (1-f(p))$. Nice proof! For clarity, I would like to point out that the above holds only for completely multiplicative functions, not all multiplicative functions.

Tiks wrote: Peter wrote: Show that for all $n \in \mathbb{N}$, \[n = \sum^{}_{d \vert n}\phi(d).\] The problem is obvious in case when $n=1$. Let's suppose that we have proved the desired identity for all $s<n$. We have that $n=p^{t}m$ for a positive integer $m$ and a prime $p$ so that $gcd(m;p)=1$. We know that $\phi(mn)=\phi(m)\phi(n)$ when $gcd(m;n)=1$. => \[m=\sum^{}_{d|m}\phi(m)\]=> \[n = \sum^{}_{d \vert n}\phi(d)=\sum^{}_{d|m}\phi(m)+\sum^{t}_{i=1}\sum^{}_{d|m}{\phi(dp^{i})}=\sum^{}_{d|m}\phi(m)+\sum^{}_{d|m}\phi(m)(\sum^{t}_{i=1}\phi(p^{t}))=\sum^{}_{d|m}\phi(m)(1+(p-1)(\sum^{t-1}_{i=1}p^{i}))=\sum^{}_{d|m}\phi(m)(p^{t})=p^{t}m\] We are done! :razz: Very nice soloution

$\phi (n)=\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)$, where $n=\prod_{i=1}^k p_i^{\alpha_i}$ and $\phi (0)=0, \phi(1)=1$ $\implies$ if $\gcd(m,n)=1$ then $\phi (mn)=\phi (m)\phi (n)$ $\sum_{d|n} \phi (d)= \sum_{r_k=0}^{\alpha_k}\cdots \sum_{r_2=0}^{\alpha_2}\sum_{r_1=0}^{\alpha_1} \phi (p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k})$ $=\sum_{r_k=0}^{\alpha_k}\cdots \sum_{r_2=0}^{\alpha_2}\sum_{r_1=0}^{\alpha_1} \phi (p_1^{r_1})\phi (p_2^{r_2})\cdots \phi (p_k^{r_k})$ $=\sum_{r_k=0}^{\alpha_k}\phi (p_k^{r_k})\cdots \sum_{r_2=0}^{\alpha_2}\phi (p_2^{r_2})\sum_{r_1=0}^{\alpha_1}\phi (p_1^{r_1})$ $=\left(\sum_{r_k=0}^{\alpha_k}\phi (p_k^{r_k})\right)\cdots \left(\sum_{r_2=0}^{\alpha_2}\phi (p_2^{r_2})\right)\left(\sum_{r_1=0}^{\alpha_1}\phi (p_1^{r_1})\right)$ Now $\phi (p_i^{r_i})=p_i^{r_i-1}(p_i-1)=p_i^{r_i}-p_i^{r_i-1}$ for $r_i>0$ $\sum_{r_k=0}^{\alpha_k}\phi (p_k^{r_k})=\phi(1)+\sum_{r_k=1}^{\alpha_k}\phi (p_k^{r_k})=1+\sum_{r_k=1}^{\alpha_k}p_i^{r_i}-p_i^{r_i-1}=p_i^{\alpha_i}$ Hence $\sum_{d|n} \phi (d)=\left(\sum_{r_k=0}^{\alpha_k}\phi (p_k^{r_k})\right)\cdots \left(\sum_{r_2=0}^{\alpha_2}\phi (p_2^{r_2})\right)\left(\sum_{r_1=0}^{\alpha_1}\phi (p_1^{r_1})\right)=\prod_{i=1}^k p_i^{\alpha_i}=n$