In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. For example, φ(8) = 4 since the four numbers 1, 3, 5 and 7 are coprime to 8. The function φ so defined is the totient function. The totient is usually called the Euler totient or Euler's totient, after the Swiss mathematician Leonhard Euler, who studied it. The totient function is also called Euler's phi function or simply the phi function, since the letter Phi (φ) is so commonly used for it. Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ... The Swiss Confederation or Switzerland is a landlocked federal state in Europe, with neighbours Germany, France, Italy, Austria and Liechtenstein. ... Leonhard Euler aged 49 (oil painting by Emanuel Handmann, 1756) Leonhard Euler (April 15, 1707 - September 18, 1783) (pronounced oiler) was a Swiss mathematician and physicist. ... Phi (upper case Φ, lower case φ), pronounced fee or fie (depending on context and, often, personal inclination), is the 21st letter of the Greek alphabet. ...

The totient function is important chiefly because it gives the size of the multiplicative group of integers modulo n -- more precisely, φ(n) is the order of the group of units of the ring . This fact, together with Lagrange's theorem, provides a proof for Euler's theorem. In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... Modular arithmetic is a modified system of arithmetic for integers, sometimes referred to as clock arithmetic, where numbers wrap around after they reach a certain value (the modulus). ... In mathematics, a unit in a ring R is an element u such that there is v in R with uv = vu = 1R. That is, u is an invertible element of the multiplicative monoid of R. The units of R form a group U(R) under multiplication, the group of... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... In mathematics, most commonly, Lagranges theorem states that if G is a finite group and H is a subgroup of G, then the order (that is, the number of elements) of H divides the order of G. This can be shown using the concept of left cosets of H... In number theory, Eulers theorem (also known as the Fermat-Euler theorem) states that if n is a positive integer and a is coprime to n, then aφ(n) ≡ 1 ( mod n) where φ(n) denotes Eulers totient function. ...

Computing Euler's function

It follows from the definition that φ(1) = 1, and φ(n) is (p-1)p^k-1 when n is the kth power of a prime p^k. Moreover, φ is a multiplicative function; if m and n are coprime then φ(mn) = φ(m)φ(n). (Sketch of proof: let A, B, C be the sets of residue classes modulo-and-coprime-to m, n, mn respectively; then there is a bijection between AxB and C, via the Chinese remainder theorem.) The value of φ(n) can thus be computed using the fundamental theorem of arithmetic: if In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then f(ab) = f(a) f(b). ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one-to-one and onto. ... The Chinese remainder theorem is any of a number of related results in abstract algebra and number theory. ... In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 can be written as a product of prime numbers in only one way. ...

n = p₁^k₁ ... p_r^k_r

where the p_j are distinct primes, then In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ...

φ(n) = (p₁−1) p₁^k₁−1 ... (p_r−1) p_r^k_r−1.

This last formula is an Euler product and is often written as In mathematics, an Euler product is an infinite product expansion, indexed by prime numbers p, of a Dirichlet series. ...

with the product ranging only over the distinct primes p_r.

Other properties

The number φ(n) is also equal to the number of generators of the cyclic group C_n (and therefore also to the degree of the cyclotomic polynomial Φ_n). Since every element of C_n generates a cyclic subgroup and the subgroups of C_n are of the form C_d where d divides n (written as d|n), we get In mathematics, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that every element of the group is a power of a. ... In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ... In mathematics, given a group G under a binary operation *, we say that some subset H of G is a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H is a group operation... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

where the sum extends over all positive divisors d of n.

We can now use the Möbius inversion formula to "invert" this sum and get another formula for φ(n):

where μ is the usual Möbius function defined on the positive integers. Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...

If a is coprime to n, that is, (a,n)=1 then In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ...

.

Generating functions

A Dirichlet series involving φ(n) is In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... In mathematics, a Dirichlet series, one of a number of concepts named in honor of Johann Peter Gustav Lejeune Dirichlet, is a series of the form The most famous of Dirichlet series is which is the Riemann zeta function. ...

A Lambert series generating function is A Lambert series, named after Johann Heinrich Lambert, is a series taking the form It can be resummed by expanding the denominator: where the coefficients of the new series are given by the Dirichlet convolution of with the constant function Since this last sum is a typical number-theortic sum...

which holds for |q|<1.

Growth of the function

The growth of φ(n) as a function of n is an interesting question, since the first impression from small n that φ(n) might be noticeably smaller than n is somewhat misleading. Asymptotically we have

n^1−ε < φ(n) < n

for any given ε > 0 and n > N(ε). In fact if we consider

φ(n)/n

we can write that, from the formula above, as the product of factors

1 −p⁻¹

taken over the prime numbers p dividing n. Therefore the values of n corresponding to particularly small values of the ratio are those n that are the product of an initial segment of the sequence of all primes. From the prime number theorem it can be shown that a constant ε in the formula above can therefore be replaced by In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. ...

C loglog n/log n.

This behavior also holds in an average sense:

where the big O is the Landau symbol. In complexity theory, computer science, and mathematics the Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

Some values of the function

See also

• Nontotient
• Noncototient
• Highly totient number
• Highly cototient number

A nontotient is a positive integer n which is not in the range of Eulers totient function φ, that is, for which φ(x) = n has no solution. ... A noncototient is a positive integer n that can not be expressed as the difference between a positive integer m and the number of coprime integers below it. ... A highly totient number k is an integer that has more solutions to the equation φ(x) = k, where φ is Eulers totient function, than any integer below it. ...

References

• Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications, New York. ISBN 486-61272-4 . See paragraph 24.3.2.