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.

Printable View

- March 9th 2011, 12:17 AMdemodeEuler's totient function Proof
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. - March 9th 2011, 01:11 AMchisigma
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

- March 9th 2011, 02:19 AMShanks
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. - March 9th 2011, 02:34 AMtonio

An alternative idea to the two already given,you know some group theory:__if__

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 - March 9th 2011, 07:44 PMdemode
Thanks 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 ?

- March 10th 2011, 05:30 AMShanks