Divisibility and Congruences — Laying the Foundations of Number Theory

Starting from the definition of divisibility, we give a rigorous proof of the division algorithm (existence and uniqueness). We then introduce congruences, establish their basic properties and arithmetic rules, and construct the quotient ring Z/nZ.

Folio Official

March 1, 2026

1 Definition of Divisibility

Definition 1 (Divisibility).

For integers

a, b

with

a \neq = 0

, we say that

a

divides

b

if there exists an integer

q

such that

b = a q

. We write

a ∣ b

. If

a

does not divide

b

, we write

a ∤ b

Theorem 2 (Basic properties of divisibility).

For integers

a, b, c

, the following hold:

If $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ (transitivity).
If $a ∣ b$ and $a ∣ c$ , then $a ∣ (b x + cy)$ for all integers $x, y$ (linear combinations).
If $a ∣ b$ and $b ∣ a$ , then $a = \pm b$ .
If $a ∣ b$ and $b \neq = 0$ , then $∣ a ∣ \leq ∣ b ∣$ .

Proof.

(1) Write

b = a q_{1}

and

c = b q_{2}

. Then

c = a (q_{1} q_{2})

, so

a ∣ c

(2) Write

b = a q_{1}

and

c = a q_{2}

. Then

b x + cy = a (q_{1} x + q_{2} y)

, so

a ∣ (b x + cy)

(3) Write

b = a q_{1}

and

a = b q_{2}

. Then

a = a q_{1} q_{2}

, which gives

q_{1} q_{2} = 1

. Since

q_{1}, q_{2}

are integers, we must have

q_{1} = q_{2} = 1

q_{1} = q_{2} = - 1

, so

a = \pm b

(4) Since

b = a q

and

b \neq = 0

, we have

q \neq = 0

, hence

∣ q ∣ \geq 1

. Therefore

∣ b ∣ = ∣ a ∣ \cdot ∣ q ∣ \geq ∣ a ∣

. □

2 The Division Algorithm

Theorem 3 (Division algorithm).

For any integer

a

and positive integer

b

, there exist unique integers

q

(quotient) and

r

(remainder) such that

a = b q + r, 0 \leq r < b .

Proof.

Existence. Consider the set

S = {a - bk ∣ k \in Z, a - bk \geq 0}

. By choosing

k

sufficiently small, we can ensure

a - bk > 0

, so

S \neq = \emptyset

. By the well-ordering principle,

S

has a least element

r = a - b q

. Since

r \in S

, we have

r \geq 0

. Suppose for contradiction that

r \geq b

. Then

r - b = a - b (q + 1) \geq 0

and

r - b < r

, contradicting the minimality of

r

. Therefore

0 \leq r < b

Uniqueness. Suppose

a = b q_{1} + r_{1} = b q_{2} + r_{2}

with

0 \leq r_{1}, r_{2} < b

. Then

b (q_{1} - q_{2}) = r_{2} - r_{1}

, so

b ∣ (r_{2} - r_{1})

. Since

∣ r_{2} - r_{1} ∣ < b

, it follows that

r_{2} - r_{1} = 0

, and hence

q_{1} = q_{2}

. □

3 Congruences: Definition and Basic Properties

Definition 4 (Congruence).

For integers

a, b

and a positive integer

n

, we say that

a

is congruent to

b

modulo

n

n ∣ (a - b)

, and write

a \equiv b (mod n)

Theorem 5 (Congruence is an equivalence relation).

For any integers

a, b, c

and positive integer

n

$a \equiv a (mod n)$ (reflexivity).
If $a \equiv b (mod n)$ , then $b \equiv a (mod n)$ (symmetry).
If $a \equiv b (mod n)$ and $b \equiv c (mod n)$ , then $a \equiv c (mod n)$ (transitivity).

Proof.

(1) Since

n ∣ 0

, we have

a \equiv a

. (2) If

n ∣ (a - b)

, then

n ∣ (b - a)

. (3) If

n ∣ (a - b)

and

n ∣ (b - c)

, then

n ∣ ((a - b) + (b - c)) = n ∣ (a - c)

. □

Theorem 6 (Arithmetic of congruences).

a \equiv b (mod n)

and

c \equiv d (mod n)

, then:

$a + c \equiv b + d (mod n)$ .
$a - c \equiv b - d (mod n)$ .
$a c \equiv b d (mod n)$ .
$a^{k} \equiv b^{k} (mod n)$ for every non-negative integer $k$ .

