Where is an integer and is a positive divisor of n and is the Euler Totient function, how do we prove that:
?
I have absolutely no idea how to approach this problem, any help to get me started is very much appreciated.
The 'direct proof' is a little 'efforts spending'. A confortable alternative is to read...
Möbius Inversion Formula -- from Wolfram MathWorld
...where the 'Moebius inversion pair formula' is illustrated...
(1)
Here is the 'Moebius function'. Of course the (1) can be apply 'from top to bottom' or 'from bottom to top'... using the last option You derive that...
(2)
Kind regards
chisigma has provided a "advanced" proof, here is a "elementary" proof:
consider the set {1,2,3,...,n}, there are n elements in it, for each element k , there is exactly one divisor d of n such that (n,k)=d. so the collection of all subsets where d divides n, forms a partition of {1,2,...,3}. for each d, the subset contains elements.
as d run over all divisors of n, n/d run over all divisors of n, the identity follows.
An alternative idea to the two already given, if you know some group theory:
Look at the cyclic group of order n , and then use that :
1) It has a unique (cyclic, also) group of order d, for any divisor d of n ;
2) A cyclic group of order k has exactly generators.
Put the above together and voila!
Tonio