Euler phi function

Euler phi function
Pietro Battiston (it:User:Toobaz) · CC BY-SA 4.0 · source
Name	Euler phi function
Domain	positive integers
Codomain	positive integers
Introduced by	Leonhard Euler
Year introduced	1763
Related	Euler's theorem, Euler totient theorem, Carmichael function, Möbius function

Euler phi function

The Euler phi function is a multiplicative arithmetical function that counts positive integers up to a given integer n that are coprime to n. Originating in the work of Leonhard Euler in the 18th century, it plays a central role in elementary number theory, analytic number theory, and modern cryptography, particularly in proofs of Euler's theorem and constructions like the RSA algorithm. The function links to classical results of Pierre de Fermat and later developments involving Dirichlet characters, Möbius inversion, and the distribution of prime numbers studied by Carl Friedrich Gauss and Bernhard Riemann.

Definition and basic properties

For a positive integer n, the Euler phi function φ(n) is defined as the number of integers k with 1 ≤ k ≤ n for which gcd(k,n) = 1. Basic properties include φ(1) = 1, φ(2) = 1, and φ(n) = n−1 for n prime, reflecting connections to the work of Pierre de Fermat on prime residues. The function is multiplicative in the sense familiar from studies by Adrien-Marie Legendre and Évariste Galois: if gcd(m,n)=1 then φ(mn)=φ(m)φ(n). It also satisfies inequalities and monotonicity properties used in proofs by Srinivasa Ramanujan and later by Paul Erdős.

Multiplicativity and formula

Multiplicativity yields the prime-power formula: for a prime p and integer k ≥ 1, φ(p^k) = p^k − p^{k−1} = p^k(1−1/p). Combined with the Fundamental Theorem of Arithmetic—established in modern form by Gauss—this gives the product formula for general n with prime factorization n = ∏ p_i^{a_i}: φ(n) = n ∏ (1−1/p_i). This formulation links to the Möbius function μ(n) through inversion identities exploited by Augustin-Louis Cauchy and later by Johann Peter Gustav Lejeune Dirichlet in his work on arithmetic progressions. The formula also underpins counting arguments in classical results by Émile Borel and combinatorial applications studied by George Pólya.

Values and examples

Values of φ(n) for small n illustrate behavior: φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4. For n equal to a product of distinct primes, such as n=30=2·3·5, one gets φ(30)=8, reflecting multiplicative structure analyzed by Leonhard Euler and cataloged in tables by Adrien-Marie Legendre. Special classes of integers relate to φ-values: primes p satisfy φ(p)=p−1, powers of primes follow φ(p^k)=p^{k−1}(p−1), and numbers with φ(n) odd are precisely n = 1 or n = 2 or n = 4 or n = 2p^k for odd prime p, a classification explored by Srinivasa Ramanujan and formalized by later researchers including Karl Wilhelm Borchardt. Much work by Erdős and Pál Erdős (note: same surname reference) investigated preimage sets {n : φ(n)=m} and conjectures on their sizes.

Analytic and asymptotic results

Analytic study of φ(n) connects to average and extremal behavior. Mertens-type estimates and summatory functions Σ_{k≤x} φ(k) relate to results of Jacques Hadamard and Charles Jean de la Vallée-Poussin on prime distribution and culminate in asymptotics like Σ_{k≤x} φ(k) ~ 3x^2/π^2 as x→∞, drawing on Bernhard Riemann's insights into zeta-function methods. Lower and upper bounds for φ(n) involve inequalities established by Nikolai Ivanovich Lobachevsky (historical analytic techniques) and refined by Pál Turán and Paul Erdős. Problems about values of φ(n) and multiplicative inverses tie into zero-free regions for the Riemann zeta function and conjectures influenced by G. H. Hardy and John Littlewood.

Applications in number theory and cryptography

In number theory, φ(n) underlies Euler's theorem: a^φ(n) ≡ 1 (mod n) for gcd(a,n)=1, a generalization of Fermat's little theorem used in proofs by Euler and later exploited by Dirichlet and Lejeune Dirichlet. Cryptography uses φ(n) in key generation and correctness proofs for RSA, with security based on the difficulty of factoring n into primes as studied by Carl Friedrich Gauss and modern computational complexity theory developed by Alan Turing and Donald Knuth. Protocols in public-key infrastructure and standards from organizations like National Institute of Standards and Technology rely on φ-related number-theoretic primitives and hardness assumptions examined by Adi Shamir and Rivest, Shamir, and Adleman.

Generalizations and related functions

Generalizations include the Jordan totient functions J_k(n), which count k-tuples of integers with joint coprimality properties and were studied by Camille Jordan; the Carmichael function λ(n), giving the exponent of the multiplicative group modulo n and investigated by Robert Carmichael; and multiplicative functions constructed via convolutions with the Möbius function μ(n) as in the work of Möbius. Connections extend to multiplicative order studies by Évariste Galois, group-theoretic interpretations in Évariste Galois's theory, and to arithmetic functions such as τ(n) and σ(n) cataloged by Niccolò Paganini (historical compilers) and modern expositors like Tom M. Apostol. Recent research links totient values to sieve methods of Atle Selberg and distribution questions pursued by Paul Erdős and contemporary analytic number theorists.

Category:Number theory