About the Euler's Totient Calculator
This Euler's totient calculator computes φ(n) — the number of integers from 1 to n that share no common factor with n other than 1. For n = 36 the answer is 12, because exactly twelve numbers (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35) are coprime to 36. The tool factors n into primes, applies Euler's product formula step by step and lists the coprime residues for smaller n.
Totients matter in number theory and cryptography. Euler's theorem says a^φ(n) ≡ 1 (mod n) whenever a and n are coprime, which is the basis of RSA key generation (where φ(pq) = (p − 1)(q − 1)) and of reducing huge modular exponents. Students meet φ(n) in discrete maths and abstract algebra, where it also counts the generators of a cyclic group of order n.
Alongside φ(n) you get the Carmichael function λ(n), the smallest exponent that works in Euler's theorem for every coprime base, and the ratio φ(n)/n. Any whole number up to one trillion (10¹²) can be entered; factorization is by exact trial division.
With the default inputs, the euler’s totient φ(n) is 12. Change any value above to recalculate instantly.
How to use the euler's totient calculator
- 1Enter a positive whole number n.
- 2Read φ(n) and the prime factorization it was built from.
- 3Check the product-formula line and the per-prime table to follow the working.
- 4For n up to 200, scan the full list of coprime integers.
Formula and method
Write n = p₁^k₁ × p₂^k₂ × … as a product of prime powers. Among the pᵏ numbers 1…pᵏ, exactly the multiples of p (there are pᵏ⁻¹ of them) share a factor with pᵏ, so φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). Because φ is multiplicative for coprime factors, φ(n) is the product of these contributions, which is the same as n × Π(1 − 1/p).
The Carmichael function λ(n) is the least common multiple of λ(pᵏ) over the prime powers, where λ(pᵏ) = φ(pᵏ) for odd primes, λ(2) = 1, λ(4) = 2 and λ(2ᵏ) = 2ᵏ⁻² for k ≥ 3. It always divides φ(n).
- φ(n)
- Euler's totient: count of 1 ≤ k ≤ n with gcd(k, n) = 1
- p
- A distinct prime factor of n
- λ(n)
- Carmichael function (reduced totient)
Worked examples
φ(36)
36 = 2² × 3², so φ(36) = 36 × (1 − ½) × (1 − ⅓) = 12. Equivalently (2 × 1) × (3 × 2) = 12. λ(36) = lcm(2, 6) = 6.
A prime: φ(97)
For a prime p every smaller positive integer is coprime to it, so φ(97) = 96.
φ(1000)
1000 = 2³ × 5³, so φ = (2² × 1) × (5² × 4) = 4 × 100 = 400. λ(1000) = lcm(λ(8), λ(125)) = lcm(2, 100) = 100.
A larger number: 123,456,789
123,456,789 = 3² × 3607 × 3803, so φ = 6 × 3606 × 3802 = 82,260,072.
Frequently asked questions
What is Euler's totient function?+
Euler's totient φ(n) counts how many integers from 1 to n are coprime to n, meaning their greatest common divisor with n is 1. For example φ(10) = 4 because 1, 3, 7 and 9 are coprime to 10.
How do you calculate φ(n) by hand?+
Factor n into primes, then multiply n by (1 − 1/p) for each distinct prime p. For 60 = 2² × 3 × 5: φ(60) = 60 × ½ × ⅔ × ⅘ = 16.
How is the totient used in RSA?+
RSA picks two primes p and q, sets n = pq and computes φ(n) = (p − 1)(q − 1). The public exponent e and private exponent d satisfy e·d ≡ 1 (mod φ(n)) — many implementations use λ(n) = lcm(p − 1, q − 1) instead.
What is the difference between φ(n) and λ(n)?+
φ(n) counts coprime residues; λ(n), the Carmichael function, is the smallest m with aᵐ ≡ 1 (mod n) for every a coprime to n. λ(n) always divides φ(n), and they are equal when n is 1, 2, 4, an odd prime power or twice an odd prime power.
Is φ(n) always even?+
Yes for every n greater than 2. Coprime numbers come in pairs k and n − k, which are different when n > 2, so the count is even. Only φ(1) = φ(2) = 1 are odd.