18.1 Divisibility

Divisibility is one of the most fundamental concepts in number theory. Nearly every algorithm in computational number theory relies on divisibility properties, whether directly or indirectly. Prime factorization, greatest common divisors, modular arithmetic, congruences, cryptographic protocols, and arithmetic functions all begin with the simple question:

Does one integer divide another?

Despite its apparent simplicity, divisibility provides a rich algebraic structure that allows many difficult problems to be transformed into efficient algorithms. Understanding divisibility thoroughly is therefore essential before studying more advanced number-theoretic techniques.

Problem

Given two integers a and b, determine whether a divides b, and use divisibility properties to reason about more complex arithmetic relationships.

Examples include:

• Is 7 a divisor of 84?
• Does 15 divide 360?
• Is 42 divisible by 6?
• What divisors does 720 have?
• Do two numbers share common divisors?

These questions appear repeatedly throughout algorithm design.

Mathematical Foundation

An integer a divides an integer b if there exists an integer k such that:

b = a × k

This relationship is written as:

a | b

and read as:

a divides b

For example:

3 | 12

because:

12 = 3 × 4

Similarly:

8 | 64

because:

64 = 8 × 8

However:

5 ∤ 18

because no integer k satisfies:

18 = 5 × k

Checking Divisibility

In programming, divisibility is tested using the remainder operator.

A number a divides b exactly when:

b mod a = 0

Python example:

def divides(a, b):
    return b % a == 0

print(divides(7, 84))
print(divides(5, 18))

Output:

True
False

This simple operation forms the basis of countless algorithms.

Basic Properties

Divisibility follows several important algebraic rules.

Reflexivity

Every nonzero integer divides itself.

a | a

Example:

17 | 17

since:

17 = 17 × 1

Divisibility of Zero

Every nonzero integer divides zero.

a | 0

because:

0 = a × 0

For example:

5 | 0
13 | 0
100 | 0

Transitivity

If:

a | b

and

b | c

then:

a | c

Proof:

Suppose:

b = a × m

and:

c = b × n

Then:

c = (a × m) × n

which gives:

c = a × (mn)

Therefore:

a | c

This property is heavily used in correctness proofs.

Closure Under Addition

If:

a | b

and:

a | c

then:

a | (b + c)

and:

a | (b - c)

Proof:

Suppose:

b = ak
c = am

Then:

b + c = a(k + m)

and:

b - c = a(k - m)

Both are multiples of a.

Divisors of an Integer

A divisor of n is any integer that divides n.

Example:

n = 12

Divisors:

1
2
3
4
6
12

Every divisor appears together with a complementary divisor.

1 × 12
2 × 6
3 × 4

This observation leads to an important optimization.

Instead of checking all integers from:

1 ... n

we only need to search until:

√n

Enumerating Divisors

Naive approach:

def divisors(n):
    result = []

    for i in range(1, n + 1):
        if n % i == 0:
            result.append(i)

    return result

Complexity:

O(n)

A better approach exploits divisor pairs.

from math import isqrt

def divisors(n):
    result = []

    for i in range(1, isqrt(n) + 1):
        if n % i == 0:
            result.append(i)

            if i != n // i:
                result.append(n // i)

    return sorted(result)

Complexity:

O(√n)

For large inputs this improvement is dramatic.

Counting Divisors

Consider:

360 = 2³ × 3² × 5¹

Any divisor is formed by choosing exponents:

2^a × 3^b × 5^c

where:

0 ≤ a ≤ 3
0 ≤ b ≤ 2
0 ≤ c ≤ 1

Choices:

4 × 3 × 2

Therefore:

24 divisors

General rule:

If

n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ

then:

number of divisors
=
(e₁ + 1)(e₂ + 1)...(eₖ + 1)

This formula appears frequently in combinatorial and arithmetic algorithms.

Sum of Divisors

Prime factorization also allows efficient computation of divisor sums.

For:

n = p^e

the divisor sum equals:

1 + p + p² + ... + pᵉ

which is a geometric series.

For a general factorization:

n = p₁^e₁ p₂^e₂ ... pₖ^eₖ

the sum of divisors becomes:

(1+p₁+\cdots+p₁^{e₁})
(1+p₂+\cdots+p₂^{e₂})
...
(1+pₖ+\cdots+pₖ^{eₖ})

This principle forms the basis of many arithmetic functions.

Common Divisors

Consider:

18 = 2 × 3²
24 = 2³ × 3

Shared prime factors:

2 × 3

Therefore the common divisors arise from:

6

This leads naturally to the concept of the Greatest Common Divisor (GCD), which is the subject of the next section.

Applications

Divisibility appears in many practical algorithms:

Application	Use of Divisibility
Prime testing	Detect factors
GCD computation	Find common divisors
Cryptography	Modular arithmetic
Scheduling	Period alignment
Hashing	Modular reduction
Combinatorics	Counting factors
Data structures	Capacity selection
Computational geometry	Lattice properties

Many seemingly unrelated algorithms eventually reduce to divisibility questions.

Complexity Considerations

Task	Complexity
Single divisibility test	O(1)
Enumerate divisors (naive)	O(n)
Enumerate divisors (optimized)	O(√n)
Count divisors from factorization	O(k)
Sum divisors from factorization	O(k)

where k is the number of distinct prime factors.

Common Mistakes

Confusing Division and Divisibility

10 ÷ 3

exists as a real number calculation.

However:

3 ∤ 10

because the quotient is not an integer.

Forgetting Negative Divisors

Mathematically:

3 | 12

and:

-3 | 12

are both true.

Many algorithms restrict attention to positive divisors.

Using O(n) Enumeration

Beginners often search all integers from 1 to n.

Divisor pairing reduces this immediately to:

O(√n)

which becomes crucial when n reaches millions or billions.

Takeaway

Divisibility provides the foundation of computational number theory. A divisor relationship captures whether one integer is an exact multiple of another, and a small collection of divisibility properties enables powerful reasoning about arithmetic structures. Efficient divisor enumeration, divisor counting, and divisor-sum formulas emerge naturally from prime factorization and form essential building blocks for greatest common divisors, modular arithmetic, primality testing, factorization algorithms, and cryptographic systems.