Totient Function

The totient function $\phi(n)$, also called Euler's totient function, is defined as the number of Positive Integers $\leq n$ which 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$.

By convention, $\phi(0)=1$. 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). $\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 which 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}=p^{\alpha-1}(p-1)=p^\alpha\left({1-{1\over p}}\right).$$ (2)

Now take a general $m$ divisible by $p$. Let $\phi_p(m)$ be the number of Positive Integers $\leq m$ not Divisible by $p$. As before, $p$, $2p$, ..., $(m/p)p$ have common factors, so

$$\phi_p(m)=m-{m\over p}=m\left({1-{1\over p}}\right).$$ (3)

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 which must be subtracted from $\phi_p$ to obtain $\phi_{pq}$ is

$$\Delta\phi_q(m)={m\over q}-{m\over pq}={m\over q}\left({1-{1\over p}}\right),$$ (4)

and

$$\phi_{pq}(m) \equiv \phi_p(m)-\Delta\phi_q(m)$$

$$= m\left({1-{1\over p}}\right)-{m\over q}\left({1-{1\over p}}\right)$$

$$= m\left({1-{1\over p}}\right)\left({1-{1\over q}}\right).$$ (5)

By induction, the general case is then

$$\phi(n)=n\left({1-{1\over p_1}}\right)\left({1-{1\over p_2}}\right)\cdots\left({1-{1\over p_r}}\right).$$ (6)

An interesting identity relates $\phi(n^2)$ to $\phi(n)$,

$$\phi(n^2)=n\phi(n).$$ (7)

Another identity relates the Divisors $d$ of $n$ to $n$ via

$$\sum_d \phi(d)=n.$$ (8)

The Divisor Function satisfies the Congruence

$$n\sigma(n)\equiv 2\ \left({{\rm mod\ } {\phi(n)}}\right)$$ (9)

for all Primes and no Composite with the exceptions of 4, 6, and 22 (Subbarao 1974), where $\sigma(n)$ is the Divisor Function. No Composite solution is currently known to

$$n-1\equiv 0\ \left({{\rm mod\ } {\phi(n)}}\right)$$ (10)

(Honsberger 1976, p. 35).

Walfisz (1963), building on the work of others, showed that

$$\sum_{n=1}^N \phi(n) ={3N^2\over\pi^2}+{\mathcal O}[N(\ln N)^{2/3}(\ln\ln N)^{4/3}],$$ (11)

and Landau (1900, quoted in Dickson 1952) showed that

$$\sum_{n=1}^N {1\over\phi(n)} = A\ln N+B+{\mathcal O}\left({\ln N\over N}\right),$$ (12)

where

$$A = \sum_{k=1}^\infty {[\mu(k)]^2\over k\phi(k)}={\zeta(2)\zeta(3)\over\zeta(6)}={315\over 2\pi^4}\zeta(3)$$

$$= 1.9435964368\ldots$$ (13)

$$B = \gamma {315\over 2\pi^4}\zeta(3)-\sum_{k=1}^\infty {[\mu(k)]^2\ln k\over k\phi(k)}$$

$$= -0.0595536246\ldots,$$ (14)

$\mu(k)$ is the Möbius Function, $\zeta(z)$ is the Riemann Zeta Function, and $\gamma$ is the Euler-Mascheroni Constant (Dickson). $A$ can also be written

$$A=\prod_{k=1}^\infty {1-{p_k}^6\over (1-{p_k}^{-2})(1-{p_k}^... ...)} = \prod_{k=1}^\infty \left[{1+{1\over p_k(p_k-1)}}\right].$$ (15)

Note that this constant is similar to Artin's Constant.

If the Goldbach Conjecture is true, then for every number $m$, there are Primes $p$ and $q$ such that

$$\phi(p)+\phi(q)=2m$$ (16)

(Guy 1994, p. 105).

Curious equalities of consecutive values include

$$\phi(5186)=\phi(5187)=\phi(5188)=2^5 3^4$$ (17)

$$\phi(25930)=\phi(25935)=\phi(25940)=\phi(25942)=2^7 3^4$$ (18)

$$\phi(404471)=\phi(404473)=\phi(404477)=2^8 3^2 5^2 7$$ (19)

(Guy 1994, p. 91).

The Summatory totient function, plotted above, is defined by

$$\Phi(n)\equiv \sum_{k=1}^n \phi(k)$$ (20)

and has the asymptotic series

$$\Phi(x) \sim {1\over 2\zeta(2)} x^2+{\mathcal O}(x\ln x)$$ (21)

$$\sim {3\over\pi^2} x^2+{\mathcal O}(x\ln x),$$ (22)

where $\zeta(z)$ is the Riemann Zeta Function (Perrot 1881). The first values of $\Phi(n)$ are 1, 2, 4, 6, 10, 12, 18, 22, 28, ... (Sloane's A002088).

See also Dedekind Function, Euler's Totient Rule, Fermat's Little Theorem, Lehmer's Problem, Leudesdorf Theorem, Noncototient, Nontotient, Silverman Constant, Totative, Totient Valence Function

References

Abramowitz, M. and Stegun, C. A. (Eds.). ``The Euler Totient Function.'' §24.3.2 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 826, 1972.

Beiler, A. H. Ch. 12 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.

Conway, J. H. and Guy, R. K. ``Euler's Totient Numbers.'' The Book of Numbers. New York: Springer-Verlag, pp. 154-156, 1996.

Courant, R. and Robbins, H. ``Euler's $\varphi$ Function. Fermat's Theorem Again.'' §2.4.3 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 48-49, 1996.

DeKoninck, J.-M. and Ivic, A. Topics in Arithmetical Functions: Asymptotic Formulae for Sums of Reciprocals of Arithmetical Functions and Related Fields. Amsterdam, Netherlands: North-Holland, 1980.

Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, pp. 113-158, 1952.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/totient/totient.html

Guy, R. K. ``Euler's Totient Function,'' ``Does $\phi(n)$ Properly Divide $n-1$,'' ``Solutions of $\phi(m)=\sigma(n)$,'' ``Carmichael's Conjecture,'' ``Gaps Between Totatives,'' ``Iterations of $\phi$ and $\sigma$,'' ``Behavior of $\phi(\sigma(n))$ and $\sigma(\phi(n))$.'' §B36-B42 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 90-99, 1994.

Halberstam, H. and Richert, H.-E. Sieve Methods. New York: Academic Press, 1974.

Honsberger, R. Mathematical Gems II. Washington, DC: Math. Assoc. Amer., p. 35, 1976.

Perrot, J. 1811. Quoted in Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, p. 126, 1952.

Shanks, D. ``Euler's $\phi$ Function.'' §2.27 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 68-71, 1993.

Sloane, N. J. A. Sequences A000010/M0299 and A002088/M1008 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Subbarao, M. V. ``On Two Congruences for Primality.'' Pacific J. Math. 52, 261-268, 1974.