What does it mean to "divide evenly"? Why number theory begins with mod

The modular reduction map is a projection that deliberately discards information. Clocks, days of the week, and the competitive-programming modulus 10^9+7 all share the same algebraic structure. From the definition of divisibility through congruences to the ring Z/nZ, we uncover the reason number theory starts where it does.

Folio Official

March 1, 2026

Open any number theory textbook and, within the first few pages, you will encounter the notation $a \equiv b (mod n)$ . What the textbook rarely pauses to explain is why number theory begins with remainders. In this article we shall see that the mod operation is a deliberate act of forgetting – a projection that discards the quotient and retains only the remainder – and that the arithmetic of clocks, calendars, and competitive-programming problems all rest on exactly the same algebraic foundation.

1 Divisibility: the starting point

Definition 1 (Divisibility).

For integers

a

and

b

, we say that

a

divides

b

, and write

a ∣ b

, if there exists an integer

q

such that

b = q a

Example 2.

3 ∣ 12

(since

12 = 4 \times 3

), but

3 ∤ 7

Divisibility is deceptively simple, yet it carries powerful consequences.

Theorem 3 (Basic properties of divisibility).

For integers

a, b, c

If $a ∣ b$ and $a ∣ c$ , then $a ∣ (b + c)$ and $a ∣ (b - c)$ .
If $a ∣ b$ , then $a ∣ kb$ for every integer $k$ .
If $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ (transitivity).

Each of these is straightforward to prove, but together they express a single essential fact: the divisibility relation is preserved under linear combinations.

2 The Division Theorem: existence and uniqueness of remainders

Theorem 4 (Division Theorem).

For any integer

a

and positive integer

n

, there exist unique integers

q

(quotient) and

r

(remainder) such that

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

Proof.

For existence, consider the set

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

and take

r

to be its smallest element. If

r \geq n

, then

r - n \geq 0

and

r - n < r

, contradicting the minimality of

r

. For uniqueness, suppose

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

. Then

∣ r_{1} - r_{2} ∣ = ∣ q_{2} - q_{1} ∣ n

, and since

0 \leq ∣ r_{1} - r_{2} ∣ < n

, we conclude

r_{1} = r_{2}

. □

This theorem guarantees that the remainder $r$ is well-defined – a fact on which the entire theory of congruences depends.

3 Congruences: focusing on remainders

Definition 5 (Congruence).

For integers

a, b

and a positive integer

n

, we say that

a

is congruent to

b

modulo

n

, and write

a \equiv b (mod n),

n ∣ (a - b)

Remark 6.

The condition

a \equiv b (mod n)

is equivalent to saying that

a

and

b

leave the same remainder when divided by

n

. In other words, a congruence retains only the remainder and discards everything else.

The power of congruences lies in their compatibility with arithmetic.

Theorem 7 (Arithmetic of congruences).

