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·107 articles

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

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·107 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

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

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

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem