Euler's Totient Function and Euler's Theorem

⚡ Key Takeaways

Euler's totient function $\varphi(n)$ counts the positive integers up to $n$ that are coprime to $n$ . Euler's theorem states that if $\gcd(a,n)=1$ , then $a^{\varphi(n)}\equiv 1 \pmod n$ . These tools underpin modular arithmetic, cyclic group structure, and the RSA cryptosystem. Introduced by Leonhard Euler in 1763.

💡 The Core Insight

The integers coprime to $n$ form a group under multiplication modulo $n$ — the unit group $(\mathbb{Z}/n\mathbb{Z})^\times$ — and that group has exactly $\varphi(n)$ elements. By Lagrange's theorem, every element raised to the size of the group returns to the identity. That single structural fact, applied to a finite abelian group of units, is Euler's theorem.

DefinitionEuler's Totient Function

For a positive integer $n$ , the totient $\varphi(n)$ is the number of integers $k$ in the range $1\le k\le n$ satisfying $\gcd(k,n)=1$ :

1

\quad \varphi(n) = \#\{\,k\in\mathbb{Z} : 1\le k\le n,\ \gcd(k,n)=1\,\}

Derivation hint: Directly count the residues modulo $n$ that have a multiplicative inverse; by convention $\varphi(1)=1$ since $\gcd(1,1)=1$ . Symbols: $n$ is the modulus; $k$ ranges over representatives of residue classes; $\gcd$ is the greatest common divisor. Equivalently, $\varphi(n)=|(\mathbb{Z}/n\mathbb{Z})^\times|$ , the order of the group of units.

DefinitionProduct Formula

If $n = p_1^{a_1} p_2^{a_2}\cdots p_r^{a_r}$ is the prime factorization of $n>1$ , then

2

\quad \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right) = \prod_{i=1}^{r} p_i^{a_i-1}(p_i-1)

Derivation hint: Compute $\varphi(p^a)=p^a-p^{a-1}$ for prime powers, then multiply across distinct primes using multiplicativity (Theorem below). Symbols: the product $\prod_{p\mid n}$ runs over distinct prime divisors $p$ of $n$ ; each factor $(1-1/p)$ removes the fraction of integers divisible by $p$ .

TheoremMultiplicativity

If $\gcd(m,n)=1$ , then

3

\quad \varphi(mn) = \varphi(m)\,\varphi(n).

Derivation hint: The Chinese Remainder Theorem gives a ring isomorphism $\mathbb{Z}/mn\mathbb{Z}\cong \mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ , which restricts to a bijection of unit groups, so unit counts multiply. Note: $\varphi$ is multiplicative but not completely multiplicative; e.g. $\varphi(4)=2\ne\varphi(2)^2=1$ .

TheoremEuler's Theorem

If $a$ and $n$ are integers with $n\ge 1$ and $\gcd(a,n)=1$ , then

4

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

Derivation hint: $a$ represents a unit in $(\mathbb{Z}/n\mathbb{Z})^\times$ , a finite group of order $\varphi(n)$ ; apply Lagrange's theorem, whose corollary forces $g^{|G|}=e$ for all $g\in G$ . When $n=p$ is prime, $\varphi(p)=p-1$ and [4] becomes Fermat's little theorem: $a^{p-1}\equiv 1\pmod p$ for $p\nmid a$ .

TheoremDivisor-Sum Identity (Gauss)

For every positive integer $n$ ,

5

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

Derivation hint: Partition the $n$ fractions $1/n,2/n,\dots,n/n$ by their reduced denominator $d\mid n$ ; exactly $\varphi(d)$ of them reduce to a fraction with denominator $d$ .

ProofEuler's Theorem via Group Theory

Step 1. Let $G = (\mathbb{Z}/n\mathbb{Z})^\times$ , the set of residue classes coprime to $n$ . Closure holds: if $\gcd(a,n)=\gcd(b,n)=1$ then $\gcd(ab,n)=1$ . Associativity and the identity $\bar 1$ are inherited from $\mathbb{Z}/n\mathbb{Z}$ . Inverses exist because $\gcd(a,n)=1$ means $ax\equiv 1$ is solvable by Bézout. Hence $G$ is a finite abelian group with $|G|=\varphi(n)$ .

Step 2. Fix $a\in G$ and consider its cyclic subgroup $\langle a\rangle = \{\bar1, a, a^2, \dots\}$ . Let $d=\operatorname{ord}(a)$ , the smallest positive integer with $a^d\equiv 1$ . Then $|\langle a\rangle| = d$ .

