Divisibility and Primes

Table of Contents

Divisibility and prime numbers are central themes in number theory. In this chapter, we focus on how integers “fit into” each other (divisibility), and on the special role played by prime numbers.

Divisibility

When we say that one integer “divides” another, we mean that the second can be written as a whole-number multiple of the first.

Formally, for integers $a$ and $b$ with $a \neq 0$, we say that $a$ divides $b$ (written $a \mid b$) if there exists an integer $k$ such that
$$
b = ak.
$$

If no such integer $k$ exists, we write $a \nmid b$.

Some simple examples:

$3 \mid 12$ because $12 = 3 \cdot 4$.
$5 \nmid 12$ because there is no integer $k$ with $12 = 5k$.
$(-4) \mid 20$ because $20 = (-4)\cdot (-5)$.

Note that divisibility is about exact integer multiples: remainders are not allowed.

Basic properties of divisibility

From the definition, several properties follow naturally. These often get used in proofs and problem solving.

Let $a,b,c$ be integers with $a \neq 0$.

Reflexive property
Every nonzero integer divides itself:
$$
a \mid a \quad\text{since } a = a \cdot 1.
$$
Division by $\pm 1$

$1 \mid a$ for every integer $a$ (because $a = 1 \cdot a$).
$(-1) \mid a$ for every integer $a$ (because $a = (-1)\cdot(-a)$).

Zero and divisibility

For any integer $a \neq 0$, we have $a \mid 0$ (since $0 = a \cdot 0$).
But $0$ does not divide any nonzero integer, because $b = 0 \cdot k$ implies $b=0$.

Transitivity
If $a \mid b$ and $b \mid c$, then $a \mid c$.
Indeed, if $b = a k$ and $c = b\ell$, then $c = (ak)\ell = a(k\ell)$.
Compatibility with multiplication
If $a \mid b$, then $a \mid bc$ for any integer $c$.
If $b = ak$, then $bc = (ak)c = a(kc)$.
Stability under sums and differences
If $a \mid b$ and $a \mid c$, then:

$a \mid (b+c)$,
$a \mid (b-c)$,
and more generally, for any integers $m,n$, $a \mid (mb+nc)$.
For example, if \mid 12$ and \mid 20$, then \mid (12+20)=32$ and \mid (20-12)=8$.

These properties allow you to manipulate divisibility statements algebraically in much the same way that you manipulate equations.

Divisibility and remainders

Whenever you divide an integer $b$ by a nonzero integer $a$, you can write:
$$
b = aq + r
$$
where $q$ is the quotient and $r$ is the remainder. The remainder $r$ is chosen so that
$$
0 \le r < |a|.
$$

This is often called the division algorithm (though it is not an algorithm in the step-by-step sense here, just a theorem about how numbers behave).

Divisibility is exactly the case when the remainder is zero:

$a \mid b$ if and only if when $b$ is divided by $a$, the remainder is $0$.

For example, when dividing $23$ by $5$:
$$
23 = 5 \cdot 4 + 3,
$$
so the remainder is $3$, which is not zero, so $5 \nmid 23$.

But
$$
20 = 5 \cdot 4 + 0,
$$
so $5 \mid 20$.

This viewpoint is also the foundation of modular arithmetic, which is treated later when we study congruences.

Tests for divisibility (in base 10)

In everyday work with decimal notation, some quick mental tests for divisibility are useful. These tests come from writing numbers in base 10; they are not “magic rules” but consequences of the way place value works.

We mention a few common ones. Each of these can be proved from the definition of divisibility by writing the number as a sum of powers of $10$ and using the fact that $10$ has certain divisors.

