Euler's totient function, denoted φ(n), serves as a cornerstone of number theory by counting the positive integers up to a given integer n that are relatively prime to n. This arithmetic function transforms abstract concepts of divisibility and greatest common divisors into a precise quantitative measure. Understanding the behavior of numbers through this lens reveals deep structural properties that underpin modern cryptography, particularly in the RSA encryption algorithm.
Defining Relative Primality and Core Functionality
To grasp the essence of the totient, one must first understand the concept of relative primality. Two integers are relatively prime, or coprime, if their greatest common divisor (gcd) is 1. This means they share no prime factors. The function φ(n) effectively filters the set {1, 2, ..., n}, isolating only those elements that satisfy this condition of gcd(k, n) = 1. For example, φ(9) equals 6 because the numbers 1, 2, 4, 5, 7, and 8 share no common factors with 9 aside from 1.
The Fundamental Formula for Prime Powers
Deriving the Base Case
The calculation becomes remarkably straightforward when n is a prime number p. Since primes are only divisible by 1 and themselves, every integer from 1 to p-1 is coprime to p. Consequently, the totient of a prime p is simply p-1. Extending this logic to prime powers, the formula φ(p^k) = p^k - p^(k-1) emerges naturally. This accounts for all p^k numbers while subtracting the p^(k-1) multiples of p that share the prime factor, leaving only the integers that maintain relative primality.
The Multiplicative Property and General Formula
A crucial property of Euler's totient function is its multiplicativity. If two numbers a and b are coprime, then the totient of their product is the product of their totients, expressed as φ(ab) = φ(a)φ(b). This allows the function to be decomposed across the unique prime factorization of any integer n. If n can be expressed as the product of primes raised to their respective powers, n = p1^a1 * p2^a2 * ... * pk^ak, the general formula takes shape. The totient of n is the product of (pi^ai - pi^(ai-1)) for each distinct prime factor, or more compactly, n multiplied by the product of (1 - 1/p) for each prime p dividing n.