Step 3. By Lagrange's theorem, the order of any subgroup divides the order of the group: $d \mid \varphi(n)$ . Write $\varphi(n)=d\cdot q$ .

Step 4. Therefore

a^{\varphi(n)} = a^{dq} = (a^d)^q \equiv \bar1^{\,q} = \bar1 \pmod n.

This is exactly [4]. $\blacksquare$

∎

ProofEuler's Theorem via Permuted Residues (elementary)

Step 1. Let $r_1,r_2,\dots,r_{\varphi(n)}$ be a reduced residue system — one representative from each class coprime to $n$ .

Step 2. Since $\gcd(a,n)=1$ , the map $r_i\mapsto a r_i \bmod n$ permutes this set: each $ar_i$ is still coprime to $n$ , and $ar_i\equiv ar_j$ forces $r_i\equiv r_j$ (cancel the unit $a$ ). So $\{ar_1,\dots,ar_{\varphi(n)}\}$ is a permutation of $\{r_1,\dots,r_{\varphi(n)}\}$ modulo $n$ .

Step 3. Multiply all elements of each set:

\prod_{i=1}^{\varphi(n)} (a r_i) \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod n \;\Longrightarrow\; a^{\varphi(n)}\prod_i r_i \equiv \prod_i r_i \pmod n.

Step 4. Each $r_i$ is invertible, so $\prod_i r_i$ is a unit and may be cancelled, yielding $a^{\varphi(n)}\equiv 1\pmod n$ . $\blacksquare$

∎

mathematician · Leonhard Euler | 1707–1783

The Swiss polymath Euler introduced the totient (he wrote it as $\pi D$ for a number $D$ ) while extending Fermat's little theorem to composite moduli, publishing the result in Theoremata arithmetica nova methodo demonstrata (1763). Across an unmatched output of nearly 900 works, Euler founded analytic number theory, introduced the zeta function and its product over primes, and codified the notation ( $e$ , $i$ , $\Sigma$ , $f(x)$ ) that students still use. The symbol $\varphi$ for the totient was later popularized by Gauss in Disquisitiones Arithmeticae (1801), where the function received its systematic treatment.

🧠 Intuition

Think of $\varphi(n)$ as a sieve count. Start with all $n$ integers from $1$ to $n$ ; the factor $(1-1/p)$ in [2] discards exactly the fraction $1/p$ that are divisible by $p$ . Because divisibility by distinct primes is "independent" (a probabilistic shadow of the Chinese Remainder Theorem), you simply multiply the surviving fractions. For Euler's theorem, picture the units modulo $n$ as beads on a finite necklace. Multiplying everything by a unit $a$ just rotates the necklace — it relabels the beads without losing any. Since the necklace has $\varphi(n)$ beads, repeating the rotation $\varphi(n)$ times (i.e. raising to the $\varphi(n)$ power) lands you exactly back where you started.

Figure

Sieving the totient: integers 1–12 with those coprime to 12 highlighted

ExampleComputing φ(360)

Given: $n = 360$ .

Step 1 — Factor: $360 = 2^3\cdot 3^2\cdot 5$ .

Step 2 — Apply product form [2]:

\varphi(360)=2^{3-1}(2-1)\cdot 3^{2-1}(3-1)\cdot 5^{1-1}(5-1) = 4\cdot1\;\cdot\;3\cdot2\;\cdot\;1\cdot4.

Step 3 — Multiply: $4\cdot 6\cdot 4 = 96$ .

Check via fractions: $360\cdot(1-\tfrac12)(1-\tfrac13)(1-\tfrac15)=360\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45=96.$ ✓

\boxed{\varphi(360) = 96}

ExampleUsing Euler's Theorem to find the last two digits of

7^{803}

Given: compute $7^{803}\bmod 100$ (the last two digits in base 10).

Step 1 — Totient of modulus: $100=2^2\cdot5^2$ , so $\varphi(100)=100(1-\tfrac12)(1-\tfrac15)=100\cdot\tfrac12\cdot\tfrac45=40$ .

Step 2 — Check coprimality: $\gcd(7,100)=1$ , so Euler's theorem [4] gives $7^{40}\equiv1\pmod{100}$ .

Step 3 — Reduce the exponent mod 40: $803 = 40\cdot20 + 3$ , so $7^{803}=(7^{40})^{20}\cdot7^3\equiv 7^3\pmod{100}$ .

