# Divisibility

In the following, $\mathbb Z$ will denote the set of all integers, i.e. $\mathbb Z = \{\dots, -3, -2, -1, 0, 1, 2, 3, 4, \dots\}$, and $\mathbb N$ will denote the set of all natural numbers (aka positive integers), $\mathbb N = \{1, 2, 3, 4, 5, \dots\}$.

## 1. Division with remainder

Let $b$ be an integer and $a$ be a natural number. Then there exists a unique pair of integers $(q, r)$, such that $b = qa + r$ and $0 \leq r < a$.

Here $q$ is called the **quotient** and $r$ the **remainder** of dividing $b$ by $a$.
The remainder $r$ is also denoted by $b \operatorname{mod} a$.

Find the quotient $q$ and the remainder $r$ for the following divisions $b/a$. Pay attention to the condition $0 ≤ r < a$.

Write a Python script for finding quotients and remainders given an integer $b$ and a natural number $a$.

## 2. Divisibility

**divides**an integer $b$ if there is an integer $c$ such that $b = ac$. This is denoted by $a \mid b$.

For example, consider the number 6. It divides, e.g., 6, 12, -18, 24, 0 and is divided by 6, -6, 3, -2, 1.

By using the notation from above write down that $6$ is divided by $-2$.

Since $0=0\cdot1$, we can write $0 \mid 0$, i.e. zero divides itself. However, **we can not write** $0 \mid b$ where $b\neq 0$ since there is no such integer $c$ that could provide the equality $b=0\cdot c$.

Among the following numbers, which numbers divide which: $0,\ 1,\ -1,\ 2,\ 4,\ -5,\ 10,\ -10$.

If $a$ is a natural number, then $a$ divides $b$ if and only if $b \operatorname{mod} a = 0$.

This is standard criterion for checking divisibility.

## 3. Lattice of divisibility

In the following let us restrict ourselves to natural numbers.

We can represent all the distinct divisors of a number in a directed graph where there is an arc (aka arrow) from $a$ to $b$ if $a$ divides $b$ and there is no number $c$ (distinct from $a$ and $b$) such that $a$ divides $c$ and $c$ divides $b$.

For instance, consider a graph formed by all the divisors of $12$.

Such a graph is called a **lattice of divisibility**.

Apriori it may not be clear that a lattice of divisibility exists for any given number. One might imagine a divisor $a$ such that for any other divisor $b$ there exists $c$ sitting inbetween $a$ and $b$, i.e., satisfying $a\mid c$ and $c\mid b$.

So, why there is no such divisor? If such a divisor $a$ existed, then taking $c$ in place of $b$ we would find $d$ sitting between $a$ and $c$, then $e$ between $a$ and $d$ and so on. We could go on infinitely. But in practice we cannot go on infinitely.

For instance, if we start with a pair $1\mid 12$ we can quickly discover $1\mid 6$ and $6 \mid 12$ and then discover $1\mid 3$ and $3\mid 6$. Then there is nothing to be put between $1$ and $3$, so there must be an arc from $1$ to $3$.

To understand why this process is finite it is enough to **observe that $a$ can divide $b$ only if $a\leq b$** and for any number $b$ there are only finitely many numbers less than $b$ and greater than $1$, so there are only finitely many divisors of $b$.

Thus, indeed any given number has a lattice of divisibility.

Construct a lattice of divisibility for $24$ by dragging and dropping the given numbers onto their correct locations in the diagram.

A number $a$ divides $b$ if and only if there is a path from $a$ to $b$ in the lattice of divisibility.

This follows from the **transitivity** of divisibility. Namely, if $a$ divides $b$ and $b$ divides $c$ then $a$ also divides $c$.

Transitivity guarantees that there are no directed cycles in the graph. Indeed, let us observe a cycle with an arc from $a$ to $b$ ($a \neq b$):

Since it is a cycle, there is path from $b$ to $a$, i.e. $b \mid a$. And there is arc from $a$ to $b$ meaning $a \mid b$. Recall that from $a \mid b$ follows that **$a \leq b$**. We have also $b \mid a$ meaning **$a \geq b$**. Thus $a=b$ which is contradiction.

- $a | b$ only if $a \leq b$,
- $a | b$ and $b | a$ if and only if $a = b$ (antisymmetry),
- $a | b$ and $b |c$ imply $a | c$ (transitivity).

The divisibility relation is a **partial order**. See Ordered sets for more details on this type of structures.