—
—
—
%
—
0
—
—
—
—
%
—
0
—
The Euler's Totient Calculator computes $$\varphi(n)$$, the count of positive integers up to $$n$$ that are relatively prime to $$n$$. Euler's totient function is one of the most important arithmetic functions in number theory, connecting prime factorization to the structure of modular arithmetic.
Leonhard Euler introduced this function in 1763, though the notation $$\varphi(n)$$ was standardized later by Gauss. The totient function arises naturally from the structure of the multiplicative group of integers modulo $$n$$, denoted $$(\mathbb{Z}/n\mathbb{Z})^\times$$. This group consists of exactly the residue classes coprime to $$n$$, and its order is $$\varphi(n)$$.
The computation relies on the prime factorization formula. If $$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$, then:
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = n \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdots \frac{p_k - 1}{p_k}$$
This formula encodes the inclusion-exclusion principle: start with $$n$$ integers, subtract those divisible by each prime factor, add back those divisible by pairs of prime factors, and so on.
Key properties include multiplicativity: $$\varphi(mn) = \varphi(m)\varphi(n)$$ when $$\gcd(m,n) = 1$$. For a prime $$p$$, $$\varphi(p) = p - 1$$ since every number from 1 to $$p-1$$ is coprime to $$p$$. For prime powers, $$\varphi(p^k) = p^{k-1}(p-1)$$. The Gauss identity states $$\sum_{d \mid n} \varphi(d) = n$$ — the totient values of all divisors of $$n$$ sum to $$n$$ itself.
Euler's theorem, the crown jewel application, states: if $$\gcd(a, n) = 1$$, then $$a^{\varphi(n)} \equiv 1 \pmod{n}$$. This generalizes Fermat's Little Theorem and is the mathematical foundation of RSA encryption, where the public and private keys are constructed so that encryption followed by decryption raises the message to the power $$\varphi(n) + 1$$, recovering the original message.
This calculator determines the prime factors of $$n$$ (checking small primes up to 13, plus any remaining prime factor) and applies the product formula to compute $$\varphi(n)$$ exactly.
The calculator computes Euler's totient using the prime factorization product formula.
Step 1: Find prime factors. Trial division by primes 2, 3, 5, 7, 11, 13. For each prime $$p$$ that divides $$n$$, divide out all powers of $$p$$. Any remaining factor greater than 1 is itself prime.
Step 2: Apply the product formula. Starting with $$\varphi = n$$, for each prime factor $$p$$:
$$\varphi \leftarrow \varphi \cdot \left(1 - \frac{1}{p}\right) = \varphi - \frac{\varphi}{p}$$
Step 3: Compute auxiliary values.
The totient ratio $$\varphi(n)/n = \prod(1 - 1/p)$$ measures the "density" of coprime residues. For primes, this ratio is $$(p-1)/p$$, approaching 1. For highly composite numbers with many small prime factors, the ratio is small.
Primality check: If $$\varphi(n) = n - 1$$ and $$n > 1$$, then $$n$$ must be prime, because only primes have the property that every smaller positive integer is coprime to them.
φ(n) is the count of integers in $$\{1, 2, \ldots, n\}$$ that share no common factor with $$n$$ other than 1. For example, $$\varphi(12) = 4$$ because exactly four numbers (1, 5, 7, 11) are coprime to 12.
Totient Ratio φ(n)/n represents the probability that a randomly chosen integer from 1 to n is coprime to n. Numbers with many distinct small prime factors have lower ratios — the primorial $$2 \times 3 \times 5 \times 7 = 210$$ has ratio $$\approx 0.229$$.
Prime Factors Used lists the distinct prime divisors found. The totient depends only on the set of prime factors, not their multiplicities — $$\varphi(12) = 12(1-1/2)(1-1/3) = 4$$, and the same formula applies whether $$n = 12 = 2^2 \cdot 3$$ or $$n = 6 = 2 \cdot 3$$.
Is n Prime? — since $$\varphi(p) = p - 1$$ if and only if $$p$$ is prime, the totient provides a primality test.
Inputs
Results
12 = 2² × 3. φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4. The four integers coprime to 12 are {1, 5, 7, 11}.
Inputs
Results
17 is prime, so φ(17) = 16. Every integer from 1 to 16 is coprime to 17. The totient ratio 16/17 ≈ 0.941 is close to 1, characteristic of primes.
The totient function is central to RSA cryptography, where key generation requires computing $$\varphi(n) = (p-1)(q-1)$$ for $$n = pq$$. It also appears in group theory (order of multiplicative groups), number theory (Euler's theorem, primitive roots), and combinatorics (counting reduced fractions, necklace problems, cyclotomic polynomials).
Fermat's Little Theorem states $$a^{p-1} \equiv 1 \pmod{p}$$ for prime $$p$$ with $$\gcd(a,p) = 1$$. Since $$\varphi(p) = p-1$$, Euler's theorem $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ is a direct generalization. Fermat's theorem is the special case where $$n$$ is prime.
The product formula $$\varphi(n) = n \prod(1 - 1/p)$$ arises from inclusion-exclusion on divisibility. Whether a number is divisible by $$p$$ depends only on whether $$p$$ is a factor of $$n$$, not on the exponent of $$p$$ in the factorization. The factor $$n$$ in front already accounts for the prime power contributions.
$$\varphi(1) = 1$$ and $$\varphi(2) = 1$$. For $$n > 2$$, $$\varphi(n)$$ is always even. Not every even number is a totient value — for example, 14 is not $$\varphi(n)$$ for any $$n$$. The totient valence function counts how many $$n$$ share a given totient value. Carmichael's conjecture (still unproven) asserts that no totient value is taken exactly once.
This calculator checks prime factors up to 13 by trial division, then treats any remaining quotient as a single prime factor. This gives exact results for all $$n$$ whose prime factors are at most 13, and for all $$n$$ that are products of at most one prime factor greater than 13. For very large numbers with multiple large prime factors, the factorization step may be incomplete.
Gauss proved that $$\sum_{d \mid n} \varphi(d) = n$$. For example, for $$n = 12$$, the divisors are 1, 2, 3, 4, 6, 12, and $$\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$$. This identity has an elegant combinatorial proof: partition $$\{1, \ldots, n\}$$ by the value of $$\gcd(k, n)$$.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
