Euler's Totient Function and Euler's Theorem

$ϕ (n)$ counts positive integers ≤ $n$ that are coprime to $n$ (share no common factors except 1)
Euler's Theorem: if $g cd (a, n) = 1$ , then $a^{ϕ (n)} \equiv 1 (mod n)$ generalizes Fermat's Little Theorem
$ϕ (n)$ measures the exponent of periodicity in modular arithmetic—how many multiplications until cycling back to 1
For prime factorization $n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}$ : $ϕ (n) = n \prod (1 - 1/ p_{i})$ over prime divisors
Central to RSA cryptosystem security; transforms number theory from isolated results into coherent predictive theory
The multiplicative group modulo $n$ has order $ϕ (n)$ , linking counting to group structure

Euler's Totient Function and Euler's Theorem

Overview

ϕ (n)

, counts how many positive integers up to

n

are relatively prime to

n

—that is, share no common factors with

n

except 1. This seemingly simple counting question turns out to be one of the most fundamental objects in number theory, connecting divisibility, modular arithmetic, prime factorization, and the structure of multiplicative groups. The totient function appears throughout modern mathematics and computer science, from cryptography to abstract algebra, making it essential knowledge for any student of pure or applied mathematics.

The power of the totient function becomes fully apparent through Euler's Theorem, which generalizes Fermat's Little Theorem and provides a deep connection between counting and congruences. Euler's Theorem states that if $a$ and $n$ are coprime, then $a^{ϕ (n)} \equiv 1 (mod n)$ . This elegant result reveals that the totient function measures the exponent of periodicity in modular arithmetic—it tells us exactly how far we need to raise numbers before they cycle back to 1 modulo $n$ .

Leonhard Euler introduced both the totient function and his theorem in the 1760s, building on Fermat's work from a century earlier. These contributions transformed number theory from a collection of isolated observations into a coherent theory with predictive power. The totient function would later prove central to the RSA cryptosystem, making it one of the rare mathematical concepts that directly protects digital communications worldwide.

The totient function $ϕ (n)$ counts coprime residues and simultaneously reveals the multiplicative order structure modulo $n$ : every number coprime to $n$ returns to 1 after exactly $ϕ (n)$ multiplications.

Euler's Totient Function: For a positive integer

n

, the Euler totient function (or Euler phi function) is defined as

ϕ (n) = ∣ {k \in Z : 1 \leq k \leq n and g cd (k, n) = 1} ∣

That is,

ϕ (n)

counts the number of integers between 1 and

n

(inclusive) that are relatively prime to

n

. Euler's Theorem: If

n

is a positive integer and

a

is an integer with

g cd (a, n) = 1

, then

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

Core Theory

Main Results

Theorem 1 (Multiplicativity of

ϕ

): If

g cd (m, n) = 1

, then

ϕ (mn) = ϕ (m) ϕ (n)

. Theorem 2 (Explicit Formula): If

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}

is the prime factorization of

n

, then

ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) = n (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{k}})

Theorem 3 (Euler's Theorem): If

g cd (a, n) = 1

, then

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

. Theorem 4 (Prime Power Formula): For a prime

p

and positive integer

k

ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1)

Proof of Theorem 4: Among the integers

1, 2, 3, \dots, p^{k}

, exactly those that are multiples of

p

share a common factor with

p^{k}

. The multiples of

p

in this range are

p, 2 p, 3 p, \dots, p^{k - 1} \cdot p

, of which there are

p^{k - 1}

. Therefore,

ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1)

Proof of Theorem 1: We use the Chinese Remainder Theorem. Since

g cd (m, n) = 1

, the map

f : Z / mn Z \to Z / m Z \times Z / n Z

given by

f (x mod mn) = (x mod m, x mod n)

is a ring isomorphism. An element

x

is coprime to

mn

if and only if

x

is coprime to both

m

and

n

. Under the isomorphism

f

, the units modulo

mn

correspond exactly to pairs

(u, v)

where

u

is a unit modulo

m

and

v

is a unit modulo

n

. There are

ϕ (m)

choices for

u

and

ϕ (n)

choices for

v

, giving

ϕ (mn) = ϕ (m) ϕ (n)

. Proof of Theorem 2: By Theorem 1,

