# Divisibility

Definition 1: (divides, divisor, multiple)

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

We write this as ${\displaystyle a\mid b}$ .

Proposition 1: (some elementary properties of division)

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

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

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

Proposition 2: (division algorithm)

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