The totient function 
,
also called Euler's totient function, is defined for a positive
integer 
as the number of positive integers 
that are relatively prime
to (i.e., share no common divisor other than 1 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 the Wolfram Language as EulerPhi[n].
The number 
is called the cototient of 
and gives the number of positive
integers 
that have at least one prime factor in common with
.
is always even
for 
.
In the extension used here, 
, although the Wolfram
Language 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, ... (OEIS
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
with positive integer exponent 
, then the numbers that have a common
divisor with 
are the multiples of 
: 
, 
, ..., 
. There are 
of these multiples, so the number of totatives
of 
is
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
Now take a positive integer 
divisible by 
. Let 
be the number of positive
integers 
not divisible by 
. As before, the multiples 
, 
, ..., 
are excluded, so
 |  |  |
(5)
|
 |  |  |
(6)
|
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
 |  |  |
(7)
|
 |  |  |
(8)
|
and
 |  |  |
(9)
|
 |  |  |
(10)
|
 |  |  |
(11)
|
By induction, the general case is then
 |  |  |
(12)
|
 |  |  |
(13)
|
where the product runs over all primes 
dividing 
. For a positive integer 
, an identity relating 
to 
is given by
 |
(14)
|
(A. Olofsson, pers. comm., Dec. 30, 2004).
Another identity relates the divisors 
of 
to 
via
 |
(15)
|
The totient function is connected to the Möbius function 
through the sum
 |
(16)
|
where the sum is over the divisors of 
,
which can be proved by induction on 
and the fact that 
and 
are multiplicative
(Berlekamp 1968, pp. 91-93; van Lint and Nienhuys 1991, p. 123).
The totient function has the Dirichlet generating function
 |
(17)
|
for 
,
where 
is the Riemann zeta function (Hardy and Wright
1979, p. 250).
The totient function satisfies the inequality
 |
(18)
|
for all 
except 
and 
(Kendall and Osborn 1965; Mitrinović and Sándor 1995, p. 9). Therefore,
the only values of 
for which 
are 
,
4, and 6. In addition, for composite 
,
 |
(19)
|
(Sierpiński and Schinzel 1988; Mitrinović and Sándor 1995, p. 9).
also satisfies
 |
(20)
|
where 
is the Euler-Mascheroni constant. The
values of 
for which 
are given by 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (OEIS A100966).
The divisor function satisfies the congruence
 |  |  |
(21)
|
 |  |  |
(22)
|
for all primes 
and no composite
with the exception of 4, 6, and 22, where 
is the divisor function.
This fact was proved by Subbarao (1974), despite the implication to the contrary,
"is it true for infinitely many composite 
?," stated in Guy (1994, p. 92), a query subsequently
removed from Guy (2004, p. 142). No composite
solution is currently known to
 |
(23)
|
(Honsberger 1976, p. 35).
For distinct positive integers 
and 
and a positive integer 
, a corollary of the Zsigmondy
theorem gives the congruence
 |
(24)
|
(Zsigmondy 1892, Moree 2004, Ruiz 2004ab).
The first few 
for which
 |
(25)
|
are given by 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (OEIS A001274), which have common values 
, 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (OEIS A003275).
The only 
for which
 |
(26)
|
is 
,
giving
 |
(27)
|
(Guy 2004, p. 139).
Values of 
shared among 
that are close together include
 |  |  |
(28)
|
 |  |  |
(29)
|
 |  |  |
(30)
|
 |  |  |
(31)
|
(Guy 2004, p. 139). McCranie found an arithmetic progression of six numbers with equal totient functions,
 |
(32)
|
as well as other arithmetic progressions of six numbers starting at 1166400, 1749600, ... (OEIS A050518).
If the Goldbach conjecture is true, then for every positive integer 
, there are primes 
and 
such that
 |
(33)
|
(Guy 2004, p. 160). Erdős asked if this holds for 
and 
not necessarily prime, but
this relaxed form remains unproven (Guy 2004, p. 160).
Guy (2004, p. 150) discussed solutions to
 |
(34)
|
where 
is the divisor function. The unit solution 
is trivial. F. Helenius has found
365 such solutions. The first nontrivial solutions with 
are 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800,
... (OEIS A001229).
for Which 
Divides 
." Fib. Quart. 27, 285-286, 1989.Conway,
J. H. and Guy, R. K. "Euler's Totient Numbers." 
Function. Fermat's Theorem Again." §2.4.3 in Supplement
to Ch. 1 in 
Properly Divide 
," "Solutions of 
," "Carmichael's Conjecture,"
"Gaps Between Totatives," "Iterations of 
and 
," "Behavior of 
and 
." §B36-B42 in 
-Function." §8 in 
Function." §2.27 in