a \equiv a^{'} (mod n)

and

b \equiv b^{'} (mod n)

, then:

$a + b \equiv a^{'} + b^{'} (mod n)$
$a - b \equiv a^{'} - b^{'} (mod n)$
$ab \equiv a^{'} b^{'} (mod n)$

Proof.

Write

n ∣ (a - a^{'})

and

n ∣ (b - b^{'})

. For addition,

(a + b) - (a^{'} + b^{'}) = (a - a^{'}) + (b - b^{'})

, and the claim follows. For multiplication, decompose

ab - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'})

; each term is divisible by

n

. □

4 Everyday mod: clocks, calendars, and $1 0^{9} + 7$

Modular arithmetic pervades daily life.

Example 8 (Clocks).

At 10 a.m., five hours later it is 3 p.m.:

10 + 5 = 15 \equiv 3 (mod 12)

. A clock face is the world of

Z /12 Z

Example 9 (Days of the week).

If today is Wednesday (call it

3

), what day is it ten days from now?

3 + 10 = 13 \equiv 6 (mod 7)

– Saturday. The weekly cycle lives in

Z /7 Z

Example 10 (The modulus

1 0^{9} + 7

in competitive programming).

Competitive programming contests (AtCoder, Codeforces, and others) routinely ask for answers modulo

1 0^{9} + 7

. Why this particular number?

$1 0^{9} + 7$ is a prime. Working modulo a prime guarantees that every nonzero element has a multiplicative inverse, so division is possible (a point we shall develop in a later article).
$1 0^{9} + 7 < 2^{30}$ , so the product of two residues satisfies $(1 0^{9} + 7)^{2} < 2^{62}$ and fits in a 64-bit integer.

5 Mod as information projection

Remark 11.

The essence of the mod operation is information loss by design. The map

a \mapsto a mod n

is a surjection from

Z

onto

{0, 1, \dots, n - 1}

. It throws away the quotient

q

and retains only the remainder

r

What is remarkable is that, despite discarding information, this map preserves both addition and multiplication. In the language of algebra, the natural map

Z \to Z / n Z

is a ring homomorphism.

6 A first look at the ring $Z / n Z$

Equipping the set of remainders ${0, 1, \dots, n - 1}$ with addition and multiplication gives the algebraic structure denoted $Z / n Z$ .

Definition 12 (

Z / n Z

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

, with operations

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

and

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

, is called the residue ring modulo

n

Remark 13.

When

n

is prime,

Z / n Z

is a field: every nonzero element has a multiplicative inverse, and division is available. This is the algebraic reason why the competitive-programming modulus

1 0^{9} + 7

is chosen to be prime.

7 Takeaway

Divisibility $a ∣ b$ is the most fundamental relation in number theory.
Congruences formalize the idea of "looking only at remainders," and they are compatible with addition and multiplication.
The mod operation is a projection that deliberately discards information. Clocks, days of the week, and the modulus $1 0^{9} + 7$ all share the same underlying structure.
$Z / n Z$ endows the world of remainders with an algebraic structure; when $n$ is prime, that structure is a field.

In the next article, we turn to the computation of greatest common divisors – the Euclidean algorithm – and ask why its simple recursion always finds the largest common factor.

Number Theory Mathematics Between the Lines

Folio Official

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

1 followers·107 articles

What does it mean to "divide evenly"? Why number theory begins with mod

Folio Official

March 1, 2026

1 Divisibility: the starting point

Definition 1 (Divisibility).

For integers

a

and

b

, we say that

a

divides

b

, and write

a ∣ b

, if there exists an integer

q

such that

b = q a

Example 2.

3 ∣ 12

(since

12 = 4 \times 3

), but

3 ∤ 7

Divisibility is deceptively simple, yet it carries powerful consequences.

Theorem 3 (Basic properties of divisibility).

For integers

a, b, c

If $a ∣ b$ and $a ∣ c$ , then $a ∣ (b + c)$ and $a ∣ (b - c)$ .
If $a ∣ b$ , then $a ∣ kb$ for every integer $k$ .
If $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ (transitivity).

Each of these is straightforward to prove, but together they express a single essential fact: the divisibility relation is preserved under linear combinations.

2 The Division Theorem: existence and uniqueness of remainders

Theorem 4 (Division Theorem).

For any integer

a

and positive integer

n

, there exist unique integers

q

(quotient) and

r

(remainder) such that

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

Proof.

For existence, consider the set

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

and take

r

to be its smallest element. If

r \geq n

, then

r - n \geq 0

and

r - n < r

, contradicting the minimality of

r

. For uniqueness, suppose

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

. Then

∣ r_{1} - r_{2} ∣ = ∣ q_{2} - q_{1} ∣ n

, and since

0 \leq ∣ r_{1} - r_{2} ∣ < n

, we conclude

r_{1} = r_{2}

. □

This theorem guarantees that the remainder $r$ is well-defined – a fact on which the entire theory of congruences depends.

3 Congruences: focusing on remainders

Definition 5 (Congruence).

For integers

a, b

and a positive integer

n

, we say that

a

is congruent to

b

modulo

n

, and write

a \equiv b (mod n),

n ∣ (a - b)

Remark 6.

The condition

a \equiv b (mod n)

is equivalent to saying that

a

and

b

leave the same remainder when divided by

n

. In other words, a congruence retains only the remainder and discards everything else.

The power of congruences lies in their compatibility with arithmetic.

Theorem 7 (Arithmetic of congruences).

a \equiv a^{'} (mod n)

and

b \equiv b^{'} (mod n)

, then:

$a + b \equiv a^{'} + b^{'} (mod n)$
$a - b \equiv a^{'} - b^{'} (mod n)$
$ab \equiv a^{'} b^{'} (mod n)$

Proof.

Write

n ∣ (a - a^{'})

and

n ∣ (b - b^{'})

. For addition,

(a + b) - (a^{'} + b^{'}) = (a - a^{'}) + (b - b^{'})

, and the claim follows. For multiplication, decompose

ab - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'})

; each term is divisible by

n

. □

4 Everyday mod: clocks, calendars, and $1 0^{9} + 7$

Modular arithmetic pervades daily life.

Example 8 (Clocks).

At 10 a.m., five hours later it is 3 p.m.:

10 + 5 = 15 \equiv 3 (mod 12)

. A clock face is the world of

Z /12 Z

Example 9 (Days of the week).

If today is Wednesday (call it

3

), what day is it ten days from now?

3 + 10 = 13 \equiv 6 (mod 7)

– Saturday. The weekly cycle lives in

Z /7 Z

Example 10 (The modulus

1 0^{9} + 7

in competitive programming).

Competitive programming contests (AtCoder, Codeforces, and others) routinely ask for answers modulo

1 0^{9} + 7

. Why this particular number?

$1 0^{9} + 7$ is a prime. Working modulo a prime guarantees that every nonzero element has a multiplicative inverse, so division is possible (a point we shall develop in a later article).
$1 0^{9} + 7 < 2^{30}$ , so the product of two residues satisfies $(1 0^{9} + 7)^{2} < 2^{62}$ and fits in a 64-bit integer.

5 Mod as information projection

Remark 11.

The essence of the mod operation is information loss by design. The map

a \mapsto a mod n

is a surjection from

Z

onto

{0, 1, \dots, n - 1}

. It throws away the quotient

q

and retains only the remainder

r

What is remarkable is that, despite discarding information, this map preserves both addition and multiplication. In the language of algebra, the natural map

Z \to Z / n Z

is a ring homomorphism.

6 A first look at the ring $Z / n Z$

Equipping the set of remainders ${0, 1, \dots, n - 1}$ with addition and multiplication gives the algebraic structure denoted $Z / n Z$ .

Definition 12 (

Z / n Z

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

, with operations

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

and

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

, is called the residue ring modulo

n

Remark 13.

When

n

is prime,

Z / n Z

is a field: every nonzero element has a multiplicative inverse, and division is available. This is the algebraic reason why the competitive-programming modulus

1 0^{9} + 7

is chosen to be prime.

7 Takeaway

Divisibility $a ∣ b$ is the most fundamental relation in number theory.
Congruences formalize the idea of "looking only at remainders," and they are compatible with addition and multiplication.
The mod operation is a projection that deliberately discards information. Clocks, days of the week, and the modulus $1 0^{9} + 7$ all share the same underlying structure.
$Z / n Z$ endows the world of remainders with an algebraic structure; when $n$ is prime, that structure is a field.

In the next article, we turn to the computation of greatest common divisors – the Euclidean algorithm – and ask why its simple recursion always finds the largest common factor.

Number Theory Mathematics Between the Lines

Folio Official

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

1 followers·107 articles

What does it mean to "divide evenly"? Why number theory begins with mod

1 Divisibility: the starting point

2 The Division Theorem: existence and uniqueness of remainders

3 Congruences: focusing on remainders

4 Everyday mod: clocks, calendars, and $1 0^{9} + 7$

5 Mod as information projection

6 A first look at the ring $Z / n Z$

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

What does it mean to "divide evenly"? Why number theory begins with mod

1 Divisibility: the starting point

2 The Division Theorem: existence and uniqueness of remainders

3 Congruences: focusing on remainders

4 Everyday mod: clocks, calendars, and $1 0^{9} + 7$

5 Mod as information projection

6 A first look at the ring $Z / n Z$

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

1 Divisibility: the starting point

2 The Division Theorem: existence and uniqueness of remainders

3 Congruences: focusing on remainders

4 Everyday mod: clocks, calendars, and109+7

5 Mod as information projection

6 A first look at the ringZ/nZ

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

1 Divisibility: the starting point

2 The Division Theorem: existence and uniqueness of remainders

3 Congruences: focusing on remainders

4 Everyday mod: clocks, calendars, and109+7

5 Mod as information projection

6 A first look at the ringZ/nZ

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

4 Everyday mod: clocks, calendars, and $1 0^{9} + 7$

6 A first look at the ring $Z / n Z$

4 Everyday mod: clocks, calendars, and $1 0^{9} + 7$

6 A first look at the ring $Z / n Z$