18.4 Modular Arithmetic

Modular arithmetic is the arithmetic of remainders. Instead of tracking the exact value of an integer, we track only its position within a finite cycle. This simple idea transforms many seemingly impossible computations into efficient algorithms and forms the foundation of modern cryptography, hashing, number theory, combinatorics, distributed systems, and competitive programming.

A computer clock provides an intuitive example. If the time is 10 o'clock and we advance 5 hours, the result is 3 o'clock rather than 15 o'clock. The arithmetic wraps around after reaching a fixed boundary.

Modular arithmetic formalizes this behavior.

Problem

Given a positive integer:

m

called the modulus, perform arithmetic while keeping only the remainder after division by m.

Examples:

17 mod 5 = 2
29 mod 7 = 1
100 mod 12 = 4

Instead of working with large integers, computations are performed within a finite set:

0, 1, 2, ..., m-1

This finite structure provides remarkable computational advantages.

Congruence

Two integers are congruent modulo m if they leave the same remainder when divided by m.

Notation:

a ≡ b (mod m)

Definition:

m | (a - b)

In words:

a and b differ by a multiple of m.

Examples:

17 ≡ 2 (mod 5)

because:

17 - 2 = 15

and:

5 | 15

Similarly:

38 ≡ 3 (mod 7)

because:

38 - 3 = 35

and:

7 | 35

Congruence behaves like equality inside modular arithmetic.

Residue Classes

Under modulus:

m = 5

all integers belong to one of five classes:

Class	Members
0	..., -10, -5, 0, 5, 10 ...
1	..., -9, -4, 1, 6, 11 ...
2	..., -8, -3, 2, 7, 12 ...
3	..., -7, -2, 3, 8, 13 ...
4	..., -6, -1, 4, 9, 14 ...

Every integer belongs to exactly one residue class.

Computations move among these classes rather than among infinitely many integers.

Addition Modulo m

Addition behaves naturally.

If:

a ≡ x (mod m)
b ≡ y (mod m)

then:

a + b ≡ x + y (mod m)

Example:

17 + 24

under modulus:

5

Reduce first:

17 ≡ 2
24 ≡ 4

Then:

2 + 4 = 6

Reduce again:

6 ≡ 1 (mod 5)

Result:

17 + 24 ≡ 1 (mod 5)

Subtraction Modulo m

Subtraction follows the same rule.

Example:

18 - 11

modulo:

5

Reduce:

18 ≡ 3
11 ≡ 1

Compute:

3 - 1 = 2

Result:

2

Therefore:

18 - 11 ≡ 2 (mod 5)

Multiplication Modulo m

Multiplication is also preserved.

If:

a ≡ x (mod m)
b ≡ y (mod m)

then:

ab ≡ xy (mod m)

Example:

17 × 24

modulo:

5

Reduce:

17 ≡ 2
24 ≡ 4

Multiply:

2 × 4 = 8

Reduce:

8 ≡ 3

Therefore:

17 × 24 ≡ 3 (mod 5)

Why Reduction Works

Consider:

a = mq + r

Then:

a ≡ r (mod m)

The multiple:

mq

contributes nothing to the remainder.

Only the residue remains.

Consequently we can reduce intermediate results repeatedly without affecting correctness.

This property is crucial for large-number computations.

Modular Arithmetic in Code

A simple helper:

def mod_add(a, b, m):
    return (a + b) % m

def mod_sub(a, b, m):
    return (a - b) % m

def mod_mul(a, b, m):
    return (a * b) % m

Example:

print(mod_add(17, 24, 5))
print(mod_mul(17, 24, 5))

Output:

1
3

Modular Division

Addition, subtraction, and multiplication always work.

Division is different.

In ordinary arithmetic:

6 ÷ 3 = 2

Under modular arithmetic, division requires an inverse.

Suppose we want:

3x ≡ 1 (mod 7)

Try values:

3×5 = 15

and:

15 ≡ 1 (mod 7)

Therefore:

x = 5

We say:

3⁻¹ ≡ 5 (mod 7)

and write:

1/3 ≡ 5 (mod 7)

Division becomes multiplication by an inverse.

When Inverses Exist

An inverse exists precisely when:

gcd(a,m)=1

Example:

3 mod 7

has an inverse.

Because:

gcd(3,7)=1

Example:

4 mod 8

has no inverse.

Because:

gcd(4,8)=4

not:

1

This criterion connects modular arithmetic directly to the Extended Euclidean Algorithm.

Modular Exponentiation

Consider:

7^1000 mod 13

Direct computation is impossible in practice.

Instead, reduce after every multiplication.

Even better, use repeated squaring.

Naive complexity:

O(n)

Fast exponentiation:

O(log n)

Implementation:

def mod_pow(base, exp, mod):
    result = 1

    while exp > 0:
        if exp & 1:
            result = (result * base) % mod

        base = (base * base) % mod
        exp >>= 1

    return result

Example:

print(mod_pow(7, 1000, 13))

Computes efficiently despite the enormous exponent.

Modular Arithmetic Laws

The following identities always hold.

Addition:

(a+b) mod m
=
((a mod m)+(b mod m)) mod m

Subtraction:

(a-b) mod m
=
((a mod m)-(b mod m)) mod m

Multiplication:

(ab) mod m
=
((a mod m)(b mod m)) mod m

Exponentiation:

(a^k) mod m
=
((a mod m)^k) mod m

These rules permit aggressive reduction during computation.

Negative Numbers

Many languages handle negative remainders differently.

Mathematically:

-3 mod 5 = 2

because:

-3 ≡ 2 (mod 5)

since:

5 | (-3 - 2)

When implementing modular arithmetic, always verify how the programming language defines %.

A safe normalization is:

x = ((x % m) + m) % m

which guarantees:

0 ≤ x < m

Applications

Cryptography

RSA, Diffie-Hellman, elliptic curve cryptography, and digital signatures operate almost entirely in modular arithmetic.

Hash Tables

Hash values are frequently reduced:

hash(key) mod table_size

Scheduling

Cyclic schedules naturally use modular arithmetic.

Circular Buffers

Index wrapping:

(i + 1) mod capacity

Number Theory

Congruences, inverses, and arithmetic functions rely on modular computation.

Competitive Programming

Most counting problems use large prime moduli such as:

1,000,000,007

to prevent overflow.

Common Mistakes

Forgetting Reduction

Intermediate values can grow exponentially.

Reduce frequently.

Assuming Division Always Works

Division requires an inverse.

Not every element has one.

Overflow Before Modulo

Computing:

(a × b) mod m

can overflow before reduction.

Special multiplication techniques may be required for large integers.

Mishandling Negative Values

Different languages produce different remainder behavior.

Always normalize when necessary.

Prime Moduli

Prime moduli possess especially useful properties.

If:

p

is prime, every nonzero element has an inverse.

For modulus:

7

the nonzero residues:

1,2,3,4,5,6

all have inverses.

This property makes prime moduli the preferred choice in cryptography and algorithm design.

Takeaway

Modular arithmetic replaces ordinary equality with congruence classes and performs computations within a finite cyclic system. Addition, subtraction, multiplication, and exponentiation behave predictably under reduction, enabling efficient computation with very large integers. Modular inverses, modular exponentiation, and congruence relations form the foundation of cryptography, hashing, combinatorics, and advanced number theory. Understanding modular arithmetic is essential for every topic that follows in this chapter.