Step 4 — Evaluate: $7^3 = 343 \equiv 43 \pmod{100}$ .

\boxed{7^{803}\equiv 43 \pmod{100}\quad(\text{last two digits} = 43)}

⚠️ Common mistake

Euler's theorem requires coprimality. The congruence $a^{\varphi(n)}\equiv 1\pmod n$ holds only when $\gcd(a,n)=1$ . If $a$ shares a factor with $n$ , $a$ is not a unit and the conclusion generally fails — for such cases use the Carmichael function $\lambda(n)$ or handle prime-power factors separately. Also: reducing exponents works modulo $\varphi(n)$ , not modulo $n$ . To simplify $a^e\bmod n$ , reduce $e$ modulo $\varphi(n)$ (when $\gcd(a,n)=1$ ), never modulo $n$ itself.

Counterexample

Take $n=6$ and $a=4$ . Here $\gcd(4,6)=2\ne1$ , and $\varphi(6)=2$ . Euler's theorem would predict $4^{2}\equiv1\pmod6$ , but $4^2=16\equiv 4\pmod 6$ , not $1$ . The hypothesis fails, so the conclusion fails. Indeed $4^k\equiv4\pmod6$ for all $k\ge1$ — the powers of $4$ never reach $1$ .

Counterexample

$\varphi$ is not completely multiplicative. One might guess $\varphi(mn)=\varphi(m)\varphi(n)$ always, but [3] requires $\gcd(m,n)=1$ . With $m=n=6$ (not coprime): $\varphi(36)=36(1-\tfrac12)(1-\tfrac13)=12$ , whereas $\varphi(6)\varphi(6)=2\cdot2=4\ne12$ .

connection

Euler's theorem is the composite-modulus parent of Fermat's Little Theorem (the prime case) and a direct corollary of Lagrange's Theorem applied to the Group of Units Modulo n. The product formula [2] flows from the Chinese Remainder Theorem and exhibits $\varphi$ as a Multiplicative Function in Analytic Number Theory, where it appears in the Dirichlet Series identity $\sum \varphi(n)n^{-s} = \zeta(s-1)/\zeta(s)$ . The divisor-sum identity [5] is a clean application of Möbius Inversion, giving $\varphi(n)=\sum_{d\mid n}\mu(d)\,n/d$ . Structurally, $\varphi(n)$ measures the order of the abelian group studied in Cyclic Groups and Primitive Roots.

🔬 Where this appears

⏳ History

- 1640 — Pierre de Fermat states (without proof) his little theorem

a^{p}\equiv a\pmod p

in correspondence with Frénicle de Bessy.

- 1736 — Euler publishes the first proof of Fermat's little theorem.

- 1763 — Euler generalizes it to composite moduli, introducing the totient in Theoremata arithmetica nova methodo demonstrata, proving

a^{\varphi(n)}\equiv1\pmod n

.

- 1801 — Gauss systematizes the function in Disquisitiones Arithmeticae, popularizing the notation and proving the divisor-sum identity [5].

- 1832 — Gauss and contemporaries clarify the structure of

(\mathbb{Z}/n\mathbb{Z})^\times

and existence of primitive roots.

- 1879 — J. J. Sylvester coins the term totient.

- 1900s — Robert Carmichael introduces the function

\lambda(n)

, the exact (least universal) exponent, refining Euler's bound.

- 1933 — Edmund Landau and others establish asymptotics:

\sum_{n\le x}\varphi(n)\sim \tfrac{3}{\pi^2}x^2

.

- 1977 — Rivest, Shamir, and Adleman publish RSA, turning

\varphi

and Euler's theorem into the backbone of public-key cryptography.

open-problem

Lehmer's totient problem (1932) asks whether there exists a composite $n$ with $\varphi(n)\mid (n-1)$ . Every prime $p$ satisfies $\varphi(p)=p-1\mid p-1$ ; D. H. Lehmer conjectured no composite does, but the question remains open. Any counterexample must be odd, squarefree, and have at least 15 prime factors exceeding $10^{20}$ . Relatedly, Carmichael's totient conjecture posits that no value of $\varphi$ is attained exactly once — for every $n$ there is some $m\ne n$ with $\varphi(m)=\varphi(n)$ ; verified to enormous bounds but unproven. These show that despite its elementary definition, $\varphi$ still hides deep mysteries.

Euler's Totient Function and Euler's Theorem

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also