Sign in to watch this lesson
Advanced - Number Theory · 5:09
Euler's Totient Function and Euler's Theorem
Euler's totient φ(n) counts the numbers from 1 to n that share no factor with n; sorting the fractions k/n by reduced denominator shows that the totients of the divisors of n add up to n. It is computed as n·Π(1 − 1/p) in O(√n) for one number or with a sieve for a whole range, and Euler's theorem uses it to shrink huge exponents, with an extra φ(m) when the base shares a factor with the modulus, which is exactly what power towers need.
You will learn
- Define φ(n), compute it as n·Π(1 − 1/p) in O(√n) without forgetting the leftover prime above √n
- Explain why Σ_{d|n} φ(d) = n and why φ is multiplicative for coprime arguments
- Compute φ for every number up to n with a sieve, and for a window [L, R] near 10^12 with a segmented sieve
- Reduce exponents with Euler's theorem when gcd(a, m) = 1, use the generalized rule x^n ≡ x^(φ(m) + n mod φ(m)) for any base, and evaluate power towers through the φ chain