Euler Totient Calculator

Use this Euler Totient Calculator to enter values, adjust options, and review results in a compact responsive workspace.

Results are calculated automatically as you enter data.

Integer n Explore n from 1 to 200

The first screen focuses on phi(n), the factor formula, and a preview of residues that are coprime to n.

Formula, residues, and Euler theorem

Result phi(n) appears here.

Disclaimer: All tools on this site are intended for educational and informational purposes only. Not professional advice. No guarantee of accuracy; verify units, formulas, assumptions, tolerances, rounding, and limitations before important use. See our Terms of Use.

Assumptions and limitations

Results are educational estimates, not professional engineering, construction, safety, scientific, legal, financial, or academic advice. No guarantee is made that outputs are accurate, complete, suitable, or error-free. Verify units, formulas, assumptions, tolerances, rounding, and limitations independently, and use qualified professional review for technical or safety-sensitive work. This Euler Totient Calculator is for educational number-theory exploration only. It is not a cryptographic tool, key generator, or security validator. Do not use results for real security parameters, official records, or high-stakes decisions without qualified review. Use of this calculator is subject to our Terms of Use.

▼ See explanations and tips below ▼

Related Calculators

What Is Euler’s Totient Function?

Euler’s totient function, written as $\varphi(n)$, counts how many integers are coprime to a positive integer $n$. Two integers are coprime when their greatest common divisor is $1$.

For example, the positive integers up to $12$ that are coprime to $12$ are:

$$ 1,\ 5,\ 7,\ 11 $$

Each of these has no common factor with $12$ except $1$, so:

$$ \varphi(12)=4 $$

The totient function is useful because it connects prime factorization, modular arithmetic, reduced residues, Euler’s theorem, and RSA-style arithmetic. Instead of asking only “what divides $n$?”, it asks “how many residues remain usable when numbers that share factors with $n$ are removed?”

A common definition is:

$$ \varphi(n)=\#\left\{a:1\le a\le n,\ \gcd(a,n)=1\right\} $$

In words: $\varphi(n)$ is the number of integers from $1$ through $n$ whose greatest common divisor with $n$ is $1$. For $n>1$, this is the same as counting the reduced residues from $1$ through $n-1$.

Why Euler’s Totient Function Matters

Euler’s totient function matters because it turns a counting problem into a structure problem. At first, $\varphi(n)$ looks like something you would find by checking every number from $1$ to $n$. But once you know the prime factorization of $n$, you can compute $\varphi(n)$ directly.

That is important in number theory because many modular arithmetic results depend on coprime residues. For example, Euler’s theorem says that if $a$ is coprime to $n$, then:

$$ a^{\varphi(n)}\equiv 1 \pmod{n} $$

This theorem generalizes Fermat’s little theorem from prime moduli to many composite moduli. The same family of ideas also appears in introductory explanations of RSA-style arithmetic, where a modulus is often written as a product of two distinct primes.

Key Terms to Know

Integer: A whole number, such as $1$, $8$, $33$, or $1000000$.
Positive integer: An integer greater than $0$.
Greatest common divisor: The largest positive integer that divides two numbers. It is often written as $\gcd(a,b)$.
Coprime integers: Two integers whose greatest common divisor is $1$.
Prime number: An integer greater than $1$ whose only positive divisors are $1$ and itself.
Composite number: An integer greater than $1$ that is not prime.
Prime factorization: Writing a number as a product of prime powers, such as $72=2^3\cdot 3^2$.
Reduced residue: A residue modulo $n$ that is coprime to $n$.
Reduced residue system: A complete set of incongruent reduced residues modulo $n$.
Modular arithmetic: Arithmetic based on remainders after division by a modulus.

How Euler’s Totient Function Works

The direct way to find $\varphi(n)$ is to test each number from $1$ to $n$ and count the values that have greatest common divisor $1$ with $n$. That method is easy to understand, but it is not the most efficient way to compute the function.

The faster method uses the distinct prime factors of $n$. If $p$ runs over the distinct prime numbers that divide $n$, then:

$$ \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right) $$

Where:

$n$ is the positive integer being evaluated.
$p\mid n$ means that $p$ is a prime divisor of $n$.
The product uses each distinct prime factor once, even if that prime appears with an exponent.

This formula works because every prime factor of $n$ removes a predictable fraction of the residues. If $2$ divides $n$, then multiples of $2$ are not coprime to $n$. If $3$ also divides $n$, then multiples of $3$ are also excluded. The product formula combines these exclusions in a way that avoids double-counting.

If the prime factorization is:

$$ n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r} $$

then the totient can also be written as:

$$ \varphi(n)=\prod_{i=1}^{r}p_i^{e_i-1}(p_i-1) $$

Both forms give the same result. The product form with $n\prod(1-1/p)$ is often the easiest to apply once the distinct prime factors are known.

Examples of Euler’s Totient Function in Practice

Example 1: Counting the Coprime Values for $12$

Start with the numbers from $1$ through $12$:

$$ 1,2,3,4,5,6,7,8,9,10,11,12 $$

Keep only the numbers whose greatest common divisor with $12$ is $1$:

