LinkBack URL
About LinkBacksWhereis 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...
= \sum_{d|n} f(d) )
(1)
Hereis 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 subsetswhere d divides n, forms a partition of {1,2,...,3}. for each d, the subset
elements.
as d run over all divisors of n, n/d run over all divisors of n, the identity follows.
Originally Posted by demode
Where
I have absolutely no idea how to approach this problem, any help to get me started is very much appreciated.
An alternative idea to the two already given, if you know some group theory:
Look at the cyclic groupof 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 exactlygenerators.
Put the above together and voila!
Tonio
gcd(k,n)=d impliesThanks Tonio and Shanks. I know group theory so Tonio's suggestion was also pretty straightforward. Also as a related question, how should I go about calculating the cardinality of the set?
(1) k and n are both divisible by d;
(2) k/d and n/d are relatively prime.
so combine (1) and (2), we have
the cardinality of the set, that is
  |
