4.1 Divisibility

In the next few sections we shall work in $\mathbb{Z}$. We know that we can always add, subtract and multiply two integers to obtain another; but division is more subtle.

As explained in the course overview (Section 1.2), we are on the whole more interested in results which hold in general than in specific instances. For example, the result above that $3|12$ is all very well, and is relevant if we happen to be considering the numbers $3$ and $12$, but it goes no further. By contrast, if we can establish some general result about arbitrary numbers, then we can apply it to lots of different cases; in addition, such results give us a deeper insight into the world of integers than isolated examples ever will.

From this point of view, it is of interest to observe that the last part of Example 4.1.2(ii) above is a special case of the fact that, for each $a\in\mathbb{Z}$, the set of multiples of $a$ is

We shall next state and prove some elementary facts about divisibility. To do so, we require the following concept.

In other words, $|x|$ measures how ‘‘large’’ $x$ is, irrespective of sign; it is clear that $|xy|=|x|\cdot|y|$ for any $x,y\in\mathbb{R}$. Although this definition applies to real numbers in general, we shall only apply it to integers.

Before presenting the proof, we shall consider a numerical example; this will help you understand what exactly the statement of the proposition is and thus what we need to prove; the example may also give you an idea of why the statement is true. Do not, however, get confused by this approach: a numerical example is never a valid substitute for a proof of a statement.

Proof. (i) If $b=qa$ and $c=rb$ for $q,r\in\mathbb{Z}$, then $c=rb=(rq)a$ with $rq\in\mathbb{Z}$, so $a|c$.

(ii) If $b=qa$ for $q\in\mathbb{Z}$, then $bc=q(ac)$, so $ac|bc$.

(iii) ‘‘$\Rightarrow$’’. Suppose that $1=qa$ for some $q\in\mathbb{Z}$. Then $1=|1|=|qa|=|q|\cdot|a|$, so that $|q|=|a|=1$, and hence $a=\pm 1$.

‘‘$\Leftarrow$’’. Suppose that $a=\pm 1$. Then $a|1$ because $1=a\cdot a$.

(iv) ‘‘$\Rightarrow$’’. Suppose that $a|b$ and $b|a$, and choose $q,r\in\mathbb{Z}$ such that $b=qa$ and $a=rb$. If $a=0$ then $b=q\cdot 0=0$ as well; so assume that $a\neq 0$. Since $a=rqa$, we have $a(1-rq)=0$, and as $a\neq 0$, this implies that $1-rq=0$ because $\mathbb{Z}$ has no zero divisors. Thus $rq=1$. From (iii) this gives $q=\pm 1$, so $b=\pm a$.

‘‘$\Leftarrow$’’. Suppose that $b=\pm a$. Then $a|b$ because $b=\pm 1\cdot a$, and $b|a$ because $a=\pm 1\cdot b.$ $\Box$

Although some numbers cannot be divided by others, we are all familiar with the idea of dividing ‘‘as much as possible’’ to get a quotient and a remainder; for example, we might divide $27$ by $4$ to get a quotient of $6$ and a remainder of $3$. This idea turns out to be worth pursuing; to formalize it, we first need to clarify what exactly is going on. In the first place, the statement ‘‘$27$ divided by $4$ equals $6$ with remainder $3$’’ means that $27=6\cdot 4+3.$ However, there are other values which could be used in place of the $6$ and the $3$ in such an equation; for example, we have $27=5\cdot 4+7$, or $27=7\cdot 4+(-1)$. What distinguishes the choice of $6$ and $3$ here is that the remainder should be ‘‘small’’ (less than $4$) and non-negative. The following result shows that we may always ‘‘divide’’ in this way to obtain a unique quotient and a unique remainder; it is called division with remainder.

Proof. We begin with the existence part. Let $q$ be the largest integer such that $q\leqslant a/d,$ and set $r=a-qd\in\mathbb{Z}$. Then $a=qd+r$ holds by definition. Further, the choice of $q$ implies that $qd\leqslant a$, and so $0\leqslant a-qd=r$. Since $q$ is the largest integer less than or equal to $a/d$, we have $a/d<q+1$, so that $a<(q+1)d=qd+d$ and thus $r=a-qd<d$, as required.

To show that $q$ and $r$ are unique, suppose that $a=q_{1}d+r_{1}$ and $a=q_{2}d+r_{2},$ where $q_{1},q_{2}\in\mathbb{Z}$ and $r_{1},r_{2}\in\{0,1,\ldots,d-1\}$. We must show that $q_{1}=q_{2}$ and $r_{1}=r_{2}$. We may suppose that $r_{1}\geqslant r_{2}$. Then $d>r_{1}\geqslant r_{1}-r_{2}\geqslant 0$, and since $r_{1}=a-q_{1}d$ and $r_{2}=a-q_{2}d$, we have

However, the only multiple of $d$ in $\{0,1,\ldots,d-1\}$ is $0$, so we conclude that $r_{1}-r_{2}=0$ and thus also $q_{2}-q_{1}=0$ (because $\mathbb{Z}$ has no zero divisors) as required. $\Box$