# Divisibility Relations

## Exact Division

Division of integers does not always produce an integer. For example,

$$
12/3=4
$$

is an integer, while

$$
14/3
$$

is not. Number theory is mainly concerned with exact division, where one integer divides another without leaving a remainder.

Let $a,b\in\mathbb{Z}$, with $a\ne0$. We say that $a$ divides $b$, and write

$$
a\mid b,
$$

if there exists an integer $q$ such that

$$
b=aq.
$$

The integer $q$ is called the quotient.

For example,

$$
3\mid 12
$$

because

$$
12=3\cdot4.
$$

But

$$
3\nmid 14
$$

because no integer $q$ satisfies

$$
14=3q.
$$

## Divisors and Multiples

If

$$
a\mid b,
$$

then $a$ is called a divisor of $b$, and $b$ is called a multiple of $a$.

For example, the positive divisors of $12$ are

$$
1,2,3,4,6,12.
$$

The integer $12$ is a multiple of each of these numbers.

Every nonzero integer divides $0$, since

$$
0=a\cdot0.
$$

Thus

$$
a\mid0
$$

for every $a\ne0$.

On the other hand, $0$ divides no integer under our definition, because division by zero is excluded.

## Basic Properties

Divisibility satisfies several simple but important properties.

First, every nonzero integer divides itself:

$$
a\mid a,
$$

because

$$
a=a\cdot1.
$$

Second, $1$ divides every integer:

$$
1\mid b,
$$

because

$$
b=1\cdot b.
$$

Third, if

$$
a\mid b
$$

and

$$
b\mid c,
$$

then

$$
a\mid c.
$$

Indeed, if $b=am$ and $c=bn$, then

$$
c=(am)n=a(mn),
$$

so $a\mid c$.

This property is called transitivity of divisibility.

## Divisibility and Linear Combinations

A central property of divisibility is compatibility with addition.

If

$$
a\mid b
$$

and

$$
a\mid c,
$$

then

$$
a\mid (b+c).
$$

Indeed, if

$$
b=am
$$

and

$$
c=an,
$$

then

$$
b+c=am+an=a(m+n).
$$

Similarly,

$$
a\mid (b-c).
$$

More generally, if $a\mid b$ and $a\mid c$, then for any integers $x,y$,

$$
a\mid (xb+yc).
$$

The expression

$$
xb+yc
$$

is called an integer linear combination of $b$ and $c$.

This fact is one of the foundations of greatest common divisors, Bézout identities, and the Euclidean algorithm.

## Divisibility and Sign

Divisibility is insensitive to sign.

If

$$
a\mid b,
$$

then

$$
-a\mid b,
\qquad
a\mid -b,
\qquad
-a\mid -b.
$$

For example,

$$
3\mid12,
\qquad
-3\mid12,
\qquad
3\mid(-12).
$$

Because of this symmetry, one often studies positive divisors only.

The positive divisors of $n$ are the positive integers $d$ satisfying

$$
d\mid n.
$$

## Divisibility and Order

If $a\mid b$ and $b\ne0$, then the size of $a$ cannot exceed the size of $b$, unless $a$ differs only by sign from $b$. More precisely, if

$$
a\mid b,
$$

then

$$
|a|\le |b|
$$

whenever $b\ne0$.

Indeed, $b=aq$ for some nonzero integer $q$. Therefore

$$
|b|=|a||q|.
$$

Since $|q|\ge1$, it follows that

$$
|a|\le |b|.
$$

This simple observation is often used to prove finiteness of divisor sets.

## Units

An integer $u$ is called a unit if it divides $1$. Thus $u$ is a unit when there exists an integer $v$ such that

$$
uv=1.
$$

The only units in $\mathbb{Z}$ are

$$
1
\quad\text{and}\quad
-1.
$$

Units are important because they do not change divisibility in an essential way. For example,

$$
a
\quad\text{and}\quad
-a
$$

have exactly the same divisibility behavior up to sign.

## Divisibility as a Relation

Divisibility is a relation on the integers, but it behaves differently from ordinary order.

It is reflexive:

$$
a\mid a
$$

for every nonzero integer $a$.

It is transitive:

$$
a\mid b,\ b\mid c
\quad\Longrightarrow\quad
a\mid c.
$$

However, it is not a linear order. For example, neither

$$
2\mid3
$$

nor

$$
3\mid2
$$

holds.

Thus divisibility defines a partial structure on the integers, not a total ordering.

## Role in Number Theory

Divisibility is the first genuinely number-theoretic relation. It studies how integers contain one another multiplicatively.

Prime numbers are defined by their divisibility properties. Greatest common divisors measure shared divisibility. Congruences are defined through divisibility of differences:

$$
a\equiv b\pmod n
$$

means

$$
n\mid(a-b).
$$

For this reason, divisibility is the gateway from elementary arithmetic to the central ideas of number theory.