1 Definition and basic properties

Euler’s totient function is one of the central arithmetic functions of elementary number theory. It measures, for each positive integer n, how many integers from 1 through n are relatively prime to n. Because the notion of relative primality depends on the prime factorization of n, the function is closely tied to the structure of the integers and to modular arithmetic.

1.1 Formal definition

The totient function, written φ(n), is defined for every positive integer n by the number of integers k with 1 ≤ k ≤ n such that gcd(k, n) = 1. Here gcd denotes the greatest common divisor. By convention, φ(1) = 1, since 1 is relatively prime to itself.

1.2 Coprimality and counting interpretation

The function counts the reduced residue classes modulo n. In practical terms, it records how many integers less than or equal to n can serve as multiplicative units modulo n. This counting interpretation makes φ(n) a bridge between divisibility and modular arithmetic.

1.3 Values for small integers

For small n, the values of φ(n) are easy to compute directly: φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, and φ(6) = 2. These examples already show that the function does not grow steadily and that it depends strongly on the prime factors of n.

1.4 Relation to the gcd

The definition of φ(n) is stated in terms of the greatest common divisor. An integer k contributes to φ(n) precisely when gcd(k, n) = 1. This relation makes the totient function a natural tool for counting numbers that avoid all prime divisors of n.

2 Computation formulas

Several exact formulas allow φ(n) to be computed efficiently once the prime factorization of n is known. These formulas are among the most useful properties of the function and explain many of its arithmetic features.

2.1 Totient of a prime

If p is prime, then every integer from 1 to p − 1 is relatively prime to p. Hence φ(p) = p − 1. This is the simplest nontrivial case and serves as a starting point for more general formulas.

2.2 Totient of a prime power

For a prime p and integer k ≥ 1, the totient of p^k is φ(p^k) = p^k − p^(k−1) = p^k(1 − 1/p). These are the integers up to p^k that are not divisible by p, so the count is obtained by subtracting the multiples of p.

2.3 Multiplicative formula for general n

If the prime factorization of n is n = p_1^a1 p_2^a2 ... p_r^ar, then φ(n) = n(1 − 1/p_1)(1 − 1/p_2)...(1 − 1/p_r). This formula depends only on the distinct primes dividing n, not on their exponents alone.

2.3.1 Product over distinct prime factors

The product formula can be written in terms of the radical structure of n: φ(n) = n ∏(1 − 1/p), where the product runs over all distinct primes p dividing n. It shows that each prime divisor reduces the count by a fixed proportion.

2.3.2 Derivation from inclusion-exclusion

One way to derive the formula is by counting integers from 1 to n and excluding those divisible by at least one prime factor of n. Inclusion-exclusion adjusts for overlaps among the sets of multiples of the prime divisors. The resulting count yields the product formula above.

2.4 Efficient algorithms for computing φ(n)

In computational settings, φ(n) is usually found by first factoring n. Once the prime factors are known, the product formula gives the value quickly. For many inputs, sieving methods or factorization routines are used to obtain φ-values for all integers up to a bound. When factorization is unavailable, the problem is generally much harder.

3 Arithmetic properties

The totient function satisfies a number of basic arithmetic laws and inequalities. Many of these properties reflect its multiplicative nature and its dependence on prime factors.

3.1 Multiplicativity

The function φ is multiplicative: if gcd(m, n) = 1, then φ(mn) = φ(m)φ(n). This property follows from the Chinese remainder structure of residues modulo mn and is a defining feature of the function among arithmetic counts.

3.2 Parity and divisibility properties

For n > 2, φ(n) is even. This is because the reduced residues modulo n can be paired with their negatives, which are distinct modulo n except in very small cases. Also, φ(n) divides n − 1 when n is prime, but in general it need not divide n or n − 1.

3.3 Bounds and asymptotic behavior

The size of φ(n) varies widely. It is often much smaller than n, especially when n has many distinct prime factors, but it remains on average comparable to n.

3.3.1 Upper bounds

Since each factor (1 − 1/p) is less than 1, one always has φ(n) ≤ n. Sharper bounds show that φ(n) is often significantly smaller than n when n is divisible by many small primes. In general, φ(n) can be bounded using the prime factorization of n.

3.3.2 Average order

On average, φ(n) is proportional to n. More precisely, the summatory behavior of φ shows that its mean size over large intervals is governed by a constant multiple of n. This reflects the average density of integers coprime to a typical integer.

3.4 Numbers with equal totients

Different integers can share the same totient value. Such coincidences arise because φ compresses information about prime factors into a single count. The study of integers n and m with φ(n) = φ(m) leads to questions about the distribution of totient values and the size of their preimages.

4 Connections with modular arithmetic

The totient function is deeply connected to the algebra of congruences. It describes the number of invertible residue classes modulo n and appears in fundamental theorems about powers modulo integers.

4.1 Euler’s theorem

