Euler's Totient Function Calculator

Compute φ(n) — count coprime integers, prime factorization, Euler's product formula & RSA connection

Enter n (positive integer, up to 10,000,000)

Quick Examples

What is Euler's Totient Function φ(n)?

Euler's totient function, written φ(n) or phi(n), is one of the most important functions in number theory. For a positive integer n, φ(n) counts how many integers from 1 to n are coprime with n — that is, how many k satisfy gcd(k, n) = 1. The function was introduced by Leonhard Euler in 1763 as part of his work on modular arithmetic.

For example, φ(12) = 4 because only the numbers 1, 5, 7, and 11 (from 1 to 12) share no common factor with 12. Numbers like 2, 3, 4, 6, 8, 9, 10, and 12 all share a factor with 12 = 2² × 3.

Euler's Product Formula

The most efficient way to compute φ(n) is via the Euler product formula. First, find the prime factorization of n:

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Then apply:

φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × ... × (1 − 1/pₖ)

For n = 60 = 2² × 3 × 5: φ(60) = 60 × (1 − 1/2) × (1 − 1/3) × (1 − 1/5) = 60 × 1/2 × 2/3 × 4/5 = 16. This formula works because the totient is a multiplicative function — if gcd(a, b) = 1, then φ(ab) = φ(a) × φ(b).

Key Properties

φ(1) = 1 — 1 is the only number coprime with itself in the range [1, 1].
φ(p) = p − 1 for any prime p — all integers 1 through p−1 are coprime with p.
φ(p^k) = p^(k-1) × (p − 1) for prime powers.
Multiplicative: φ(mn) = φ(m) × φ(n) when gcd(m, n) = 1.
Summatory property: The sum of φ(d) over all divisors d of n equals n.
φ(n) is always even for n > 2 (because coprime pairs {k, n−k} come in pairs).

Euler's Theorem

Euler's theorem is the cornerstone of modular arithmetic: if gcd(a, n) = 1, then:

a^φ(n) ≡ 1 (mod n)

This generalises Fermat's Little Theorem (when n is prime, φ(n) = n − 1, so a^(n−1) ≡ 1 mod n). Euler's theorem is used to compute modular inverses and perform fast modular exponentiation in cryptography.

RSA Cryptography Connection

RSA, the most widely deployed public-key cryptosystem, is built directly on Euler's totient function. The setup:

Choose two large primes p and q.
Set n = p × q (the RSA modulus). This is a semiprime.
Compute φ(n) = (p − 1)(q − 1).
Choose encryption exponent e with gcd(e, φ(n)) = 1.
Compute decryption exponent d such that e × d ≡ 1 (mod φ(n)).

Security rests on the hardness of factoring n — an attacker who cannot factor n cannot compute φ(n) and hence cannot find d. For a typical RSA-2048 key, n is a 2048-bit semiprime and φ(n) ≈ n.

φ(n) Reference Table: n = 1 to 30

n	φ(n)	Prime Factors	Coprime Ratio	n	φ(n)	Prime Factors	Coprime Ratio
1	1	—	100%	16	8	2	50%
2	1	2	50%	17	16	17	94.1%
3	2	3	66.7%	18	6	2, 3	33.3%
4	2	2	50%	19	18	19	94.7%
5	4	5	80%	20	8	2, 5	40%
6	2	2, 3	33.3%	21	12	3, 7	57.1%
7	6	7	85.7%	22	10	2, 11	45.5%
8	4	2	50%	23	22	23	95.7%
9	6	3	66.7%	24	8	2, 3	33.3%
10	4	2, 5	40%	25	20	5	80%
11	10	11	90.9%	26	12	2, 13	46.2%
12	4	2, 3	33.3%	27	18	3	66.7%
13	12	13	92.3%	28	12	2, 7	42.9%
14	6	2, 7	42.9%	29	28	29	96.6%
15	8	3, 5	53.3%	30	8	2, 3, 5	26.7%

Frequently Asked Questions

What is Euler's totient function φ(n)?

Euler's totient function φ(n) counts how many positive integers up to n are coprime with n — integers k with gcd(k, n) = 1. For example, φ(12) = 4 because only 1, 5, 7, and 11 are coprime with 12. The function was introduced by Leonhard Euler in 1763 and is fundamental in number theory and cryptography.

How do you compute φ(n) using prime factorization?

Factorize n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ, then apply Euler's product formula: φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × ... × (1 − 1/pₖ). For n = 12 = 2² × 3: φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4. The formula works because the totient is a multiplicative function.

What is φ(p) when p is prime?

When p is prime, φ(p) = p − 1. This is because all integers from 1 to p−1 are coprime with p. For example, φ(7) = 6, φ(13) = 12, φ(97) = 96. Conversely, if φ(n) = n − 1, then n must be prime. This is the basis for Fermat's Little Theorem: a^(p−1) ≡ 1 (mod p) for gcd(a, p) = 1.

How is Euler's totient function used in RSA cryptography?

In RSA, you choose two large primes p and q, set n = p × q, and compute φ(n) = (p−1)(q−1). This is used to find encryption exponent e (coprime to φ(n)) and decryption exponent d with e × d ≡ 1 (mod φ(n)). Security relies on the difficulty of factoring n — without knowing p and q, an attacker cannot compute φ(n) or d.

What is Euler's theorem and how does it relate to φ(n)?

Euler's theorem states: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This generalises Fermat's Little Theorem (the special case when n is prime). Euler's theorem underpins RSA decryption and modular exponentiation — it guarantees that encrypting and then decrypting a message with the correct exponents returns the original.

What are coprime numbers?

Two integers a and b are coprime (or relatively prime) if gcd(a, b) = 1 — they share no common prime factor. For example, 8 = 2³ and 15 = 3 × 5 are coprime. Euler's totient φ(n) counts exactly how many integers from 1 to n are coprime with n. Note that being coprime does not require either number to be prime.

What is the value of φ(1)?

φ(1) = 1. By convention, gcd(1, 1) = 1, so 1 is coprime with itself. It is the only integer in [1, 1] that is coprime with 1, hence φ(1) = 1. This is the unique case where φ(n) = 1, since for all n > 1 both 1 and n−1 are coprime with n (when n > 2), giving φ(n) ≥ 2.