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:

(1)

\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:

(2)

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