Euler Totient Calculator
Compute Euler's totient φ(n) — the count of integers up to n that are coprime to n.
Inputs
Positive integer. φ(n) counts how many integers from 1 to n are coprime to n.
φ(n)
4
Prime Factors of n
2, 3
Calculation
φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 4
Step by step
Prime factors of n
2, 3
Product formula
φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 4
φ(n)
= 4
How it works
Euler's totient function φ(n) counts the integers from 1 to n that are coprime to n (share no common factor other than 1). It is computed efficiently via the product formula: φ(n) = n × ∏(1 − 1/p) over all distinct prime factors p of n. For a prime p, φ(p) = p − 1. The totient is fundamental in RSA cryptography, where it determines the modular inverse of the public exponent.
Formula
Euler's product formula
φ(n) = n × ∏(1 − 1/p) for each distinct prime factor p of n
- n
- Positive integer
- p
- Distinct prime factor of n
Frequently Asked Questions
What is φ(1)?
φ(1) = 1 by convention — the only integer from 1 to 1 is 1 itself, and gcd(1, 1) = 1.
How is the totient used in RSA?
In RSA, the private key d is the modular inverse of the public exponent e modulo φ(n), where n = p×q for two large primes. Knowing φ(n) is equivalent to being able to factor n.