8.1 Divisibility, Primes, and Factorization

Chapter 7 showed how a recursive process repeatedly reduces a problem to a smaller one. Number theory begins with an equally simple reduction question:

> Can one integer be divided into equal groups of another integer with nothing left over?

This question leads to divisibility, prime numbers, and factorization. These ideas will become the raw material for Euclid's algorithm, modular arithmetic, and RSA.

Integers and exact division

The set of integers is

In this section, a divisor will always be nonzero. Let $a,b\in\mathbb Z$ with $a\ne0$. We say that $a$ divides $b$, written

if there exists an integer $k$ such that

The integer $k$ is the exact quotient. The symbol $\mid$ is a relation symbol; it does not mean ordinary division.

Examples

Because

we have $6\mid42$.

Because no integer $k$ satisfies $43=6k$, we write

read “$6$ does not divide $43$.”

Negative values are allowed:

because $30=(-5)(-6)$.

Every nonzero integer divides $0$ because

Also, $1$ and $-1$ divide every integer.

Divisors and multiples describe the same equation

If $a\mid b$, then $a$ is a divisor or factor of $b$, while $b$ is a multiple of $a$.

For example, the positive divisors of $18$ are

The positive multiples of $6$ begin

The divisor list of a fixed nonzero integer is finite, but its list of multiples is infinite.

Factor pairs prevent missed divisors

To list the positive divisors of $36$, pair factors whose product is $36$:

Reading both entries of every pair gives

Once the first factor passes $\sqrt{36}=6$, the same pairs appear in reverse order. This observation will later shorten prime tests.

Basic divisibility rules follow from the definition

The definition $b=ak$ lets us prove useful rules instead of memorizing them.

Transitivity

If $a\mid b$ and $b\mid c$, then $a\mid c$.

Indeed, there are integers $r,s$ such that

Substituting the first equation into the second gives

Because $rs\in\mathbb Z$, the definition proves $a\mid c$.

Integer linear combinations

If $a\mid b$ and $a\mid c$, then for any integers $x$ and $y$,

To see why, write $b=ar$ and $c=as$. Then

This rule is important because Euclid's algorithm will repeatedly replace two numbers by integer combinations without changing their common divisors.

Choose an integer, arrange its factor pairs on a mirrored divisor lattice, and test proposed divisibility arrows by supplying an integer quotient. Perfect squares visibly merge their middle pair, while invalid arrows expose the nonzero remainder that prevents exact division.

Prime and composite numbers

From now on, we focus on positive integers.

A positive integer $p>1$ is prime if its only positive divisors are

Examples are

A positive integer $n>1$ is composite if it has a positive divisor other than $1$ and $n$.

For example,

so $15$ is composite.

The integer $1$ is neither prime nor composite. It has only one positive divisor, not exactly two. Keeping $1$ outside the primes is what makes prime factorization unique.

The integer $2$ is the only even prime. Every even integer larger than $2$ has $2$ as a proper divisor.

Why trial division stops at the square root

Suppose $n$ is composite. Then

for integers $1<a<n$ and $1<b<n$.

If both $a>\sqrt n$ and $b>\sqrt n$, then

contradicting $ab=n$. Therefore at least one factor is at most $\sqrt n$.

So to test whether $n$ is prime, it is enough to try prime divisors not exceeding $\sqrt n$.

Example: testing $97$

Because

we only test the primes $2,3,5,7$.

• $97$ is not even, so $2\nmid97$.

• Its digit sum is $9+7=16$, so $3\nmid97$.

• It does not end in $0$ or $5$, so $5\nmid97$.

• Division by $7$ gives a nonzero remainder.

No prime at most $\sqrt{97}$ divides it, so $97$ is prime.

Prime factorization

A prime factorization writes an integer greater than $1$ as a product of primes.

Repeatedly splitting composite factors gives

Grouping equal primes produces exponent form:

The exponent $3$ means that factor $2$ appears three times; the exponent $2$ means that factor $3$ appears twice.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states:

> Every integer greater than $1$ can be written as a product of primes, and that factorization is unique apart from the order of the factors.

Thus

and

are the same prime factorization in different orders. There is no genuinely different prime inventory for $60$.

The theorem has two claims:

1. Existence: repeated splitting eventually reaches primes because every split uses smaller positive integers.

2. Uniqueness: two prime products for the same integer must contain the same primes with the same exponents.

The first claim echoes Chapter 7's well-founded recursion: a positive integer cannot keep decreasing forever.

Counting positive divisors from a prime factorization

Suppose

where the $p_i$ are distinct primes and the $e_i$ are positive integers.

Every positive divisor chooses an exponent for each prime:

There are $e_i+1$ choices for prime $p_i$. The product principle from Chapter 6 gives the divisor-count formula

The symbol $\tau(n)$ denotes the number of positive divisors of $n$.

For

we obtain

Split composite number blocks into factor-tree branches until every leaf is prime. The forge continuously audits unfinished composite leaves, collapses the tree into an exponent inventory, and generates divisors by choosing exponent coordinates rather than listing them blindly.

Section bridge

Prime factorizations can reveal common factors, but factoring large numbers is expensive. Section 8.2 develops Euclid's algorithm, which finds the greatest common divisor by repeated remainder reduction without factoring either input.