# Euler's totient function

**Euler's totient function**, written \( \varphi(n) \) or \( \phi(n) \), counts the positive integers up to \( n \) that are coprime to \( n \), that is, the integers \( k \) in \([1, n]\) with \( \gcd(k, n) = 1 \).<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup> It equals the number of elements of the multiplicative group of units modulo \( n \), the residues in \( \mathbb{Z}_n \) that have multiplicative inverses.<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup><sup> • </sup><sup>[2](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/02%3A_Congruences/2.05%3A_Euler%27s__%CF%95__Function)</sup> The function is central to [Euler's theorem](https://www.edgepedia.org/eulers-theorem) on modular exponentiation and to the [RSA cryptosystem](https://www.edgepedia.org/rsa-cryptosystem).

| Key fact | Detail |
|---|---|
| Definition | \( \varphi(n) = \#\{k \in [1,n] : \gcd(k,n)=1\} \), with \( \varphi(1) = 1 \)<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup> |
| Prime powers | \( \varphi(p) = p - 1 \) and \( \varphi(p^k) = p^k - p^{k-1} \)<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup> |
| Product formula | For \( n = p_1^{k_1} \cdots p_m^{k_m} \), \( \varphi(n) = n \prod_{i=1}^{m} (1 - 1/p_i) \)<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup> |
| Multiplicativity | \( \varphi(mn) = \varphi(m)\varphi(n) \) when \( \gcd(m,n)=1 \); it is multiplicative but not completely multiplicative<sup>[3](https://crypto.stanford.edu/pbc/notes/numbertheory/mult.html)</sup> |
| Divisor sum | \( \sum_{d \mid n} \varphi(d) = n \); for \( n = 12 \) the totients of 1, 2, 3, 4, 6, 12 are 1, 1, 2, 2, 2, 4, summing to 12<sup>[3](https://crypto.stanford.edu/pbc/notes/numbertheory/mult.html)</sup> |
| Computational status | Computing \( \varphi(n) \) without knowing the factorization of \( n \) is essentially as hard as factoring \( n \)<sup>[4](https://zoo.cs.yale.edu/classes/cs460/numthlect.pdf)</sup> |
| History | Defined by Euler in 1763; the \( \phi \) notation was introduced by Gauss in 1801; the word "totient" was used by Sylvester in 1879<sup>[5](https://old.maa.org/press/periodicals/convergence/math-origins-the-totient-function)</sup> |

## Definition and first examples

The function is defined on the positive integers by

\[ \varphi(n) = \#\{a \in [n] : \gcd(a, n) = 1\}. \]

For \( n > 1 \) this is the same as counting the integers in \([1, n-1]\) coprime to \( n \), since \( \gcd(n, n) = n > 1 \). Setting \( \varphi(1) = 1 \) is a convention that makes the function multiplicative.<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup><sup> • </sup><sup>[6](https://mileti.math.grinnell.edu/ComboNumber.pdf)</sup> The name comes from the English mathematician [James Joseph Sylvester](https://www.edgepedia.org/james-joseph-sylvester), who introduced the word "totient" in 1879, more than a century after Euler's original definition of 1763; Gauss had introduced the \( \phi \) notation in 1801.<sup>[5](https://old.maa.org/press/periodicals/convergence/math-origins-the-totient-function)</sup>

The group-theoretic reading explains the count: an element \( y \) of \( \mathbb{Z}_n \) is a unit, meaning it has a multiplicative inverse, exactly when \( y \) and \( n \) are coprime, so \( \varphi(n) \) is the size of the unit group \( \mathbb{Z}_n^* \).<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup> For example, \( \varphi(6) = 2 \) because only 1 and 5 in \([1..6]\) are coprime to 6, and \( \varphi(4) = 2 \) because 1 and 3 are the only elements of \([4]\) relatively prime to 4.<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup><sup> • </sup><sup>[6](https://mileti.math.grinnell.edu/ComboNumber.pdf)</sup>

## The product formula

Two special cases build the general formula. For a prime \( p \), every nonzero residue modulo \( p \) is a unit, so \( \varphi(p) = p - 1 \). For a prime power \( p^k \), the only residues not coprime to \( p^k \) are the multiples of \( p \), of which there are \( p^k / p = p^{k-1} \), giving \( \varphi(p^k) = p^k - p^{k-1} \).<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup>

**Multiplicativity.** If \( m \) and \( n \) are coprime, the Chinese Remainder Theorem identifies \( \mathbb{Z}_{mn}^* \) with the product \( \mathbb{Z}_m^* \times \mathbb{Z}_n^* \), so \( \varphi(mn) = \varphi(m)\varphi(n) \).<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup><sup> • </sup><sup>[2](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/02%3A_Congruences/2.05%3A_Euler%27s__%CF%95__Function)</sup> The function is therefore multiplicative in the standard sense, \( f(mn) = f(m)f(n) \) for coprime \( m, n \), but not completely multiplicative: the identity fails when \( m \) and \( n \) share a factor.<sup>[3](https://crypto.stanford.edu/pbc/notes/numbertheory/mult.html)</sup>

Combining the prime-power case with multiplicativity gives, for \( n = p_1^{k_1} \cdots p_m^{k_m} \),

\[ \varphi(n) = (p_1^{k_1} - p_1^{k_1-1}) \cdots (p_m^{k_m} - p_m^{k_m-1}) = n \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_m}\right). \]

The product runs over the distinct primes dividing \( n \), each contributing one factor \( (1 - 1/p) \) regardless of the exponent.<sup>[1](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)</sup><sup> • </sup><sup>[7](https://algorithms.alexli.ca/euler-s-totient-function/)</sup>

## Identities and related functions

Because \( \varphi \) is multiplicative, its divisor sum \( F(n) = \sum_{d \mid n} \varphi(d) \) is multiplicative as well, and in fact

\[ \sum_{d \mid n} \varphi(d) = n. \]

The divisors of 12 are 1, 2, 3, 4, 6, 12, and their totients 1, 1, 2, 2, 2, 4 sum to 12.<sup>[3](https://crypto.stanford.edu/pbc/notes/numbertheory/mult.html)</sup> This identity also follows from facts about cyclic groups.<sup>[3](https://crypto.stanford.edu/pbc/notes/numbertheory/mult.html)</sup>

The totient connects to other classical functions. It determines the degree of the \( n \)th cyclotomic polynomial: \( [\mathbb{Q}(\mu_n) : \mathbb{Q}] = \varphi(n) \), where \( \mu_n \) is the set of \( n \)th roots of unity.<sup>[8](https://math.ucla.edu/~sharifi/notes/algnum-ch03.html)</sup> When \( n \) has a primitive root, the number of primitive roots is \( \varphi(\varphi(n)) \).<sup>[9](https://zoo.cs.yale.edu/classes/cs467/2017f/attach/ho11.html)</sup>

## Euler's theorem and cryptography

Equivalently, the number of non-coprime residues is only \( n - \varphi(n) = p + q - 1 \) out of \( n \) total residues.<sup>[10](https://zoo.cs.yale.edu/classes/cs467/2008f/attach/ln10.html)</sup>

## Computation and complexity

With the factorization of \( n \) in hand, the product formula computes \( \varphi(n) \) directly; trial division factors \( n \) in \( O(\sqrt{n}) \) time, and Pollard's rho algorithm, with a heuristic running time around \( O(n^{1/4}) \), handles larger inputs in practice.<sup>[7](https://algorithms.alexli.ca/euler-s-totient-function/)</sup><sup> • </sup><sup>[11](https://codeforces.com/topic/107472/en16)</sup> A sieve of [Eratosthenes](https://www.edgepedia.org/eratosthenes) variant computes \( \varphi(k) \) for every \( k \le n \) at once by sweeping each prime across its multiples and folding in the factor \( (1 - 1/p) \).<sup>[7](https://algorithms.alexli.ca/euler-s-totient-function/)</sup>

Without the factorization, the problem is fundamentally different: computing \( \varphi(n) \) is essentially as hard as factoring \( n \).<sup>[4](https://zoo.cs.yale.edu/classes/cs460/numthlect.pdf)</sup> Formal work confirms the equivalence in both directions. Oracle queries for values of \( \varphi \) suffice to completely factor any integer \( n \) in deterministic polynomial time, and explicit sets of integers are completely factorable in deterministic polynomial time given \( \varphi(n) \).<sup>[12](https://doi.org/10.1090/S0025-5718-09-02262-5)</sup> Deterministic factoring algorithms also exist under the assumption that the prime power decomposition of \( \varphi(N) \) is known.<sup>[13](https://journals.sagepub.com/doi/pdf/10.3233/FI-2020-1891)</sup> Inverting the function is its own problem: given \( n \), finding all \( m \) with \( \varphi(m) = n \) can be done in polynomial time on average given the factorization of \( n \), and deciding whether \( \varphi(m) = n \) has a solution is linked to the [integer factorization](https://www.edgepedia.org/integer-factorization) problem.<sup>[14](https://researchers.mq.edu.au/en/publications/complexity-of-inverting-the-euler-function/)</sup>

## Distribution and asymptotics

The summatory totient function \( \Phi(x) = \sum_{n \le x} \varphi(n) \) grows like a parabola: \( \Phi(x) \sim \frac{3}{\pi^2} x^2 + O(x \log x) \), a constant that reflects the natural density \( 6/\pi^2 \) of coprime pairs. Walfisz improved the error term in 1963 to \( O(x (\log x)^{2/3} (\log \log x)^{4/3}) \).<sup>[15](https://mathworld.wolfram.com/TotientSummatoryFunction.html)</sup> The first values of the summatory function are 1, 2, 4, 6, 10, 12, 18, 22, 28.<sup>[15](https://mathworld.wolfram.com/TotientSummatoryFunction.html)</sup>

Current research continues on the function's fine structure: the distribution of \( \varphi(n) \) in residue classes modulo primes,<sup>[16](https://doi.org/10.1307/mmj/20216082)</sup> the distribution of \( \gcd(n, \varphi(n)) \),<sup>[17](https://www.impan.pl/en/publishing-house/journals-and-series/acta-arithmetica/all/en/publishing-house/journals-and-series/acta-arithmetica/all/219/2/115958/the-distribution-of-mathrm-gcd-n-varphi-n)</sup> and improved upper bounds for the distribution of iterated totients \( \varphi_k(n) \).<sup>[18](https://arxiv.org/abs/2506.23882)</sup>

## History

Euler introduced the function in the paper *Theoremata arithmetica nova methodo demonstrata*, read to the Berlin Academy in 1758 and published in 1763 in the *Novi Commentarii academiae scientiarum Petropolitanae*, volume 8, pages 74 to 104. In it Euler gave a third proof of Fermat's theorem, the proof now called the Euler–Fermat theorem, and proved that, for gcd(\( x \),\( N \))=1, the smallest positive exponent k satisfying \( x \)^k ≡ 1 (mod \( N \)) divides φ(\( N \)), the number of integers in [1,\( N \)] coprime to \( N \).<sup>[19](https://scholarlycommons.pacific.edu/euler-works/271/)</sup> The \( \phi \) notation came from Gauss's *Disquisitiones Arithmeticae* in 1801, and Sylvester's word "totient" appeared in 1879, 116 years after Euler's definition.<sup>[5](https://old.maa.org/press/periodicals/convergence/math-origins-the-totient-function)</sup>

## References

1. [Units and the Totient Function, Stanford Number Theory notes (P. B. Cohen)](https://crypto.stanford.edu/pbc/notes/numbertheory/units.html)
2. [Euler's ϕ Function, Yet Another Introductory Number Theory Textbook (Poritz), LibreTexts](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/02%3A_Congruences/2.05%3A_Euler%27s__%CF%95__Function)
3. [Multiplicative Functions, Stanford Number Theory notes](https://crypto.stanford.edu/pbc/notes/numbertheory/mult.html)
4. [Algorithms for integers, polynomials (T. Theobald), Yale lecture notes](https://zoo.cs.yale.edu/classes/cs460/numthlect.pdf)
5. [Math Origins: The Totient Function, Mathematical Association of America](https://old.maa.org/press/periodicals/convergence/math-origins-the-totient-function)
6. [Combinatorics and Number Theory (Mileti), Grinnell College](https://mileti.math.grinnell.edu/ComboNumber.pdf)
7. [Euler's Totient Function, Algorithms notes (A. Li)](https://algorithms.alexli.ca/euler-s-totient-function/)
8. [Algebraic Number Theory, Chapter 3 (R. Sharifi), UCLA](https://math.ucla.edu/~sharifi/notes/algnum-ch03.html)
9. [Euler function, Yale CS 467 handout](https://zoo.cs.yale.edu/classes/cs467/2017f/attach/ho11.html)
10. [Yale CS 467 lecture notes on the totient function and RSA](https://zoo.cs.yale.edu/classes/cs467/2008f/attach/ln10.html)
11. [Euler's phi function tutorial, Codeforces](https://codeforces.com/topic/107472/en16)
12. [B. Źrałek, "Reductions of factoring to computing Euler's totient function," Math. Comp. 79 (2010), 513–533](https://doi.org/10.1090/S0025-5718-09-02262-5)
13. [M. Hittmeir, J. Pomykała, "Deterministic Integer Factorization with Oracles for Euler's Totient Function," Fundamenta Informaticae (2020)](https://journals.sagepub.com/doi/pdf/10.3233/FI-2020-1891)
14. [Complexity of inverting the Euler function, Macquarie University](https://researchers.mq.edu.au/en/publications/complexity-of-inverting-the-euler-function/)
15. [Totient Summatory Function, Wolfram MathWorld](https://mathworld.wolfram.com/TotientSummatoryFunction.html)
16. [N. Lebowitz-Lockard, P. Pollack, A. Singha Roy, "Distribution mod p of Euler's Totient and the Sum of Proper Divisors," Michigan Mathematical Journal (2024)](https://doi.org/10.1307/mmj/20216082)
17. [J. Stucky, "The distribution of gcd(n, φ(n))," Acta Arithmetica 219 (2025), 169–197](https://www.impan.pl/en/publishing-house/journals-and-series/acta-arithmetica/all/en/publishing-house/journals-and-series/acta-arithmetica/all/219/2/115958/the-distribution-of-mathrm-gcd-n-varphi-n)
18. [P. Gao, Q. Yang, "An improved upper bound for the distribution of iterated Euler totient functions," arXiv:2506.23882](https://arxiv.org/abs/2506.23882)
19. [L. Euler, "Theoremata arithmetica nova methodo demonstrata" (E271), Euler Archive, University of the Pacific](https://scholarlycommons.pacific.edu/euler-works/271/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Arithmetic functions*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Sep 19, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 19, 2026; Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license