Integer Division

Definition: Let $a, b \in \mathbb{Z}$. We say that $a$ Divides $b$ denoted $a \mid b$ if there exists an integer $d \in \mathbb{Z}$ such that $ad = b$. Otherwise, we say that $a$ does not divide $b$ written $a \not \mid b$.

For example, $a = 3$ divides $b = 21$ written $3 \mid 21$ since if $d = 7$ we have that:

(1)

\begin{align} \quad ad = (3)(7) = 21 = b \end{align}

That said, $a = 4$ does not divide $b = 27$ written $4 \not \mid 27$ since this would imply that $d = 6.75$ but then $d$ is not an integer.

We should note that we do not need to restrict ourselves to only positive integers. For example, $-5$ divides $40$ written $-5 \mid 40$ if we let $d = -8$.

We will now look at some simple theorems regarding integer division.

Theorem 1: a) If $a, b, c \in \mathbb{Z}$, $a \mid b$ and $b \mid c$ then $a \mid c$. b) If $d, a, b \in \mathbb{Z}$, $d \mid a$ and $d \mid b$ then $d \mid (a + b)$. c) If $d, a_1, a_2, ..., a_n \in \mathbb{Z}$ $d \mid a_1$, $d \mid a_2$, …, $d \mid a_n$ then for integers $c_1, c_2, ..., c_n \in \mathbb{Z}$ we have $d \mid (c_1a_1 + c_2a_2 + ... + c_na_n)$.

• Proof of a): Given that $a \mid b$ there exists an $x \in \mathbb{Z}$ such that $ax = b$ and given that $b \mid c$ there exists a $y \in \mathbb{Z}$ such that $by = c$.

• Substituting the first equation into the second equation gives us:

(2)

\begin{align} \quad axy = c \end{align}

• Since $x, y \in \mathbb{Z}$, their product, $xy \in \mathbb{Z}$. Therefore $a \mid c$. $\blacksquare$

• Proof of b) Since $d \mid a$, there exists an $x \in \mathbb{Z}$ such that $dx = a$ and since $d \mid b$, there exists a $y \in \mathbb{Z}$ such that $dy = b$.

• By adding these two equations we get:

(3)

\begin{align} \quad a + b = dx + dy \\ \quad a + b = d(x + y) \end{align}

• Because $x, y \in \mathbb{Z}$, the sum $(x + y) \in \mathbb{Z}$ and so $d \mid (a + b)$. $\blacksquare$

• Proof of c): Since $d \mid a_1$, $d \mid a_2$, …, $d \mid a_n$ there exists integers $x_1, x_2, ..., x_n \in \mathbb{Z}$ such that $dx_1 = a_1$, $dx_2 = a_2$, …, $dx_n = a_n$. For $c_1, c_2, ..., c_n \in \mathbb{Z}$ we multiply corresponding equations by corresponding $c_i$s to get:

(4)

\begin{align} \quad dc_1x_1 = c_1a_1 \\ \quad dc_2x_2 = c_2a_2 \\ \quad \vdots \\ \quad dc_nx_n = c_na_n \end{align}

• Adding all $n$ of these equations together gives:

(5)

\begin{align} \quad dc_1x_1 + dc_2x_2 + ... + dc_nx_n = c_1a_1 + a_2 + ... + c_na_n \\ \quad d(c_1x_1 + c_2x_2 + ... + c_nx_n) = c_1a_1 + c_2a_2 + ... + c_na_n \end{align}

• Since $c_1, c_2, ..., c_n \in \mathbb{Z}$ we have the sum $(c_1 + c_2 + ... + c_n) \in \mathbb{Z}$. Therefore $d \mid (c_1a_1 + c_2a_2 + ... + c_na_n)$. $\blacksquare$