ϕ

is multiplicative, so

ϕ (n) = ϕ (p_{1}^{a_{1}}) ϕ (p_{2}^{a_{2}}) \dots ϕ (p_{k}^{a_{k}})

By Theorem 4,

ϕ (p_{i}^{a_{i}}) = p_{i}^{a_{i}} (1 - \frac{1}{p _{i}})

. Therefore,

ϕ (n) = i = 1 \prod k p_{i}^{a_{i}} (1 - \frac{1}{p _{i}}) = (i = 1 \prod k p_{i}^{a_{i}}) i = 1 \prod k (1 - \frac{1}{p _{i}}) = n p ∣ n \prod (1 - \frac{1}{p})

Proof of Theorem 3 (Euler's Theorem): Let

U_{n} = {a \in Z : 1 \leq a \leq n, g cd (a, n) = 1}

be the set of reduced residues modulo

n

. Then

∣ U_{n} ∣ = ϕ (n)

. Claim: If

g cd (a, n) = 1

and

r \in U_{n}

, then

a r mod n \in U_{n}

. Proof of claim: If

d = g cd (a r, n)

, then

d ∣ a r

and

d ∣ n

. Since

g cd (a, n) = 1

, any common divisor of

a r

and

n

must also divide

r

. Thus

d ∣ g cd (r, n) = 1

, so

g cd (a r, n) = 1

Now consider the set ${a r mod n : r \in U_{n}}$ . By the claim, each element is in $U_{n}$ . Moreover, if $a r_{1} \equiv a r_{2} (mod n)$ , then since $g cd (a, n) = 1$ , we can cancel $a$ to get $r_{1} \equiv r_{2} (mod n)$ . Thus multiplication by $a$ gives a bijection $U_{n} \to U_{n}$ .

Let $U_{n} = {r_{1}, r_{2}, \dots, r_{ϕ (n)}}$ . Then ${a r_{1}, a r_{2}, \dots, a r_{ϕ (n)}}$ is a permutation of $U_{n}$ modulo $n$ . Therefore,

(a r_{1}) (a r_{2}) \dots (a r_{ϕ (n)}) \equiv r_{1} r_{2} \dots r_{ϕ (n)} (mod n)

a^{ϕ (n)} (r_{1} r_{2} \dots r_{ϕ (n)}) \equiv r_{1} r_{2} \dots r_{ϕ (n)} (mod n)

Let $R = r_{1} r_{2} \dots r_{ϕ (n)}$ . Since each $r_{i}$ is coprime to $n$ , we have $g cd (R, n) = 1$ . Therefore, we can cancel $R$ from both sides:

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

□

Common Error: Students often try to apply Euler's Theorem without checking that

g cd (a, n) = 1

. For example,

2^{ϕ (6)} = 2^{2} = 4 \neq \equiv 1 (mod 6)

because

g cd (2, 6) = 2 \neq = 1

. The coprimality condition is essential—the theorem simply doesn't hold otherwise. Similarly,

ϕ (n)

is not the number of primes less than

n

(that's the prime counting function

π (n)

). Leonhard Euler (1763) — Introduced the totient function and proved Euler's Theorem in his paper "Theoremata arithmetica nova methodo demonstrata," generalizing Fermat's work and founding modern multiplicative number theory.

Examples and Applications

1

Computing $ϕ (360)$ using the explicit formula:

First, find the prime factorization: $360 = 2^{3} \cdot 3^{2} \cdot 5$ .

Using Theorem 2:

ϕ (360) = 360 (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}

= 360 \cdot \frac{8}{30} = 360 \cdot \frac{4}{15} = 96

We can verify using multiplicativity:

ϕ (360) = ϕ (2^{3}) \cdot ϕ (3^{2}) \cdot ϕ (5) = (2^{2} \cdot 1) \cdot (3 \cdot 2) \cdot (4) = 4 \cdot 6 \cdot 4 = 96

Therefore, there are exactly 96 integers between 1 and 360 that share no common factors with 360.

2

Using Euler's Theorem to find $7^{222} mod 10$ :

First, check: $g cd (7, 10) = 1$ ✓

Compute $ϕ (10) = ϕ (2 \cdot 5) = ϕ (2) ϕ (5) = 1 \cdot 4 = 4$ .

By Euler's Theorem, $7^{4} \equiv 1 (mod 10)$ .

Now divide the exponent: $222 = 4 \cdot 55 + 2$ .

Therefore,

7^{222} = 7^{4 \cdot 55 + 2} = (7^{4})^{55} \cdot 7^{2} \equiv 1^{55} \cdot 49 \equiv 49 \equiv 9 (mod 10)

This technique is fundamental in modular exponentiation algorithms used in cryptography.

Why the coprimality condition is necessary:

Consider $a = 6$ , $n = 9$ . We have $ϕ (9) = 6$ , but $g cd (6, 9) = 3 \neq = 1$ .

Computing: $6^{6} = 46656 = 5184 \cdot 9$ , so $6^{6} \equiv 0 (mod 9)$ .

Clearly $0 \neq \equiv 1 (mod 9)$ , so Euler's Theorem fails completely when the coprimality hypothesis is dropped. The issue is that $6$ is not a unit in $Z /9 Z$ —it's a zero divisor, since $6 \cdot 3 \equiv 0 (mod 9)$ . The proof fundamentally relies on being able to cancel common factors, which requires working within the group of units.

Visual mental model: Imagine a clock with

n

hours. The totient

ϕ (n)

counts which hour marks are "reachable by coprime steps"—if you can walk around the clock taking steps of size

k

where

g cd (k, n) = 1

, you'll eventually hit exactly

ϕ (n)

different hours.

Euler's Theorem says: if you start at 1 and keep multiplying by any coprime number $a$ , after exactly $ϕ (n)$ steps you return to 1. The totient measures the "period of multiplication" modulo $n$ . For prime $p$ , every nonzero element works ( $ϕ (p) = p - 1$ ), which is why Fermat's Little Theorem is cleaner. For composite $n$ , $ϕ (n)$ precisely captures which elements participate in this multiplicative cycling.

Historical Development

Leonhard Euler introduced $ϕ (n)$ in 1763 in his paper Theoremata arithmetica nova methodo demonstrata, though he didn't use the modern notation $ϕ$ (that came later, from Carl Friedrich Gauss's Disquisitiones Arithmeticae in 1801). Euler's motivation was to generalize Fermat's Little Theorem, which Pierre de Fermat had stated (without proof) in 1640 for prime moduli. Fermat claimed that if $p$ is prime and $a$ is not divisible by $p$ , then $a^{p - 1} \equiv 1 (mod p)$ —precisely Euler's Theorem with $n = p$ and $ϕ (p) = p - 1$ .

