Algebra and Number Theory/Elementary Number Theory

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<a$.

▶