Euler's Totient Function Calculator

Euler's totient function calculator. Enter an integer n to get φ(n), prime factorization, formula breakdown, and (optionally) the list of integers less than n that are coprime to n. Useful for number theory and RSA cryptography.

Full original guide (expanded)

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

Audit: Complete
Formula (LaTeX) + variables + units
This section shows the formulas used by the calculator engine, plus variable definitions and units.
Formula (extracted LaTeX)
\[\varphi(n) = \left|\{\,1 \le k \le n : \gcd(k,n) = 1\,\}\right|.\]
\varphi(n) = \left|\{\,1 \le k \le n : \gcd(k,n) = 1\,\}\right|.
Formula (extracted LaTeX)
\[n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},\]
n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},
Formula (extracted LaTeX)
\[\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).\]
\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).
Formula (extracted LaTeX)
\[a^{\varphi(n)} \equiv 1 \pmod{n}.\]
a^{\varphi(n)} \equiv 1 \pmod{n}.
Formula (extracted LaTeX)
\[','\\]
','\
Formula (extracted LaTeX)
\[\\varphi(' + n + ') = ' + n + ' \\cdot ' + productParts.join('\\,') + ' = ' + phi + '.\\]
\\varphi(' + n + ') = ' + n + ' \\cdot ' + productParts.join('\\,') + ' = ' + phi + '.\
Formula (extracted text)
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\).
Variables and units
  • No variables provided in audit spec.
Sources (authoritative):
Changelog
Version: 0.1.0-draft
Last code update: 2026-01-19
0.1.0-draft · 2026-01-19
  • Initial audit spec draft generated from HTML extraction (review required).
  • Verify formulas match the calculator engine and convert any text-only formulas to LaTeX.
  • Confirm sources are authoritative and relevant to the calculator methodology.
Verified by Ugo Candido on 2026-01-19
Profile · LinkedIn
Formulas

(Formulas preserved from original page content, if present.)

Version 0.1.0-draft
Citations

Add authoritative sources relevant to this calculator (standards bodies, manuals, official docs).

Changelog
  • 0.1.0-draft — 2026-01-19: Initial draft (review required).