Originally Posted by

**chiph588@** 1.) This proof comes from Apostol's book on analytic number theory.

Let $\displaystyle N=\{1,2,3,\ldots,n\} $. For each divisor $\displaystyle d $ of $\displaystyle n $ define $\displaystyle S(d) = \{k \; | \; (k,n)=d, \; 1\leq k \leq n \} $ i.e $\displaystyle S(d) $ contains all elements of $\displaystyle N $ which have gcd $\displaystyle d $ with $\displaystyle n $. The sets $\displaystyle S(d) $ form a disjoint collection whose union is $\displaystyle N $. Thus if $\displaystyle f(d) $ denotes the number of integers in $\displaystyle S(d) $, we have $\displaystyle \sum_{d\mid n}f(d) = n $.

But $\displaystyle (k,n)=d \iff (k/d,n/d)=1 $ and $\displaystyle 1\leq k \leq n \iff 1\leq k/d \leq n/d $. So if we let $\displaystyle q=k/d $ there is a one-to-one correspondence between the elements in $\displaystyle S(d) $ and those integers $\displaystyle q $ satisfying $\displaystyle 1\leq q \leq n/d $ and $\displaystyle (q,n/d)=1 $. The number of such $\displaystyle q $ is $\displaystyle \phi(n/d) $. Thus $\displaystyle f(d) = \phi(n/d) $.

Therefore $\displaystyle n = \sum_{d\mid n} \phi(n/d) = \sum_{d\mid n} \phi(d) $.

3.) The only number known that satisfies this property is $\displaystyle n=5186 $.