TotientFunction

The totient function phi(n), also called Euler's totient function, is defined as the number of positive integers <=n that are relatively prime to (i.e., do not contain any factor in common with) n, 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 phi(n) can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so phi(24)=8. The totient function is implemented in Mathematica as EulerPhi[n].

phi(n) is always even for n>=3. By convention, phi(0)=1, although Mathematica defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command. The first few values of phi(n) for n=1, 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). phi(n) is plotted above for small n.

For a prime p,

 phi(p)=p-1,
(1)

since all numbers less than p are relatively prime to p. If m=p^alpha is a power of a prime, then the numbers that have a common factor with m are the multiples of p: p, 2p, ..., (p^(alpha-1))p. There are p^(alpha-1) of these multiples, so the number of factors relatively prime to p^alpha is

phi(p^alpha)=p^alpha-p^(alpha-1)
(2)
=p^(alpha-1)(p-1)
(3)
=p^alpha(1-1/p).
(4)

Now take a general m divisible by p. Let phi_p(m) be the number of positive integers <=m not divisible by p. As before, p, 2p, ..., (m/p)p have common factors, so

phi_p(m)=m-m/p
(5)
=m(1-1/p).
(6)

Now let q be some other prime dividing m. The integers divisible by q are q, 2q, ..., (m/q)q. But these duplicate pq, 2pq, ..., (m/(pq))pq. So the number of terms that must be subtracted from phi_p to obtain phi_(pq) is

Deltaphi_q(m)=m/q-m/(pq)
(7)
=m/q(1-1/p),
(8)

and

phi_(pq)(m)=phi_p(m)-Deltaphi_q(m)
(9)
=m(1-1/p)-m/q(1-1/p)
(10)
=m(1-1/p)(1-1/q).
(11)

By induction, the general case is then

phi(n)=nproduct_(p|n)(1-1/p)
(12)
=n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r)),
(13)

where the product runs over all primes p dividing n. An interesting identity relating phi(n^k) to phi(n) is given by

 phi(n^k)=n^(k-1)phi(n)
(14)

(A. Olofsson).

Another identity relates the divisors d of n to n via

 sum_(d|n)phi(d)=n.
(15)

The totient function is connected to the Möbius function mu(n) through the sum

 sum_(d)dmu(n/d)=phi(n),
(16)

where the sum is over the divisors of n, which can be proven by induction on n and the fact that mu(n) and phi(n) are multiplicative (Berlekamp; van Lint and Nienhuys).

The totient function has the Dirichlet series generating function

 sum_(n=1)^infty(phi(n))/(n^s)=(zeta(s-1))/(zeta(s))
(17)

for s>2 (Hardy and Wright).

The totient function satisfies the inequality

 phi(n)>=sqrt(n)
(18)

for all n except n=2 and n=6 (Kendall and Osborn 1965; Mitrinović and Sándor 1995, p. 9). Therefore, the only values of n for which phi(n)=2 are n=3, 4, and 6. In addition, for composite n,

 phi(n)<=n-sqrt(n)
(19)

(Sierpiński and Schinzel 1988; Mitrinović and Sándor).

TotientFunctionInequality

phi(n) also satisfies

 lim inf_(n->infty)phi(n)(lnlnn)/n=e^(-gamma),
(20)

where gamma is the Euler-Mascheroni constant. The values of n for which phi(n)<e^(-gamma)n/(lnlnn) 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

nsigma(n)=2 (mod phi(n))
(21)
={0 (mod phi(n)) if phi(n)=2; 2 (mod phi(n)) otherwise
(22)

for all primes p>=5 and no composite with the exception of 4, 6, and 22, where sigma(n) is the divisor function. This fact was proved by Subbarao, despite the implication to the contrary, "is it true for infinitely many composite n?," stated in Guy, a query subsequently removed from Guy. No composite solution is currently known to

 n-1=0 (mod phi(n))
(23)

(Honsberger).

A corollary of the Zsigmondy theorem leads to the following congruence,

 phi(a^n+b^n)=0 (mod n)
(24)

(Zsigmondy, Moree, Ruiz).

The first few n for which

 phi(n)=phi(n+1)
(25)

are given by 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (Sloane's A001274), which have common values phi(n)=1, 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (Sloane's A003275).

The only n<10^(10) for which

 phi(n)=phi(n+1)=phi(n+2)
(26)

is n=5186, giving

 phi(5186)=phi(5187)=phi(5188)=2^53^4
(27)

(Guy).

Values of phi(n) shared among n that are close together include

phi(25930)=phi(25935)=phi(25940)=phi(25942)
(28)
=2^73^4
(29)
phi(404471)=phi(404473)=phi(404477)
(30)
=2^83^25^27
(31)

(Guy). McCranie found an arithmetic progression of six numbers with equal totient functions,

 phi(583200)=phi(583230)=phi(583260)=phi(583290) 
 =phi(583320)=phi(583350)=155520,
(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 m, there are primes p and q such that

 phi(p)+phi(q)=2m
(33)

(Guy). Erdős asked if this holds for p and q not necessarily prime, but this relaxed form remains unproven (Guy).

Guy discussed solutions to

 phi(sigma(n))=n,
(34)

where sigma(n) 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).