$$ 1,5,7,11 $$

There are $4$ such numbers, so:

$$ \varphi(12)=4 $$

Now check the same value with the prime factorization formula. Since:

$$ 12=2^2\cdot 3 $$

we use the distinct prime factors $2$ and $3$:

$$ \varphi(12)=12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) $$

$$ \varphi(12)=12\cdot\frac{1}{2}\cdot\frac{2}{3}=4 $$

Example 2: A Prime Number

If $n$ is prime, every positive integer less than $n$ is coprime to $n$. For $n=13$, the coprime values are:

$$ 1,2,3,4,5,6,7,8,9,10,11,12 $$

There are $12$ values, so:

$$ \varphi(13)=12 $$

For any prime $p$:

$$ \varphi(p)=p-1 $$

This is why prime values sit on the line $\varphi(n)=n-1$ in a totient trend graph.

Example 3: A Prime Power

For $n=8$, the prime factorization is:

$$ 8=2^3 $$

Using the product formula:

$$ \varphi(8)=8\left(1-\frac{1}{2}\right)=4 $$

The reduced residues are:

$$ 1,3,5,7 $$

Even though $8$ has only one distinct prime factor, that prime factor still removes all even residues.

Example 4: A Semiprime and the RSA-Style Shortcut

A semiprime is a product of two primes. If $n$ is the product of two distinct primes $p$ and $q$, then:

$$ n=pq $$

and the totient becomes:

$$ \varphi(n)=\varphi(pq)=(p-1)(q-1) $$

For example, let:

$$ n=33=3\cdot 11 $$

Then:

$$ \varphi(33)=(3-1)(11-1)=2\cdot 10=20 $$

This shortcut works for products of two distinct primes. It should not be used unchanged when $n$ is not of the form $pq$ with distinct prime factors.

Example 5: The Special Case $n=1$

The value $\varphi(1)$ is conventionally taken to be:

$$ \varphi(1)=1 $$

This case is special because there are no positive integers less than $1$. In modular arithmetic, modulo $1$ also behaves differently from ordinary moduli because every integer is congruent to $0$ modulo $1$. For calculator results, treat $n=1$ as a special convention rather than as a typical counting example.

How to Interpret the Result

The main result $\varphi(n)$ is a count. It tells you how many residues are coprime to $n$.

A larger value of $\varphi(n)$ means that more residues remain usable modulo $n$. A smaller value means that more residues share factors with $n$ and are excluded from the reduced residue system.

For a prime $n$, the result is as large as possible for $n>1$:

$$ \varphi(n)=n-1 $$

For a composite $n>1$, the result is lower because at least some values share a nontrivial factor with $n$.

Result item	What it means
$\varphi(n)$	The number of residues coprime to $n$
Prime factorization	The prime powers used to compute the totient
Coprime count	Another way to describe the same total counted by $\varphi(n)$
Reduced residues	Values that are coprime to $n$, shown as a preview when the list is long
Product formula	The substitution of the prime factors into the totient formula
Badges	Number-type labels, such as prime, prime power, square-free, or composite
Trend graph	A visual comparison of $\varphi(n)$ values across nearby integers
Euler theorem example	A modular exponentiation example using one automatically selected coprime base
RSA connection	A helper for the semiprime formula when the factorization has exactly two distinct prime factors

The reduced-residue preview is especially useful for small $n$, where the full list is easy to inspect. For larger values, the preview may show only the first part of the reduced residue system, so the chips shown on screen may not be the complete list.

The trend graph helps explain the shape of the totient function. Prime numbers appear on the upper envelope $\varphi(n)=n-1$. Composite numbers usually appear below that line because at least one nontrivial factor removes additional residues from the count.

Common Mistakes and Misconceptions

A common mistake is confusing $\varphi(n)$ with the number of divisors of $n$. These are different questions. The totient function counts numbers that are coprime to $n$; the divisor-counting function counts numbers that divide $n$.

For example, $12$ has $6$ positive divisors:

$$ 1,2,3,4,6,12 $$

But $\varphi(12)=4$ because only:

$$ 1,5,7,11 $$

are coprime to $12$.

Another mistake is applying the RSA-style shortcut too broadly. The formula:

$$ \varphi(pq)=(p-1)(q-1) $$

is for two distinct primes $p$ and $q$. It is not the right shortcut for a prime power such as $p^2$, and it is not the right shortcut for a number with three or more distinct prime factors.

Users also sometimes expect the reduced-residue preview to list every residue. For large values of $\varphi(n)$, the preview may be capped, so it should be read as a sample of the reduced residues rather than as a full list.

It is also easy to forget that the input must be a positive integer. Zero, negative numbers, decimals, blank entries, and non-numeric input do not fit the definition used here.

Finally, the Euler theorem card should be read as an example, not as a complete proof for every base. Euler’s theorem applies when the base is coprime to $n$, but the calculator chooses one small coprime base automatically rather than letting the user test every possible base.

When to Use Euler’s Totient Function

Use Euler’s totient function when you need to understand how many residues are coprime to a modulus.

Common uses include:

