# Algebra and Number Theory/Printable version

Algebra and Number Theory

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Algebra_and_Number_Theory

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

# 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 .