Counting coprimes
The Euler totient of a number counts how many positive integers below it are coprime to it, sharing no common factor but one. For a prime, every smaller positive number qualifies, so the totient is the prime minus one.
Computing it from factors
The totient is multiplicative over coprime parts, so factor the number into primes and combine per prime:
- For each distinct prime factor, multiply the running result by one minus the reciprocal of that prime.
- Equivalently, start from the number and for each prime factor subtract the share it removes.
Only the distinct primes matter, not their exponents, when applying the per prime adjustment.
Why it matters
Euler's theorem generalizes Fermat: a number coprime to the modulus raised to the totient gives one. This lets you reduce huge exponents under a non prime modulus and underlies many modular identities.
Key idea
The Euler totient counts integers coprime to a number and is computed from its distinct prime factors, generalizing Fermat so that a coprime base raised to the totient is one under any modulus.