Calculating φ(n)...
Ready to calculate Euler's totient
Enter a positive integer to calculate φ(n), factor n, and reveal its coprime numbers.
What Is Euler's Totient Function?
An Euler's totient function calculator finds how many positive integers are coprime to a given positive integer n. The function is written φ(n), pronounced “phi of n.” Two numbers are coprime, or relatively prime, when their greatest common divisor is 1. They do not need to be prime individually: 8 and 15 are both composite, but gcd(8,15)=1.
For example, the positive integers from 1 through 10 that are coprime to 10 are 1, 3, 7, and 9. Therefore φ(10)=4. For every input above 1, the input itself is not counted because gcd(n,n)=n. The special conventional value is φ(1)=1, since gcd(1,1)=1.
From n to φ(n)
Input
n = 36
Start with the positive integer.
Factor
36 = 2² × 3²
Find the prime factorization.
Distinct primes
p = 2 and 3
Each distinct prime enters the product once.
Product formula
36 × (1 − 1/2) × (1 − 1/3)
Remove the share divisible by each prime.
Result
φ(36) = 12
Twelve integers are coprime to 36.
How to Calculate φ(n) from Prime Factors
Factor n, keep its distinct prime divisors, and apply Euler's product formula: φ(n) = n × ∏(1 − 1/p). If n=36=2²×3², the distinct primes are 2 and 3. Applying the formula gives 36×(1−1/2)×(1−1/3)=12. The exponent controls how large n is, but each distinct prime contributes one product factor.
For a prime p, every positive integer below p is coprime to it, so φ(p)=p−1. For a prime power, φ(p^k)=p^k−p^(k−1); the removed integers are precisely the multiples of p. The totient function is multiplicative: when gcd(a,b)=1, φ(ab)=φ(a)φ(b). That identity must not be applied without the coprime condition.
How the Coprime Grid Works
The result grid tests each integer k with the Euclidean algorithm. A cell is highlighted exactly when gcd(k,n)=1, so the number of highlighted cells must equal φ(n). The grid makes patterns visible: for n = 10, every even cell and every multiple of 5 is excluded, leaving 1, 3, 7, and 9.
Complete grids are limited to n ≤ 200 to keep the page readable and the HTML response small. Every result still shows the exact coprime density φ(n)/n. Density measures the proportion of residue classes represented by units modulo n; it is 40% for n = 10 and approaches different values depending on the distinct primes dividing n.
Euler's Totient Function and RSA
Euler's function appears in textbook descriptions of RSA. For a modulus formed from two primes, introductory key generation chooses a public exponent coprime to a totient-related value, then derives the private exponent with a modular inverse. The example 3233=53×61 has φ(3233)=52×60=3120.
This calculator is an educational number-theory tool, not cryptographic software. Production RSA involves standards, secure randomness, validated parameter generation, padding schemes, side-channel defenses, and vetted libraries. Do not use manually selected examples or calculator output to create real security keys.
Euler Totient Values Table
| n | Prime factorization | φ(n) | Coprimes in 1…n |
|---|---|---|---|
| 1 | No prime factors | 1 | 1 |
| 2 | 2 | 1 | 1 |
| 3 | 3 | 2 | 1, 2 |
| 4 | 2² | 2 | 1, 3 |
| 5 | 5 | 4 | 1, 2, 3, 4 |
| 6 | 2 × 3 | 2 | 1, 5 |
| 8 | 2³ | 4 | 1, 3, 5, 7 |
| 9 | 3² | 6 | 1, 2, 4, 5, 7, 8 |
| 10 | 2 × 5 | 4 | 1, 3, 7, 9 |
| 12 | 2² × 3 | 4 | 1, 5, 7, 11 |
Euler's Totient Calculator FAQ
What is Euler's totient function φ(n)?
Euler's totient function φ(n) counts the positive integers from 1 through n that are coprime to n. Two integers are coprime when their greatest common divisor is 1. For n above 1, this is the same as counting the qualifying positive integers below n.
How do you calculate φ(n) using prime factorization?
Factor n and keep its distinct prime divisors. Then apply φ(n) = n × ∏(1 − 1/p), using each distinct prime p once. Integer division can be applied before multiplication to keep every intermediate result exact.
Why is φ(p) equal to p − 1 for a prime number?
A prime p has no positive divisors except 1 and itself. Every integer from 1 through p−1 therefore has greatest common divisor 1 with p, giving exactly p−1 coprime integers.
What is φ(1)?
The conventional value is φ(1) = 1. The integer 1 is included because gcd(1, 1) = 1, even though 1 is not prime. This convention also keeps important number-theory identities consistent.
How is Euler's totient function used in RSA?
In textbook RSA key generation, a public exponent is selected to be coprime to a totient-related value and the private exponent is derived as a modular inverse. Real cryptographic systems should use vetted libraries and current standards rather than a teaching calculator. Modern specifications include additional details that a basic φ(n) example does not model.
What is the difference between prime and coprime numbers?
Prime describes one integer that has exactly two positive divisors. Coprime describes a relationship between two integers whose greatest common divisor is 1. Two composite integers, such as 8 and 15, can be coprime.
Related Calculators
Prime Factorization Calculator
Break an integer into prime powers with a visual factor tree.
GCF & LCM Calculator
Find greatest common divisors and least common multiples with steps.
Modular Arithmetic Calculator
Calculate residues, inverses, powers, and congruences.
Exponent Calculator
Evaluate powers, roots, and negative or fractional exponents.
Factorial Calculator
Compute n! with exact large-number output and multiplication steps.
Combination & Permutation Calculator
Calculate nCr and nPr with factorial breakdowns.