# 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 ${\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.