Integer Divisibility Review

# Integer Divisibility Review

We will now review some of the recent material regarding integer divisibility.

- On the
**The Well-Ordering Principle of the Natural Numbers**that the Well-Order Principle for the set of natural numbers $\mathbb{N}$ states the following important fact: Every**NONEMPTY**subset of the natural numbers has a least element. That is, if $A \subseteq \mathbb{N}$ and $A \neq \emptyset$ then there exists an element $x \in A$ such that $x \leq y$ for all $y \in A$.

- On the
**Integer Divisibility**we said that if $a, b \in \mathbb{Z}$ then $b$ is**Divisible**by $a$ written $a \mid b$ if there exists an integer $q \in \mathbb{Z}$ such that:

\begin{equation} aq = b \end{equation}

- We then proved some basic properties regarding divisibility which are summarized in the following table:

Property |
---|

(a) If $a \mid b$ and $b \mid c$ then $a \mid c$. |

(b) If $a \mid b$ and $a \mid c$ then for all $x, y \in \mathbb{Z}$, $a \mid (bx + cy)$. |

(c) If $a \mid b$ and $a \mid c$ then $a \mid (b + c)$ and $a \mid (b - c)$. |

- On
**The Division Algorithm**page we looked at a very important algorithm known as the division algorithm. It states that if $a, b \in \mathbb{Z}$ and $b > 0$ then there exists unique integers $q, r \in \mathbb{Z}$ with $0 \leq r < b$ such that:

\begin{align} \quad a = bq + r \end{align}

- For example, consider $a = 12$ and $b = 5$. Then $12 = 5(2) + 2$ where $q = 2$ and $r = 2$.

- On
**The Greatest Common Division Between Integers**page we said that if $a, b \in \mathbb{Z}$ then the**Greatest Common Divisor**of $a$ and $b$ denoted $\gcd (a, b)$ is the integer $d \in \mathbb{Z}$ if $d \mid a$ and $d \mid b$ ($d$ is a common divisor of $a$ and $b$) and if $c $ ]] is any divisor of [[$ a$ and $b$ then $c \leq d$ ($d$ is the greatest of such common divisors).

- We said that the integers $a$ and $b$ are
**Relatively Prime**if $\gcd (a, b) = 1$.