Divisibility by 2
An integer is divisible by $ if and only if its last digit is even (

Divisibility by 5
An integer is divisible by $ if and only if its last digit is

Divisibility by 10
An integer is divisible by $ if and only if its last digit is
Divisibility by 3
An integer is divisible by $ if and only if the sum of its digits is divisible by $.
Example: For 8$, the sum of digits is +3+8=15$, and \mid 15$, so \mid 438$.
Divisibility by 9
Similar to $: an integer is divisible by $ if and only if the sum of its digits is divisible by $.
Example: \,272$ has digit sum +2+7+2 = 18$, and \mid 18$, so \mid 7\,272$.
Divisibility by 4
An integer is divisible by $ if and only if the number formed by its last two digits is divisible by $.
Example: \,316$ ends in $, and $ is divisible by $, so \mid 1\,316$.
Divisibility by 8
An integer is divisible by $ if and only if the number formed by its last three digits is divisible by $.
Example: \,016$ ends in 6 = 16$, and $ is divisible by $, so \mid 5\,016$.
Divisibility by 6
An integer is divisible by $ if and only if it is divisible by both $ and $.
Example: 4$ is even and its digits sum to +3+4=9$ (divisible by $), so \mid 234$.

These tests will be useful when we look for prime numbers and when we factor integers.

Prime and composite numbers

Within the integers, some numbers are “building blocks” from which all positive integers are made.

An integer $p > 1$ is called prime if its positive divisors are only $1$ and $p$ itself.

An integer $n > 1$ that is not prime is called composite; such an $n$ has other positive divisors besides $1$ and $n$.

Some small examples:

Primes: $2,3,5,7,11,13,17,19,23,29,\dots$
Composite: $4 = 2\cdot 2$, $6 = 2\cdot 3$, $8 = 2\cdot 4$, $9 = 3\cdot 3$, $10 = 2\cdot 5$, etc.

By convention, the number $1$ is neither prime nor composite. It has exactly one positive divisor (itself), so it does not fit the usual pattern: primes are required to have exactly two distinct positive divisors.

Even and odd primes

A quick observation:

Any even integer greater than $2$ is divisible by $2$, and hence composite.
Therefore, $2$ is the only even prime number.

All other primes are odd.

Testing for primality (trial division)

Given a positive integer $n > 1$, how can we check if it is prime?

A naive but reliable method is trial division: try dividing $n$ by smaller integers.

However, there is an important simplification: it is enough to test divisors up to $\sqrt{n}$.

Reason:
If $n$ is composite, we can write $n = ab$ with integers $a$ and $b$ satisfying $1 < a \le b < n$. Then
$$
a^2 \le ab = n \quad\Rightarrow\quad a \le \sqrt{n}.
$$
So any nontrivial factor must be at most $\sqrt{n}$.

Thus, to test whether $n$ is prime:

If $n$ has any divisor $d$ with $2 \le d \le \sqrt{n}$, then $n$ is composite.
If no such $d$ exists (i.e. no integer between $2$ and $\sqrt{n}$ divides $n$), then $n$ is prime.

Example: Is $37$ prime?

Compute $\sqrt{37}$, which is a bit more than $6$.
Test divisibility by $2,3,4,5,6$.

$37$ is odd, so not divisible by $2$.
Sum of digits is $10$, not divisible by $3$.
Last two digits $37$ is not divisible by $4$.
Last digit is not $0$ or $5$, so not divisible by $5$.
Not divisible by $2$ or $3$, hence not by $6$.

No divisor is found up to $\sqrt{37}$, so $37$ is prime.

In practice, you can further reduce work by testing only primes as potential divisors, but the core idea remains the same.

Prime factorization

Every composite integer can be written as a product of prime numbers. This expression is called a prime factorization of the integer.

Examples:

$60 = 2 \cdot 2 \cdot 3 \cdot 5 = 2^2 \cdot 3 \cdot 5$.
$84 = 2 \cdot 2 \cdot 3 \cdot 7 = 2^2 \cdot 3 \cdot 7$.
$1\,000 = 2^3 \cdot 5^3$.

To find the prime factorization of $n$ (by hand), a common approach is:

Start with the smallest prime $2$, and divide by $2$ as long as possible.
Move to the next prime ($3$, then $5$, then $7$, etc.), each time dividing as long as possible.
Stop when what remains is $1$, or is itself a prime.

For example, factor $180$:

$180$ is even, so divide by $2$: $180 = 2 \cdot 90$.
$90$ is even, so divide by $2$: $90 = 2 \cdot 45$.
$45$ is not even, try $3$: $45 = 3 \cdot 15$.
$15$ is divisible by $3$: $15 = 3 \cdot 5$.
$5$ is prime, so we are done.

Thus
$$
180 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^2 \cdot 3^2 \cdot 5.
$$

We will later use prime factorizations to compute greatest common divisors and least common multiples, and to study properties like divisibility patterns and number of divisors.

Fundamental Theorem of Arithmetic

The central fact about prime factorization is that it is unique, up to the order of the factors.

Fundamental Theorem of Arithmetic.
Every integer $n > 1$ can be written as a product of prime numbers, and apart from the order of the factors, this factorization is unique.

That is, if
$$
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m,
$$
where each $p_i$ and each $q_j$ is a prime, then $k = m$ and, after reordering, $p_i = q_i$ for all $i$.

For example, you cannot have both
$$
60 = 2^2 \cdot 3 \cdot 5 \quad\text{and}\quad 60 = 2 \cdot 2 \cdot 3 \cdot 3
$$
be correct prime factorizations, because $2^2 \cdot 3 \cdot 5 = 60$ but $2 \cdot 2 \cdot 3 \cdot 3 = 36$. If you correctly factor $60$, you must get $2^2 \cdot 3 \cdot 5$, no matter which method you use.

This theorem justifies speaking of “the” prime factorization of an integer.

Infinitude and distribution of primes

Prime numbers are not only the building blocks of integers; they are also infinitely many and appear scattered among the integers in a seemingly irregular way.

There are infinitely many primes

One of the classic results of number theory, going back to Euclid, is that there is no largest prime.

Theorem. There are infinitely many prime numbers.

A standard proof proceeds by contradiction and uses divisibility. A sketch of the idea is:

Suppose there were only finitely many primes: $p_1, p_2, \dots, p_n$.
Consider the number
$$
N = p_1 p_2 \cdots p_n + 1.
$$
Any prime divisor of $N$ cannot be any of $p_1, \dots, p_n$, because dividing $N$ by $p_i$ would leave remainder $1$.
Therefore $N$ has a prime divisor not in the original list, contradicting the assumption that the list contained all primes.

Thus, primes cannot stop; there must be infinitely many of them.

Density and gaps (informal)

As numbers get larger, primes become less frequent, but they never stop appearing. Between successive primes there can be gaps of various sizes.

For example:

Between $2$ and $3$ there is no composite number.
Between $23$ and $29$ there are $24,25,26,27,28$ — a gap of length $5$.
One can find arbitrarily long stretches of consecutive composite numbers.

On the other hand, there are results (beyond the scope of this chapter) that describe how often primes occur on average. The precise pattern of primes remains a deep and active area of research in number theory.