If gcd(a, n) = 1, then a^φ(n) ≡ 1 mod n. This is Euler’s theorem, a generalization of Fermat’s little theorem. It is one of the best-known applications of the totient function and provides a basic method for reducing exponents in modular arithmetic.

4.2 Reduced residue systems

A reduced residue system modulo n is a complete set of integers representing the residue classes coprime to n. Its size is exactly φ(n). Such systems are important in modular arithmetic because they describe all invertible elements modulo n.

4.3 Orders of integers modulo n

If gcd(a, n) = 1, the multiplicative order of a modulo n divides φ(n). This follows from Euler’s theorem and the structure of the group of units modulo n. The totient therefore gives a universal upper bound on the order of any invertible residue class.

4.4 Carmichael function comparison

The Carmichael function λ(n) gives the exponent of the multiplicative group modulo n, and it is often a smaller bound than φ(n). While φ(n) counts the number of units modulo n, λ(n) measures the largest order that can occur. The two functions are related but serve different purposes in number theory.

5 Summatory and analytic aspects

Analytic number theory studies how φ(n) behaves when averaged over many integers. These questions connect the totient function with Dirichlet series, products over primes, and asymptotic estimates.

5.1 Totient summatory function

The summatory totient function is ∑_{n ≤ x} φ(n). Its growth is approximately quadratic in x. This reflects the average number of coprime pairs among integers up to x and gives a global measure of totient distribution.

5.2 Dirichlet generating function

The Dirichlet generating function of φ is ∑_{n=1}^∞ φ(n)/n^s = ζ(s−1)/ζ(s), for values of s where the series converges. This identity links the totient function to the Riemann zeta function and reveals its multiplicative structure.

5.3 Euler product representation

Because φ is multiplicative, its Dirichlet series can be written as an Euler product over primes. This product form encodes the contribution of each prime separately and is a standard tool for deriving analytic properties of arithmetic functions.

5.4 Analytic estimates

Analytic methods yield precise estimates for averages and error terms associated with φ. These results describe how regularly the totient function is distributed and how closely summatory formulas approximate their leading terms. Such estimates are important in both theoretical and computational number theory.

Beyond evaluating φ(n), mathematicians also study which values occur, how often they occur, and what patterns emerge when the function is iterated.

6.1 Totient values and preimages

A given integer m may have no preimage under φ, one preimage, or many. The set of n such that φ(n) = m is called the preimage of m under the totient function. Understanding these sets is a classic inverse problem and is often difficult.

6.2 Highly totient and noncototient numbers

Some numbers occur as φ(n) for many different n; these are often called highly totient values. By contrast, a noncototient number is an integer that is not of the form n − φ(n) for any n. Such topics study the range and complement of totient-related functions.

6.3 Totient chains

A totient chain is formed by repeatedly applying φ: n, φ(n), φ(φ(n)), and so on. Since φ(n) is usually smaller than n for n > 2, the chain eventually reaches 1. The length and shape of these chains are subjects of recreational and structural interest.

6.4 Iterates of the totient function

The k-fold iterate φ^k(n) applies the function repeatedly k times. Iterated totients reveal how quickly numbers descend under repeated application. These iterates are useful in studying arithmetic dynamics on the positive integers.

7 Applications

The totient function appears in several areas where multiplicative structure and modular arithmetic are central. Its role is both theoretical and practical.

7.1 Cryptography

In classical public-key cryptography, especially RSA, φ(n) is used when n is a product of two large primes. The function helps determine exponents that invert each other modulo φ(n), enabling encryption and decryption schemes based on modular exponentiation.

7.2 Primitive roots and cyclic groups

The existence and number of primitive roots modulo n are linked to the structure of the multiplicative group of units, whose size is φ(n). Since primitive roots generate the full unit group when it is cyclic, the totient function is essential in describing those cases.

7.3 Counting lattice points and coprime pairs

The totient function can be used to count coprime pairs and to analyze lattice points with arithmetic restrictions. Sums involving φ(n) often appear when counting visible points from the origin, since visible lattice points correspond to pairs of integers with gcd 1.

8 Generalizations and analogues

The totient function is the best-known example of a family of arithmetic counts that measure invertibility or coprimality in broader settings. Several useful generalizations extend its ideas.

8.1 Jordan totient function

The Jordan totient functions J_k(n) generalize φ(n) by counting k-tuples of integers that are coprime to n in a suitable sense. When k = 1, J_1(n) is exactly φ(n). These functions arise naturally in higher-dimensional counting problems.

8.2 Other arithmetic functions counting units

Other functions related to φ count units in modified algebraic settings or track the size of related residue systems. Examples include functions that count invertible elements in restricted rings or semigroups. Such analogues preserve the basic idea of measuring how many elements behave multiplicatively like units.

8.3 Group-theoretic generalizations

In abstract algebra, the role of φ(n) is played by the order of the unit group of a ring or by analogous size functions in more general groups. These generalizations show that the totient function is not only a number-theoretic tool but also a special case of broader counting principles in algebra.