Applications of Congruences and the Group of Units — The Structure of $(\mathbb{Z}/n\mathbb{Z})^*$

We investigate the group of units (Z/nZ)*, derive the formula for Euler's totient function phi(n), and prove Fermat's little theorem, Euler's theorem, and Wilson's theorem. We also introduce the order of an element and discuss primitive roots.

Folio Official

March 1, 2026

1 The Group of Units

Definition 1 (Group of units).

For a positive integer

n

, the set of residue classes

\overset{a}{ˉ} \in Z / n Z

with

g cd (a, n) = 1

is denoted

(Z / n Z)^{*}

. Under multiplication it forms a group, called the group of units (or the group of reduced residue classes).

Proof.

Closure: If

g cd (a, n) = 1

and

g cd (b, n) = 1

, then

g cd (ab, n) = 1

. (Indeed, if a prime

p

divided both

n

and

ab

, then

p ∣ a

p ∣ b

, contradicting coprimality.) Associativity: inherited from integer multiplication. Identity:

\overset{ˉ}{1}

. Inverses: Since

g cd (a, n) = 1

, Bé

a x + n y = 1

, i.e.

a x \equiv 1 (mod n)

, so

\overset{x}{ˉ}

is the inverse of

\overset{a}{ˉ}

. □

2 Euler's Totient Function

Definition 2 (Euler's totient function).

For a positive integer

n

φ (n) = ∣ (Z / n Z)^{*} ∣

, the number of integers

k

with

1 \leq k \leq n

and

g cd (k, n) = 1

, is called Euler's totient function.

Theorem 3 (Formula for the totient function).

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

, then

φ (n) = n p ∣ n \prod (1 - \frac{1}{p}) = i = 1 \prod k p_{i}^{e_{i} - 1} (p_{i} - 1) .

Proof.

We first show

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

. Among the integers

1, 2, \dots, p^{e}

, the multiples of

p

are

p, 2 p, \dots, p^{e - 1} \cdot p

, numbering

p^{e - 1}

in total. Hence

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

. For general

n

, the Chinese remainder theorem (covered in Chapter 6) yields

(Z / n Z)^{*} ≅ \prod_{i} (Z / p_{i}^{e_{i}} Z)^{*}

, from which the multiplicativity of

φ

follows and the formula is obtained. □

3 Fermat's Little Theorem and Euler's Theorem

Theorem 4 (Euler's theorem).

g cd (a, n) = 1

, then

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

Proof.

Let

(Z / n Z)^{*} = {\overset{r}{ˉ}_{1}, \overset{r}{ˉ}_{2}, \dots, \overset{r}{ˉ}_{φ (n)}}

. Since

g cd (a, n) = 1

, the map

\overset{r}{ˉ}_{i} \mapsto \overset{a}{ˉ} \overset{r}{ˉ}_{i}

is a bijection on

(Z / n Z)^{*}

(because

\overset{a}{ˉ}

is invertible). It follows that

\prod_{i} \overset{a}{ˉ} \overset{r}{ˉ}_{i} = \prod_{i} \overset{r}{ˉ}_{i}

, i.e.

\overset{a}{ˉ}^{φ (n)} \prod_{i} \overset{r}{ˉ}_{i} = \prod_{i} \overset{r}{ˉ}_{i}

. Since

\prod_{i} \overset{r}{ˉ}_{i}

is invertible, we can cancel it from both sides to obtain

\overset{a}{ˉ}^{φ (n)} = \overset{ˉ}{1}

. □

Corollary 5 (Fermat's little theorem).

For a prime

p

and an integer

a

with

p ∤ a

, we have

a^{p - 1} \equiv 1 (mod p)

Proof.

Apply Euler's theorem with

φ (p) = p - 1

. □

4 Wilson's Theorem

Theorem 6 (Wilson's theorem).

An integer

p \geq 2

is prime if and only if

(p - 1)! \equiv - 1 (mod p)

Proof.

(\Rightarrow)

Since

Z / p Z

is a field, the equation

x^{2} \equiv 1 (mod p)

has only the solutions

x \equiv \pm 1

. Among the elements of

(Z / p Z)^{*} = {1, 2, \dots, p - 1}

, only

1

and

p - 1

are their own inverses; the remaining elements pair off into inverse pairs whose products are each

1

. Therefore

(p - 1)! \equiv 1 \cdot (p - 1) \cdot (product of pairs, each 1) \equiv p - 1 \equiv - 1 (mod p)

(\Leftarrow)

We show that

(n - 1)! \neq \equiv - 1 (mod n)

when

n

is composite. Write

n = ab

with

1 < a \leq b < n

. If

a \neq = b

, then both

a

and

b

appear as factors in

(n - 1)!

, so

n ∣ (n - 1)!

and

(n - 1)! \equiv 0 \neq \equiv - 1

. If

a = b

, then

n = a^{2}

with

a \geq 2

, so

2 a \leq n - 1

, meaning both

a

and

2 a

appear as factors in

(n - 1)!

, and the same conclusion holds. □

5 The Order of an Element

Definition 7 (Order).

For

g cd (a, n) = 1

, the smallest positive integer

k

satisfying

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

is called the order of

a

modulo

n

, and is denoted

ord_{n} (a)

Theorem 8.

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

, then

ord_{n} (a) ∣ m

. In particular,

ord_{n} (a) ∣ φ (n)

Proof.

Write

m = ord_{n} (a) \cdot q + r

with

0 \leq r < ord_{n} (a)

. Then

a^{r} = a^{m} \cdot (a^{- ord_{n} (a)})^{q} \equiv 1

. Since

r < ord_{n} (a)

and

ord_{n} (a)

is the smallest positive exponent giving

1

, we must have

r = 0

. □

Number Theory Algebra Textbook Group of Units Euler Totient Function

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·105 articles

Applications of Congruences and the Group of Units — The Structure of $(\mathbb{Z}/n\mathbb{Z})^*$

1 The Group of Units

2 Euler's Totient Function

3 Fermat's Little Theorem and Euler's Theorem

4 Wilson's Theorem

5 The Order of an Element

Share your expertise with the world

More from Folio Official

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry