## Totient Function

The totient function , also called Euler's totient function, is defined as the number of Positive Integers which 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 .

By convention, . The first few values of for , 2, ... are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (Sloane's A000010). 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 which 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 which must be subtracted from to obtain is
 (4)

and
 (5)

By induction, the general case is then
 (6)

An interesting identity relates to ,
 (7)

Another identity relates the Divisors of to via
 (8)

The Divisor Function satisfies the Congruence

 (9)

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

(Honsberger 1976, p. 35).

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

 (11)

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

where
 (13) (14)

is the Möbius Function, is the Riemann Zeta Function, and is the Euler-Mascheroni Constant (Dickson). can also be written
 (15)

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

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

 (16)

(Guy 1994, p. 105).

Curious equalities of consecutive values include

 (17)

 (18)

 (19)

(Guy 1994, p. 91).

The Summatory totient function, plotted above, is defined by

 (20)

and has the asymptotic series
 (21) (22)

where is the Riemann Zeta Function (Perrot 1881). The first values of 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 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 Properly Divide ,'' Solutions of ,'' Carmichael's Conjecture,'' Gaps Between Totatives,'' Iterations of and ,'' Behavior of and .'' §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 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.