Number Theory
Advanced

Euler's Totient

Counts integers up to n coprime to n.

Formula

ϕ(n)=n∏p∣n(1−1p)\phi(n) = n\prod_{p|n}\left(1 - \frac{1}{p}\right)

Variables

nPositive integer
pPrime divisors

Example

φ(12) = 4

Did You Know?

Euler's totient counts the numbers coprime to n — the secret sauce inside RSA key generation.

totienteulernumber theory