totient function

[sfpublic]

how is summation of all phi(d) = n where d|n?

thanks

[Xittenn]

The divisors of 24 are

 

1, 2, 3, 4, 6, 8, 12, 24

 

the relative primes for each divisor are

 

1

 

1

 

1, 2

 

1, 3

 

1, 5

 

1, 3, 5, 7

 

1, 5, 7, 11

 

1, 5, 7, 11, 13, 17, 19, 23

 

the totient of each divisor is the sum of the relative primes and the sum of the totients is n which in this case is

 

1 + 1 + 2 + 2 + 2 + 4 + 4 + 8 = 24

Edited March 13, 2011 by Xittenn

[sfpublic]

can you please take a general case and solve it mathmematically..im not able to get the statement

the totient of each divisor is the sum of the relative primes and the sum of the totients is n which in this case is

how did you arrive at the statement that the sum of totients is n?

[Xittenn]

can you please take a general case and solve it mathmematically..im not able to get the statement

 

how did you arrive at the statement that the sum of totients is n?

 

 

I believe I did just give an example above.

 

You are inquiring about the identity [math] \sum_{d \mid n} \phi(d) = n [/math]. This identity states that given a positive integer n one can find the divisors(d) of n such that [math] d \mid n [/math]. You can then add together the totients of each of the divisors(d) and the sum of this will be the n for which the divisors were originally found. This identity is a consequence of the Möbius inversion formula.

 

How I came to the the statement "the sum of totients is n" is by the definition of the mathematical symbols you have presented where [math] \phi(d) [/math] is the totient function acting on each d that [math] \sum_{d \mid n} [/math] is the sum of and where n is equal to. I'm having difficulty seeing what it is you are seeking, I'm sorry.

Edited March 13, 2011 by Xittenn