Proof.

Write

a - b = n s

and

c - d = n t

. (1)

(a + c) - (b + d) = n (s + t)

. (2) Analogous. (3)

a c - b d = a c - b c + b c - b d = c (a - b) + b (c - d) = c n s + bn t = n (cs + b t)

. (4) Follows by induction, applying (3) repeatedly. □

4 The Quotient Ring $Z / n Z$

Definition 7 (Residue class).

For a positive integer

n

, the residue class of an integer

a

modulo

n

\overset{a}{ˉ} = {a + kn ∣ k \in Z}

. The set of all

n

residue classes is denoted

Z / n Z = {\overset{ˉ}{0}, \overset{ˉ}{1}, \dots, \overline{n - 1}}

Remark 8.

The addition

\overset{a}{ˉ} + \overset{ˉ}{b} = \overline{a + b}

and multiplication

\overset{a}{ˉ} \cdot \overset{ˉ}{b} = \overline{ab}

Z / n Z

are well-defined (independent of the choice of representatives), and

Z / n Z

forms a commutative ring. This ring is an integral domain if and only if

n

is prime, in which case

Z / n Z

is a field.

Example 9.

Z /6 Z

, we have

\overset{ˉ}{2} \cdot \overset{ˉ}{3} = \overset{ˉ}{0}

, so

\overset{ˉ}{2}

and

\overset{ˉ}{3}

are zero divisors and

Z /6 Z

is not an integral domain. On the other hand, in

Z /5 Z

every nonzero element is invertible (

\overset{ˉ}{2} \cdot \overset{ˉ}{3} = \overset{ˉ}{1}

\overset{ˉ}{4} \cdot \overset{ˉ}{4} = \overset{ˉ}{1}

), so

Z /5 Z

is a field.

Number Theory Algebra Textbook Divisibility Congruences

Folio Official

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

1 followers·107 articles

Divisibility and Congruences — Laying the Foundations of Number Theory

Folio Official

March 1, 2026

1 Definition of Divisibility

Definition 1 (Divisibility).

For integers

a, b

with

a \neq = 0

, we say that

a

divides

b

if there exists an integer

q

such that

b = a q

. We write

a ∣ b

. If

a

does not divide

b

, we write

a ∤ b

Theorem 2 (Basic properties of divisibility).

For integers

a, b, c

, the following hold:

If $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ (transitivity).
If $a ∣ b$ and $a ∣ c$ , then $a ∣ (b x + cy)$ for all integers $x, y$ (linear combinations).
If $a ∣ b$ and $b ∣ a$ , then $a = \pm b$ .
If $a ∣ b$ and $b \neq = 0$ , then $∣ a ∣ \leq ∣ b ∣$ .

Proof.

(1) Write

b = a q_{1}

and

c = b q_{2}

. Then

c = a (q_{1} q_{2})

, so

a ∣ c

(2) Write

b = a q_{1}

and

c = a q_{2}

. Then

b x + cy = a (q_{1} x + q_{2} y)

, so

a ∣ (b x + cy)

(3) Write

b = a q_{1}

and

a = b q_{2}

. Then

a = a q_{1} q_{2}

, which gives

q_{1} q_{2} = 1

. Since

q_{1}, q_{2}

are integers, we must have

q_{1} = q_{2} = 1

q_{1} = q_{2} = - 1

, so

a = \pm b

(4) Since

b = a q

and

b \neq = 0

, we have

q \neq = 0

, hence

∣ q ∣ \geq 1

. Therefore

∣ b ∣ = ∣ a ∣ \cdot ∣ q ∣ \geq ∣ a ∣

. □

2 The Division Algorithm

Theorem 3 (Division algorithm).

For any integer

a

and positive integer

b

, there exist unique integers

q

(quotient) and

r

(remainder) such that

a = b q + r, 0 \leq r < b .

Proof.

Existence. Consider the set

S = {a - bk ∣ k \in Z, a - bk \geq 0}

. By choosing

k

sufficiently small, we can ensure

a - bk > 0

, so

S \neq = \emptyset

. By the well-ordering principle,

S

has a least element

r = a - b q

. Since

r \in S

, we have

r \geq 0

. Suppose for contradiction that

r \geq b

. Then

r - b = a - b (q + 1) \geq 0

and

r - b < r

, contradicting the minimality of

r

. Therefore

0 \leq r < b

Uniqueness. Suppose

