Euler's totient function

Euler's totient function φ(n) counts the positive integers from 1 through n that are relatively prime to n. It is multiplicative on coprime inputs and governs the size of the units modulo n.

Euler product formula: The identity φ(n) = n∏(1 − 1/p), where the product ranges over distinct prime divisors p of n. It turns the count into a direct computation from n’s distinct prime factors.
Euler's theorem: For coprime integers a and n, Euler's theorem states that a raised to φ(n) is congruent to 1 modulo n. The totient supplies the exponent that guarantees this modular identity.
Coprime integers: Two integers are coprime when their greatest common divisor is 1. The function counts precisely the integers satisfying this relation with n.
Jordan totient function: A family of arithmetic functions counting tuples whose coordinates, together with n, have greatest common divisor 1. It generalizes φ(n), which is the one-dimensional case.
Multiplicative function: An arithmetic function f satisfying f(mn) = f(m)f(n) whenever m and n are relatively prime. This property explains why totients of coprime factors multiply.
RSA cryptosystem: A public-key cryptosystem whose security relies on the difficulty of factoring a product of two large primes. RSA uses φ(n) to construct a private exponent that reverses modular exponentiation.
Greatest common divisor: The greatest positive integer that divides each of two integers. Testing whether gcd(k,n) equals 1 determines which integers contribute to φ(n).
Dedekind psi function: An arithmetic function defined by ψ(n) = n∏(1 + 1/p) over the distinct prime divisors p of n. Its prime-factor formula uses plus signs where the totient formula uses minus signs.
Chinese remainder theorem: A theorem identifying residue classes modulo coprime integers with residue classes modulo their product. It gives a structural reason that φ(mn) = φ(m)φ(n) for coprime m and n.
Carmichael function: An arithmetic function giving the least positive exponent that makes every unit modulo n equal to 1 when raised to that exponent. It can provide a smaller exponent than φ(n) for modular exponentiation.

Linked from 21 pages