# Divisibility

Definition 1: (divides, divisor, multiple)

Let $a,b\in \mathbb {Z}$ , with $a\neq 0$ . We say that "$a$  divides $b$ " or that "$b$  is a multiple of $a$ ", if there exists some $q\in \mathbb {Z}$  such that $b=aq$ .

We write this as $a\mid b$ .

Proposition 1: (some elementary properties of division)

Let $a,\ b,\ c,\ n,\ m$  be integers. Then

1. If $a,\ b>0$  and $a\mid b$ , then $a\leqslant b$ . ▶ $b=|b|=|aq|=a|q|\geqslant a,\ q\in \mathbb {Z} _{>0}$
2. If $a\mid b$  and $b\mid a$ , then $a=\pm b$ .
3. If $a\mid b$  and $a\mid c$ , then $a\mid nb+mc$ .
4. If $a\mid b$  and $b\mid c$ , then $a\mid c$ . ▶ $c=qb=q(ra)=(qr)a$

Examples: $3|6$  because $6=3\times 2$ . However $3\nmid 7$ : if it did, would also divide $1$  (by Proposition 1, point 3), which is impossible (Proposition 1, point 1). Similarly, $3\nmid 8$ .

Proposition 2: (division algorithm)

Let $a,b\in \mathbb {Z}$ , with $a\neq 0$ . Then $b=aq+r$ , for some $q,\ r\in \mathbb {Z}$ , with $0\leqslant r .