purpose

Euler\u2019s Totient Calculator

Compute Euler\u2019s totient \u03C6(n) \u2014 the count of integers coprime to n. Used in RSA cryptography.

Back to Prime Factorization Calculator

Prime Factorization Tips

Click to show tips

Try an Example

Pick a scenario to see how the calculator works, then adjust the values

Highly Composite Number

Factor 360, a highly composite number with many divisors.

Key values: 360 = 2^3 x 3^2 x 5 · 24 divisors · phi(360) = 96

Large Prime

Check if 7919 is prime (it is -- the 1000th prime number).

Key values: 7919 is prime · 2 divisors · phi(7919) = 7918

GCD and LCM

Compute the GCD and LCM of 84 and 120.

Key values: 84 = 2^2 x 3 x 7 · 120 = 2^3 x 3 x 5 · GCD = 12, LCM = 840

Documentation

Euler's Totient Function

Euler's totient function $\phi(n)$ counts how many integers in the range [1, n] are coprime to $n$ (share no common factor other than 1).

\phi(n) = n \times \prod_{p | n} \left(1 - \frac{1}{p}\right)

The product runs over all distinct prime factors of $n$ . For a prime $p$ , $\phi(p) = p - 1$ (every number from 1 to $p-1$ is coprime to a prime).

RSA Cryptography Connection

Euler's totient is the mathematical backbone of RSA encryption, the most widely used public-key cryptosystem:

Choose two large primes $p$ and $q$
Compute $n = p \times q$ (the public modulus)
Compute $\phi(n) = (p-1)(q-1)$ (the secret)
Choose public exponent $e$ coprime to $\phi(n)$
Compute private exponent $d \equiv e^{-1} \pmod{\phi(n)}$

Security relies on the difficulty of factoring $n$ to recover $p$ and $q$ , and hence $\phi(n)$ .

Scale of the problem: For $n = 91 = 7 \times 13$ , $\phi(91) = 6 \times 12 = 72$ — trivial with small primes. But for 1024-bit primes (each ~300 digits), the factorization is computationally infeasible with current technology.

Euler's Theorem

Euler's theorem generalizes Fermat's little theorem: if $\gcd(a, n) = 1$ , then:

a^{\phi(n)} \equiv 1 \pmod{n}

This is the mathematical foundation that makes RSA decryption work: raising to the private exponent $d$ reverses the public encryption because $ed \equiv 1 \pmod{\phi(n)}$ .

Frequently Asked Questions

What does Euler's totient function calculate?

Euler's totient function $\phi(n)$ counts how many integers from 1 to $n$ are coprime to $n$ , meaning they share no common factor other than 1. For example, $\phi(12) = 4$ because the integers 1, 5, 7, and 11 are coprime to 12.

How do I compute phi(n) from the prime factorization?

Use the formula $\phi(n) = n \times \prod(1 - 1/p)$ where the product runs over all distinct prime factors $p$ of $n$ . For example, $\phi(60) = 60 \times (1 - 1/2)(1 - 1/3)(1 - 1/5) = 60 \times 1/2 \times 2/3 \times 4/5 = 16$ .

Why is the totient function important in RSA encryption?

RSA encryption relies on $\phi(n)$ where $n = p \times q$ for two large primes. The public and private keys satisfy $e \times d \equiv 1 \pmod{\phi(n)}$ . Security depends on the fact that computing $\phi(n)$ requires knowing $p$ and $q$ , and factoring large $n$ is computationally infeasible.

What is Euler's theorem?

Euler's theorem states that if $\gcd(a, n) = 1$ , then $a^{\phi(n)} \equiv 1 \pmod{n}$ . This generalizes Fermat's little theorem (where $n$ is prime). It is the mathematical foundation that makes RSA decryption work, because raising to the private exponent $d$ reverses the public encryption.

What is the totient of a prime number?

For any prime $p$ , $\phi(p) = p - 1$ , because every integer from 1 to $p - 1$ is coprime to a prime. More generally, for a prime power $p^k$ , $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$ .

Related purpose Variants

Explore more purpose options

prime-checker

Primality Tester | Is This Number Prime?

Use this calculator

divisor-calculator

Divisor Calculator | Count and List All Divisors

Use this calculator

More Math Calculators

Explore the category

Absolute Value Calculator

Area Calculator

Circle Calculator

Percentage Calculator

Pythagorean Theorem Calculator

Unit Circle Explorer