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:
(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$.