Euler's Totient Function Calculator

Number Theory & RSA

Enter a positive integer n and this tool computes Euler's totient function φ(n), shows the prime factorization of n, displays the multiplicative formula step-by-step, and can list all integers ≤ n that are coprime to n (for moderate sizes).

φ(n) via prime factors coprime integers up to n number theory & modular arithmetic RSA cryptography examples

Compute Euler's totient function φ(n)

Recommended range: 1 ≤ n ≤ 1012 for instant exact results.

For performance, the list is limited to n ≤ 2,000.

n = 10 n = 12 n = 60 n = 997 (prime)

Definition of Euler's totient function φ(n)

Euler's totient function \(\varphi(n)\) (also written φ(n)) is defined, for a positive integer \(n\), as the number of positive integers ≤ n that are coprime to n. Two integers are coprime if their greatest common divisor (gcd) is 1.

Formally,

\[ \varphi(n) = \left|\{\,1 \le k \le n : \gcd(k,n) = 1\,\}\right|. \]

In this calculator we use the fundamental identity that links φ(n) to the prime factorization of n.

Key formula for φ(n)

Let \(n > 1\) have prime factorization \[ n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \] where the \(p_i\) are distinct primes and the \(a_i \ge 1\). Then

\[ \varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) = \prod_{i=1}^{k} \left(p_i^{a_i} - p_i^{a_i - 1}\right). \]

In particular, if n is prime, \(n = p\), then \(\varphi(p) = p - 1\).

How to compute φ(n) – step by step

  1. Factor n into prime powers \(p_1^{a_1} \cdots p_k^{a_k}\).
  2. Apply the totient formula \(\varphi(n) = n \prod_i (1 - 1/p_i)\).
  3. Simplify each factor \((1 - 1/p_i) = (p_i - 1)/p_i\).
  4. Multiply to obtain the final integer value of φ(n).
  5. Optionally, verify by counting integers k ≤ n such that \(\gcd(k, n) = 1\) for small n.

Worked examples of Euler's totient function

n Prime factorization φ(n) Reason
1 – 1 By convention, the empty product gives φ(1) = 1.
10 2 · 5 4 φ(10) = 10 (1 − 1/2)(1 − 1/5) = 10 · 1/2 · 4/5 = 4.
12 22 · 3 4 φ(12) = 12 (1 − 1/2)(1 − 1/3) = 12 · 1/2 · 2/3 = 4.
15 3 · 5 8 φ(15) = 15 (1 − 1/3)(1 − 1/5) = 15 · 2/3 · 4/5 = 8.
p (prime) p p − 1 Every integer 1, …, p−1 is coprime to p.
pk pk pk − pk−1 Exclude the multiples of p among 1, …, pk.

Why φ(n) matters in modular arithmetic and cryptography

Euler's totient function appears naturally in Euler's theorem: for any integer a coprime to n,

\[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]

When n is the product of two primes, n = p · q, this is closely related to the exponent used in RSA encryption and decryption. Knowing φ(n) allows us to compute modular inverses of exponents and guarantees that certain congruences have unique solutions.

Typical use cases for this calculator

  • Checking results in number theory homework or exam preparation.
  • Exploring small RSA examples with n = p · q.
  • Investigating multiplicative arithmetic functions.
  • Generating tables of φ(n) for patterns and conjectures.

Related number theory tools