Studying modular arithmetic.
Finding the size of a reduced residue system modulo $n$.
Applying Euler’s theorem.
Comparing prime and composite behavior in number theory.
Working through introductory RSA-style examples with semiprime moduli.
Understanding how prime factorization affects arithmetic modulo $n$.

The function is especially helpful when a problem involves the phrase “relatively prime to $n$” or “invertible modulo $n$.”

Limitations and Things to Keep in Mind

The main mathematical result is exact for accepted inputs. It is an integer count, not an estimate or a rounded decimal.

The calculator accepts plain decimal-digit positive integers up to $1,000,000$. Values above that limit are not accepted so the calculation can remain responsive. Decimals, signs, and scientific notation are invalid rather than being converted into a nearby integer.

The trend slider uses integer values and is limited to a graph range from $20$ to $200$. Moving the slider also selects the corresponding value of $n$, so it changes the calculation rather than only changing the graph display.

The reduced-residue list is a preview when the list is long. If more than $80$ residues are available, only the first part is displayed.

The highly composite badge is checked only for values up to $1,000$. For larger accepted inputs, the result explicitly says that this classification was not evaluated.

The RSA connection card is educational. It shows the direct semiprime formula only when $n$ has exactly two distinct prime factors. This calculator is not a cryptographic key generator and should not be used to create real security parameters.

The Euler theorem example uses one automatically chosen coprime base. It is useful for seeing the theorem in action, but it is not a user-selected modular exponentiation tool.

How to Use This Calculator

Enter a positive integer $n$.
Optionally use the trend slider or click a graph point to select a supported graph value.
Read the main $\varphi(n)$ result.
Review the prime factorization and product formula to see how the result was computed.
Check the coprime count, reduced-residue preview, and number-type badges.
Use the trend graph to compare $\varphi(n)$ with nearby values.
Review the Euler theorem and RSA connection cards as interpretation aids.
Download the graph as a PNG if you need a visual copy.

Frequently Asked Questions

What does $\varphi(n)$ count?

$\varphi(n)$ counts how many integers from $1$ through $n$ are coprime to $n$. For $n>1$, this is the same as counting the residues from $1$ through $n-1$ that have greatest common divisor $1$ with $n$.

Why is $\varphi(p)=p-1$ when $p$ is prime?

If $p$ is prime, none of the integers $1,2,\ldots,p-1$ is divisible by $p$. Each of them is therefore coprime to $p$, so there are $p-1$ coprime values.

Why does prime factorization help compute the totient?

Prime factors tell you exactly which residues must be excluded because they share a factor with $n$. The product formula uses each distinct prime factor to remove the correct fraction of non-coprime residues.

Is $\varphi(n)$ the same as the number of divisors of $n$?

No. $\varphi(n)$ counts values that are coprime to $n$, while the divisor count measures how many positive integers divide $n$. For example, $12$ has $6$ positive divisors, but $\varphi(12)=4$.

What is a reduced residue system?

A reduced residue system modulo $n$ is a complete set of residues that are coprime to $n$, with no two values representing the same residue class modulo $n$. Its size is $\varphi(n)$.

How does Euler’s theorem use $\varphi(n)$?

Euler’s theorem says that if $a$ is coprime to $n$, then:

$$ a^{\varphi(n)}\equiv 1\pmod{n} $$

This means the totient gives an exponent that returns a coprime base to $1$ modulo $n$.

Why does the calculator reject decimals, zero, and negative numbers?

Euler’s totient function in this context is defined for positive integers. Decimals, zero, and negative values do not match that input domain, so they are not accepted.

Why is the residue list sometimes incomplete?

For large values, the number of reduced residues can be long. The calculator previews the first residues and indicates when it is not showing the complete list.

When can I use $\varphi(pq)=(p-1)(q-1)$?

Use this shortcut when $p$ and $q$ are distinct primes and $n=pq$. For other factorizations, use the general product formula instead.

Sources and References

Books and Textbooks

William Stein. Elementary Number Theory: Primes, Congruences, and Secrets. January 23, 2017 version. Relevant sections used: Chapter 1, Section 1.1 on prime factorization; Chapter 2, Section 2.1.2 on Euler’s theorem and Euler’s $\varphi$-function; Chapter 2, Section 2.2.1 on multiplicativity and computing $\varphi(n)$ from prime powers. https://wstein.org/ent/ent.pdf
Jonathan A. Poritz. Yet Another Introductory Number Theory Textbook – Cryptology Emphasis. Mathematics LibreTexts, “2.5: Euler’s $\phi$ Function,” last updated July 18, 2021. Relevant material used: definition of Euler’s totient function, invertible residues modulo $n$, and multiplicativity for relatively prime inputs. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_(Poritz)/02%3A_Congruences/2.05%3A_Euler's__%CF%95__Function

Academic and Primary Sources

R. L. Rivest, A. Shamir, and L. Adleman. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM, 21(2), 1978. Relevant material used: the RSA-style use of a modulus $n=pq$, modular exponentiation, and the relationship with $(p-1)(q-1)$. https://people.csail.mit.edu/rivest/Rsapaper.pdf