Euler Totient Calculator φ(n)

Compute Euler's totient function φ(n): count of integers from 1 to n that are coprime to n. Includes range mode, coprime verification, Carmichael λ(n), and RSA key generation context.

φ(n)
—
Prime Factors of n —
Formula Applied —
Extended More scenarios, charts & detailed breakdown ▾
φ(n)
—
Prime Factors —
Multiplicativity Note —
Professional Full parameters & maximum detail ▾

Totient & Carmichael

φ(n) —
Carmichael λ(n) —

Theorems & Applications

Euler's Theorem: a^φ(n) mod n —
Totient Sum: Σ_{d|n} φ(d) = n —
RSA Role —

How to Use This Calculator

  1. Enter a positive integer n.
  2. φ(n) and its prime factorization appear instantly.
  3. Use Range tab to see φ(k) for all k from 1 to N.
  4. Use Verify Coprime to list all integers coprime to n and confirm the count matches φ(n).
  5. Use Professional for Carmichael λ(n) and Euler's theorem verification.

Formula

φ(n) = n × Π (1 − 1/p) over all distinct prime factors p of n

Euler's theorem: a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1

Example

n=12=2²×3: φ(12)=12×(1−½)×(1−⅓)=12×½×⅔=4. Coprimes: {1,5,7,11}.

Frequently Asked Questions

  • φ(n) counts how many integers from 1 to n share no common factor with n (i.e., gcd(k,n)=1). For example, φ(12)=4 because 1, 5, 7, 11 are coprime to 12.
  • Factor n into distinct primes p₁, p₂, …: φ(n) = n × (1−1/p₁) × (1−1/p₂) × … For n=12=2²×3: φ(12)=12×(1−½)×(1−⅓)=4.
  • If gcd(a,n)=1, then a^φ(n) ≡ 1 (mod n). This is the foundation of RSA encryption: raising a number to a power mod n cycles back to 1.
  • λ(n) is the smallest positive integer m such that a^m ≡ 1 (mod n) for all a coprime to n. It always divides φ(n) and is used in modern RSA implementations.
  • RSA uses n=p×q (two primes). φ(n)=(p−1)(q−1). The private key d = e⁻¹ mod φ(n). Security relies on the difficulty of computing φ(n) without knowing p and q.

Related Calculators

mod⁻¹ Modular Inverse 🔐 RSA Key Calculator gcd+ Extended Euclidean # GCD & LCM
Sources & References (5) ▾
  1. An Introduction to the Theory of Numbers — Hardy & Wright — Oxford University Press
  2. Euler's Totient Function — Wolfram MathWorld — Wolfram Research
  3. Khan Academy — Euler's Totient Function — Khan Academy
  4. NIST Digital Library of Mathematical Functions — §27.2 — NIST
  5. OpenStax Discrete Mathematics — Number Theory — OpenStax