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).
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)
|
![]() | ![]() | ![]() |
(3)
|
![]() | ![]() | ![]() |
(4)
|
Now take a general divisible by
. Let
be the
number of positive integers
not divisible
by
. As before,
,
, ...,
have common
factors, 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
. An interesting
identity relating
to
is given
by
![]() |
(14)
|
(A. Olofsson).
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 proven
by induction on
and the fact that
and
are multiplicative
(Berlekamp; van Lint and Nienhuys).
The totient function has the Dirichlet series generating function
![]() |
(17)
|
for (Hardy and Wright).
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).
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, ... (Sloane's 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,
despite the implication to the contrary, "is it true for infinitely many composite
?," stated in Guy,
a query subsequently removed from Guy. No composite solution is currently known to
![]() |
(23)
|
(Honsberger).
A corollary of the Zsigmondy theorem leads to the following congruence,
![]() |
(24)
|
(Zsigmondy, Moree, Ruiz).
The first few for which
![]() |
(25)
|
are given by 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (Sloane's A001274), which have common values , 2, 8,
48, 80, 96, 128, 240, 288, 480, ... (Sloane's A003275).
The only for which
![]() |
(26)
|
is , giving
![]() |
(27)
|
(Guy).
Values of shared among
that are close
together include
![]() | ![]() | ![]() |
(28)
|
![]() | ![]() | ![]() |
(29)
|
![]() | ![]() | ![]() |
(30)
|
![]() | ![]() | ![]() |
(31)
|
(Guy). McCranie found an arithmetic progression of six numbers with equal totient functions,
![]() |
(32)
|
as well as other progressions of six numbers starting at 1166400, 1749600, ... (Sloane's A050518).
If the Goldbach conjecture is true, then for every positive integer , there are primes
and
such that
![]() |
(33)
|
(Guy). Erdős asked if this holds for and
not necessarily
prime, but this relaxed form remains unproven (Guy).
Guy discussed solutions to
![]() |
(34)
|
where is the divisor function. F. Helenius has found 365 such solutions,
the first of which are 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800, ...
(Sloane's A001229).