Integer Divisibility

Definition: Let $a, b \in \mathbb{Z}$. Then $b$ is said to be Divisible by $a$, or, $a$ is said to Divide $b$ written $a \mid b$ if there exists a $q \in \mathbb{Z}$ such that $aq = b$. The number $a$ is said to be a Divisor of $b$ and $b$ is said to be a Multiple of $a$. If there does not exist an $q \in \mathbb{Z}$ such that $aq = b$ then we say that $a$ does not divide $b$, or, $b$ is not divisible by $a$ denoted $a \not \mid b$.

For example, the number $a = 2$ divides $b = 6$ since for $q = 3$ we have that $aq = b$, so we write $a \mid b$. However, the number $a = 2$ does not divide any odd number $b = 2n + 1$ for $n \in \mathbb{Z}$, so in this case we have that $a \not \mid b$, i.e., $2 \not \mid (2n + 1)$ for all integers $n$.

We will now look at some rather elementary proofs regarding the divisibility of integers.

Theorem 1: Let $a, b, c \in \mathbb{Z}$. a) If $a \mid b$ and $b \mid c$ then $a \mid c$. b) If $a \mid b$ and $a \mid c$ then for all $x, y \in \mathbb{Z}$, $a \mid (bx + cy)$. c) If $a \mid b$ and $a \mid c$ then $a \mid (b + c)$ and $a \mid (b - c)$.

For the following proofs we utilize the fact that the set of integers is closed under standard addition and standard multiplication - that is, if $x, y \in \mathbb{Z}$ then $(x + y) \in \mathbb{Z}$ and $x \cdot y = xy \in \mathbb{Z}$.

• Proof of a) If $a \mid b$ and $b \mid c$ then there exists $q_1, q_2 \in \mathbb{Z}$ such that:

(1)

\begin{align} \quad aq_1 = b \quad \mathrm{and} \quad bq_2 = c. \end{align}

• Substituting the first equation into the second gives us:

(2)

\begin{align} \quad bq_2 = c \\ \quad a(q_1q_2) = c \end{align}

• Since $q_1, q_2 \in \mathbb{Z}$ we have that their product $q_1q_2 \in \mathbb{Z}$. Therefore $a \mid c$. $\blacksquare$

• Proof of b) If $a \mid b$ and $a \mid c$ then there exists $q_1, q_2 \in \mathbb{Z}$ such that:

(3)

\begin{align} \quad aq_1 = b \quad \mathrm{and} \quad aq_2 = c. \end{align}

• Multiply the first equation by $x \in \mathbb{Z}$ and the second equation by $y \in \mathbb{Z}$ to get:

(4)

\begin{align} \quad axq_1 = bx \quad \mathrm{and} \quad ayq_2 = cy. \end{align}

• We now add both of these equations:

(5)

\begin{align} \quad axq_1 + ayq_2 = bx + cy \\ \quad a(xq_1 + yq_2) = bx + cy \end{align}

• Since $q_1, q_2, x, y \in \mathbb{Z}$ we have that $(xq_1 + yq_2) \in \mathbb{Z}$ and so $a \mid (bx + cy)$. $\blacksquare$

• Proof of c) From (b) if we set $x = 1$ and $y = 1$ we get that $a \mid (b + c)$ and if we set $x = 1$ and $y = -1$ we get that $a \mid (b - c)$ as desired. $\blacksquare$