Describe EulerInformation here
The totient function , also called Euler’s totient function, is defined as the number of positive integers that are relatively prime to (i.e., do not contain any factor in common with) , where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function can be simply defined as the number of totatives of . For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so . The totient function is implemented in Mathematica as EulerPhi[n].
is always even for . By convention, , although Mathematica defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command. The first few values of for , 2, … are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, … (Sloane’s A000010). The totient function is given by the Möbius transform of 1, 2, 3, 4, … (Sloane and Plouffe 1995, p. 22). is plotted above for small .
For a prime ,
(1)
since all numbers less than are relatively prime to . If is a power of a prime, then the numbers that have a common factor with are the multiples of : , , …, . There are of these multiples, so the number of factors relatively prime to is
(2)
Now take a general divisible by . Let be the number of positive integers not divisible by . As before, , , …, have common factors, so
(3)
Now let be some other prime dividing . The integers divisible by are , , …, . But these duplicate , , …, . So the number of terms that must be subtracted from to obtain is
(4)
and
(5) (6) (7)
By induction, the general case is then
(8)
An interesting identity relating to is given by
(9)
(A. Olofsson, pers. comm., Dec. 30, 2004).
Another identity relates the divisors of to via
(10)