Euler recognized that the quantity $p - 1$ in Fermat's theorem represented the count of nonzero residues modulo $p$ , and he generalized this counting to arbitrary moduli. His proof used the permutation argument we presented above, showing deep insight into the group structure of units modulo $n$ , though the language of group theory wouldn't be developed for another century.

The explicit product formula for $ϕ (n)$ also appears in Euler's work. Gauss later systematized this theory, proved the multiplicativity rigorously using what we now recognize as the Chinese Remainder Theorem, and established the totient function as a central tool in algebraic number theory. The 20th century saw $ϕ (n)$ take on new importance in cryptography, particularly in the RSA algorithm (1977), where the security relies on the difficulty of computing $ϕ (n)$ without knowing the prime factorization of $n$ .

Connections to Other Areas

Connection to Cyclotomic Polynomials and Galois Theory: The totient function

ϕ (n)

equals the degree of the

n

-th cyclotomic polynomial

Φ_{n} (x)

, which is the minimal polynomial of primitive

n

-th roots of unity. Specifically,

Φ_{n} (x) = \prod_{g c d (k, n) = 1, 1 \leq k \leq n} (x - e^{2 π ik / n})

has degree

ϕ (n)

. This connects elementary number theory to Galois theory: the Galois group of

Q (ζ_{n})

over

Q

(where

ζ_{n}

is a primitive

n

-th root of unity) is isomorphic to

(Z / n Z)^{*}

, the multiplicative group of units modulo

n

, which has order

ϕ (n)

. This bridge between counting coprime integers and field extensions is one of the deepest in mathematics.

Euler's Totient Function and Euler's Theorem