a = b q_{1} + r_{1} = b q_{2} + r_{2}

with

0 \leq r_{1}, r_{2} < b

. Then

b (q_{1} - q_{2}) = r_{2} - r_{1}

, so

b ∣ (r_{2} - r_{1})

. Since

∣ r_{2} - r_{1} ∣ < b

, it follows that

r_{2} - r_{1} = 0

, and hence

q_{1} = q_{2}

. □

3 Congruences: Definition and Basic Properties

Definition 4 (Congruence).

For integers

a, b

and a positive integer

n

, we say that

a

is congruent to

b

modulo

n

n ∣ (a - b)

, and write

a \equiv b (mod n)

Theorem 5 (Congruence is an equivalence relation).

For any integers

a, b, c

and positive integer

n

$a \equiv a (mod n)$ (reflexivity).
If $a \equiv b (mod n)$ , then $b \equiv a (mod n)$ (symmetry).
If $a \equiv b (mod n)$ and $b \equiv c (mod n)$ , then $a \equiv c (mod n)$ (transitivity).

Proof.

(1) Since

n ∣ 0

, we have

a \equiv a

. (2) If

n ∣ (a - b)

, then

n ∣ (b - a)

. (3) If

n ∣ (a - b)

and

n ∣ (b - c)

, then

n ∣ ((a - b) + (b - c)) = n ∣ (a - c)

. □

Theorem 6 (Arithmetic of congruences).

a \equiv b (mod n)

and

c \equiv d (mod n)

, then:

$a + c \equiv b + d (mod n)$ .
$a - c \equiv b - d (mod n)$ .
$a c \equiv b d (mod n)$ .
$a^{k} \equiv b^{k} (mod n)$ for every non-negative integer $k$ .

Proof.

Write

a - b = n s

and

c - d = n t

. (1)

(a + c) - (b + d) = n (s + t)

. (2) Analogous. (3)

a c - b d = a c - b c + b c - b d = c (a - b) + b (c - d) = c n s + bn t = n (cs + b t)

. (4) Follows by induction, applying (3) repeatedly. □

4 The Quotient Ring $Z / n Z$

Definition 7 (Residue class).

For a positive integer

n

, the residue class of an integer

a

modulo

n

\overset{a}{ˉ} = {a + kn ∣ k \in Z}

. The set of all

n

residue classes is denoted

Z / n Z = {\overset{ˉ}{0}, \overset{ˉ}{1}, \dots, \overline{n - 1}}

Remark 8.

The addition

\overset{a}{ˉ} + \overset{ˉ}{b} = \overline{a + b}

and multiplication

\overset{a}{ˉ} \cdot \overset{ˉ}{b} = \overline{ab}

Z / n Z

are well-defined (independent of the choice of representatives), and

Z / n Z

forms a commutative ring. This ring is an integral domain if and only if

n

is prime, in which case

Z / n Z

is a field.

Example 9.

Z /6 Z

, we have

\overset{ˉ}{2} \cdot \overset{ˉ}{3} = \overset{ˉ}{0}

, so

\overset{ˉ}{2}

and

\overset{ˉ}{3}

are zero divisors and

Z /6 Z

is not an integral domain. On the other hand, in

Z /5 Z

every nonzero element is invertible (

\overset{ˉ}{2} \cdot \overset{ˉ}{3} = \overset{ˉ}{1}

\overset{ˉ}{4} \cdot \overset{ˉ}{4} = \overset{ˉ}{1}

), so

Z /5 Z

is a field.

Number Theory Algebra Textbook Divisibility Congruences

Folio Official

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

1 followers·107 articles

Divisibility and Congruences — Laying the Foundations of Number Theory

1 Definition of Divisibility

2 The Division Algorithm

3 Congruences: Definition and Basic Properties

4 The Quotient Ring $Z / n Z$

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

Divisibility and Congruences — Laying the Foundations of Number Theory

1 Definition of Divisibility

2 The Division Algorithm

3 Congruences: Definition and Basic Properties

4 The Quotient Ring $Z / n Z$

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

1 Definition of Divisibility

2 The Division Algorithm

3 Congruences: Definition and Basic Properties

4 The Quotient RingZ/nZ

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

1 Definition of Divisibility

2 The Division Algorithm

3 Congruences: Definition and Basic Properties

4 The Quotient RingZ/nZ

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

4 The Quotient Ring $Z / n Z$

4 The Quotient Ring $Z / n Z$