Euler's Totient Function and Euler's Theorem

Euler's totient function

φ (n)

counts the positive integers up to

n

that are coprime to

n

. Euler's theorem states that if

g cd (a, n) = 1

, then

a^{φ (n)} \equiv 1 (mod n)

. These tools underpin modular arithmetic, cyclic group structure, and the RSA cryptosystem. Introduced by Leonhard Euler in 1763.

The Euler totient function $φ : Z^{+} \to Z^{+}$ assigns to each $n$ the cardinality of the set ${k : 1 \leq k \leq n, g cd (k, n) = 1}$ , equivalently the number of units in the ring $Z / n Z$ . It is the foundation of Euler's theorem, a sweeping generalization of Fermat's little theorem that governs the multiplicative order of integers modulo $n$ . The function is multiplicative (though not completely so), enabling its computation from a number's prime factorization alone. A surprising fact: the average value of $φ (n) / n$ tends to $6/ π^{2}$ , the same constant that gives the probability that two random integers are coprime. These ideas convert abstract group theory into the concrete arithmetic that secures modern digital communication.

The Core Insight

The integers coprime to $n$ form a group under multiplication modulo $n$ — the unit group $(Z / n Z)^{\times}$ — and that group has exactly $φ (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.

Formal Statement

Euler's Totient Function

For a positive integer $n$ , the totient $φ (n)$ is the number of integers $k$ in the range $1 \leq k \leq n$ satisfying $g cd (k, n) = 1$ :

φ (n) = # {k \in Z : 1 \leq k \leq n, g cd (k, n) = 1}

⟳Directly count the residues modulo

n

that have a multiplicative inverse; by convention

φ (1) = 1

since

g cd (1, 1) = 1

Symbols: $n$ is the modulus; $k$ ranges over representatives of residue classes; $g cd$ is the greatest common divisor. Equivalently, $φ (n) = ∣ (Z / n Z)^{\times} ∣$ , the order of the group of units.

Product Formula

If $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{r}^{a_{r}}$ is the prime factorization of $n > 1$ , then

φ (n) = n p ∣ n \prod (1 - \frac{1}{p}) = i = 1 \prod r p_{i}^{a_{i} - 1} (p_{i} - 1)

⟳Compute

φ (p^{a}) = p^{a} - p^{a - 1}

for prime powers, then multiply across distinct primes using multiplicativity (Theorem below).

Symbols: the product $\prod_{p ∣ n}$ runs over distinct prime divisors $p$ of $n$ ; each factor $(1 - 1/ p)$ removes the fraction of integers divisible by $p$ .

Multiplicativity

If $g cd (m, n) = 1$ , then

φ (mn) = φ (m) φ (n) .

⟳The Chinese Remainder Theorem gives a ring isomorphism

Z / mn Z ≅ Z / m Z \times Z / n Z

, which restricts to a bijection of unit groups, so unit counts multiply.

Note: $φ$ is multiplicative but not completely multiplicative; e.g. $φ (4) = 2 \neq = φ (2)^{2} = 1$ .

Euler's Theorem

If $a$ and $n$ are integers with $n \geq 1$ and $g cd (a, n) = 1$ , then

a^{φ (n)} \equiv 1 (mod n) .

⟳

a

represents a unit in

(Z / n Z)^{\times}

, a finite group of order

φ (n)

; apply Lagrange's theorem, whose corollary forces

g^{∣ G ∣} = e

for all

g \in G

When $n = p$ is prime, $φ (p) = p - 1$ and [4] becomes Fermat's little theorem: $a^{p - 1} \equiv 1 (mod p)$ for $p ∤ a$ .

Divisor-Sum Identity (Gauss)

For every positive integer $n$ ,

d ∣ n \sum φ (d) = n .

⟳Partition the

n

fractions

1/ n, 2/ n, \dots, n / n

by their reduced denominator

d ∣ n

; exactly

φ (d)

of them reduce to a fraction with denominator

d

Why It Holds

Euler's Theorem via Group Theory

Step 1. Let

G = (Z / n Z)^{\times}

, the set of residue classes coprime to

n

. Closure holds: if

g cd (a, n) = g cd (b, n) = 1

then

g cd (ab, n) = 1

. Associativity and the identity

\overset{ˉ}{1}

are inherited from

Z / n Z

. Inverses exist because

g cd (a, n) = 1

means

a x \equiv 1

is solvable by Bézout. Hence

G

is a finite abelian group with

∣ G ∣ = φ (n)

. Step 2. Fix

a \in G

and consider its cyclic subgroup

⟨ a ⟩ = {\overset{ˉ}{1}, a, a^{2}, \dots}

. Let

d = ord (a)

, the smallest positive integer with

a^{d} \equiv 1

. Then

∣ ⟨ a ⟩ ∣ = d

. Step 3. By Lagrange's theorem, the order of any subgroup divides the order of the group:

d ∣ φ (n)

. Write

φ (n) = d \cdot q

. Step 4. Therefore

a^{φ (n)} = a^{d q} = (a^{d})^{q} \equiv \overset{ˉ}{1}^{q} = \overset{ˉ}{1} (mod n) .

This is exactly [4].

■

Euler's Theorem via Permuted Residues (elementary)

Step 1. Let

r_{1}, r_{2}, \dots, r_{φ (n)}

be a reduced residue system — one representative from each class coprime to

n

. Step 2. Since

g cd (a, n) = 1

, the map

r_{i} \mapsto a r_{i} mod n

permutes this set: each

a r_{i}

is still coprime to

n

, and

a r_{i} \equiv a r_{j}

forces

r_{i} \equiv r_{j}

(cancel the unit

a

). So

{a r_{1}, \dots, a r_{φ (n)}}

is a permutation of

{r_{1}, \dots, r_{φ (n)}}

modulo

n

. Step 3. Multiply all elements of each set:

i = 1 \prod φ (n) (a r_{i}) \equiv i = 1 \prod φ (n) r_{i} (mod n) ⟹ a^{φ (n)} i \prod r_{i} \equiv i \prod r_{i} (mod n) .

Step 4. Each

r_{i}

is invertible, so

\prod_{i} r_{i}

is a unit and may be cancelled, yielding

a^{φ (n)} \equiv 1 (mod n)

■

Leonhard Euler | 1707–1783

The Swiss polymath Euler introduced the totient (he wrote it as $π 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$ , $Σ$ , $f (x)$ ) that students still use. The symbol $φ$ for the totient was later popularized by Gauss in Disquisitiones Arithmeticae (1801), where the function received its systematic treatment.

Building Intuition

Think of $φ (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 $φ (n)$ beads, repeating the rotation $φ (n)$ times (i.e. raising to the $φ (n)$ power) lands you exactly back where you started.

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

Worked Examples

Computing φ(360)

Given:

n = 360

. Step 1 — Factor:

360 = 2^{3} \cdot 3^{2} \cdot 5

. Step 2 — Apply product form [2]:

φ (360) = 2^{3 - 1} (2 - 1) \cdot 3^{2 - 1} (3 - 1) \cdot 5^{1 - 1} (5 - 1) = 4 \cdot 1 \cdot 3 \cdot 2 \cdot 1 \cdot 4.

Step 3 — Multiply:

4 \cdot 6 \cdot 4 = 96

. Check via fractions:

360 \cdot (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96.

✓

φ (360) = 96

Using Euler's Theorem to find the last two digits of $7^{803}$

Given: compute

7^{803} mod 100

(the last two digits in base 10). Step 1 — Totient of modulus:

100 = 2^{2} \cdot 5^{2}

, so

φ (100) = 100 (1 - \frac{1}{2}) (1 - \frac{1}{5}) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40

. Step 2 — Check coprimality:

g cd (7, 100) = 1

, so Euler's theorem [4] gives

7^{40} \equiv 1 (mod 100)

. Step 3 — Reduce the exponent mod 40:

803 = 40 \cdot 20 + 3

, so

7^{803} = (7^{40})^{20} \cdot 7^{3} \equiv 7^{3} (mod 100)

. Step 4 — Evaluate:

7^{3} = 343 \equiv 43 (mod 100)

7^{803} \equiv 43 (mod 100) (last two digits = 43)

Common Misconceptions

Euler's theorem requires coprimality. The congruence

a^{φ (n)} \equiv 1 (mod n)

holds only when

g cd (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

λ (n)

or handle prime-power factors separately. Also: reducing exponents works modulo

φ (n)

, not modulo

n

. To simplify

a^{e} mod n

, reduce

e

modulo

φ (n)

(when

g cd (a, n) = 1

), never modulo

n

itself.

Take $n = 6$ and $a = 4$ . Here $g cd (4, 6) = 2 \neq = 1$ , and $φ (6) = 2$ . Euler's theorem would predict $4^{2} \equiv 1 (mod 6)$ , but $4^{2} = 16 \equiv 4 (mod 6)$ , not $1$ . The hypothesis fails, so the conclusion fails. Indeed $4^{k} \equiv 4 (mod 6)$ for all $k \geq 1$ — the powers of $4$ never reach $1$ .

φ

is not completely multiplicative. One might guess

φ (mn) = φ (m) φ (n)

always, but [3] requires

g cd (m, n) = 1

. With

m = n = 6

(not coprime):

φ (36) = 36 (1 - \frac{1}{2}) (1 - \frac{1}{3}) = 12

, whereas

φ (6) φ (6) = 2 \cdot 2 = 4 \neq = 12

Connections

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 $φ$ as a Multiplicative Function in Analytic Number Theory, where it appears in the Dirichlet Series identity $\sum φ (n) n^{- s} = ζ (s - 1) / ζ (s)$ . The divisor-sum identity [5] is a clean application of Möbius Inversion, giving $φ (n) = \sum_{d ∣ n} μ (d) n / d$ . Structurally, $φ (n)$ measures the order of the abelian group studied in Cyclic Groups and Primitive Roots.

Real-World Applications

RSA cryptography. Key generation chooses $n = pq$ and a public exponent $e$ ; the private exponent satisfies $e d \equiv 1 (mod φ (n))$ , and decryption $m^{e d} \equiv m (mod n)$ relies directly on Euler's theorem. Security rests on $φ (n)$ being hard to compute without factoring $n$ .
Diffie–Hellman key exchange. Operates in a cyclic group whose order is $φ (p) = p - 1$ for prime modulus $p$ ; exponent arithmetic is taken modulo this totient.
Random number generators. Linear congruential and multiplicative generators achieve full period using primitive roots, whose existence depends on the structure counted by $φ$ .
Cyclic redundancy and modular hashing. Period analysis of modular power sequences uses orders dividing $φ (n)$ .
Digital signatures (RSA, Rabin). Verification re-exponentiation again invokes $a^{φ (n)} \equiv 1$ .
Computing modular inverses fast. When $g cd (a, n) = 1$ , $a^{- 1} \equiv a^{φ (n) - 1} (mod n)$ , an alternative to the extended Euclidean algorithm.
Music and gear design / cycle counting. The number of distinct necklaces and rotational symmetries is counted with Burnside's lemma, in which totients of cycle lengths appear.

Historical Development

1640 — Pierre de Fermat states (without proof) his little theorem $a^{p} \equiv a (mod 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^{φ (n)} \equiv 1 (mod 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 $(Z / n Z)^{\times}$ and existence of primitive roots.
1879 — J. J. Sylvester coins the term totient.
1900s — Robert Carmichael introduces the function $λ (n)$ , the exact (least universal) exponent, refining Euler's bound.
1933 — Edmund Landau and others establish asymptotics: $\sum_{n \leq x} φ (n) \sim \frac{3}{π ^{2}} x^{2}$ .
1977 — Rivest, Shamir, and Adleman publish RSA, turning $φ$ and Euler's theorem into the backbone of public-key cryptography.

Subtleties & Limits

Lehmer's totient problem (1932) asks whether there exists a composite

n

with

φ (n) ∣ (n - 1)

. Every prime

p

satisfies

φ (p) = p - 1 ∣ 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

1 0^{20}

. Relatedly, Carmichael's totient conjecture posits that no value of

φ

is attained exactly once — for every

n

there is some

m \neq = n