Euler's totient function (phi): definition, properties, and applications

Basic formulas and properties

The totient function is multiplicative: if a and b are coprime then ϕ(ab)=ϕ(a)ϕ(b). Its value on prime powers is simple: for a prime p and k≥1,

• ϕ(p^k) = p^k − p^{k−1} = p^k(1 − 1/p).

From this one obtains the Euler product for any n with prime factorization n=∏ p_i^{e_i}: ϕ(n)=n∏(1−1/p_i). A number-theoretic consequence is that ϕ(n) is even for every n>2.

Algebraic interpretation and theorems

Value ϕ(n) equals the order of the multiplicative group of units modulo n, i.e. the group of integers coprime to n under multiplication modulo n. More precisely, ϕ(n) is the size of the unit group of the ring Z/nZ. This connection yields important results: applying Lagrange's theorem to that group gives Euler's theorem, which generalizes Fermat's little theorem.

History and naming

The function is named after the Swiss mathematician Euler, though related ideas appeared earlier. Euler used the function in the 18th century while studying modular arithmetic and primitive roots; modern notation and study grew from that work and subsequent developments by other scholars and historians of mathematics. The name "phi" (ϕ) is common in contemporary texts.

Examples, computation, and inversion

Simple values include ϕ(p)=p−1 for prime p and ϕ(1)=1. Small examples: ϕ(9)=6, ϕ(10)=4. One computes ϕ(n) by factoring n and applying the product formula; therefore, efficient computation depends on integer factorization. Möbius inversion and related identities allow reconstruction of multiplicative sums involving ϕ, and the cototient n−ϕ(n) measures how many integers ≤n share a nontrivial factor with n.

Applications and notable distinctions

Euler's totient function appears in cryptography (notably the RSA algorithm) because knowledge of ϕ(n) for a composite modulus yields information that can break certain public-key schemes. In algebraic number theory and group theory it helps describe structure of unit groups and cyclotomic polynomials. It is multiplicative but not completely multiplicative, and should not be confused with related functions such as the Carmichael function, which gives the exponent of the unit group rather than its order.

Further remarks

Many problems and results center on averages and extremal behavior of ϕ(n): for example, the average order of ϕ(n) is (3/π^2)n, and there are infinitely many n for which ϕ(n) takes the same value (the "totient equation" and its inverses are active research areas). For an introduction to proofs and more examples, see standard texts in elementary number theory and online references. For background reading, consult resources on the phi function, the role of mathematicians in its development, and connections to the multiplicative group modulo n.

Key references and further material: definitions and elementary proofs can be found in introductory number theory courses; algorithmic issues and cryptographic implications are discussed in computational number theory and applied cryptography texts. See also classic theorems linked above for formal statements and proofs.