Division Algorithm And Euclidean Algorithm

# The Division Algorithm

The division algorithm states that given two positive integers a and b where b ≠ 0, there exists unique integers q and r such that a can be expressed as a product of the integers b, q, plus the integer r, where 0 ≤ r < b. Hence, it follows:

(1)
\begin{align} a = bq + r \quad a, b, r, q \in \mathbb{Z} \end{align}

## Theorem 1: The Division Algorithm

• Proof: Assume that there exists a set of integers denoted as S, such that S = {a, a-b, a-2b, a-3b, …}. Thus, it contains a subset of nonnegative integers, T, such that T = {a, a-b, a-2b, a-3b, …, a-qb}. This implies that: a-(q+1)b < 0. From the least integer principle, this set contains a smallest element, which is a-qb. Note that a-qb < b, as if a-qb > b, then there would be an integer a-(q+1)b that is positive, however, a-(q+1)b is implied negative, so a-qb is in fact the smallest element in set T, and the smallest nonnegative element in set S.
• From rearranging the equation above, it can be said that:
(2)
$$r = a - bq$$
• To prove that q and r are unique integers, suppose there exists a q1 and r1 such that:
(3)
\begin{align} a = bq + r \\ a = bq_1 + r_1 \end{align}
• We can then subtract both equations to obtain:
(4)
$$0 = bq + r - (bq_1 + r_1)$$
• Or namely:
(5)
$$0 = b(q - q_1) + (r - r_1)$$
• Notice that since b | 0, and b | (q - q1), then it follows that b | (r - r1).
• However, it is important to remember that 0 ≤ r < b, and 0 ≤ r1 < b. Hence it can be said that -b < (r - r1) < b. However, there is only one multiple between -b and b, namely 0.
 Note that -b < -b(q - q1) < b (by substitution). Since q, and q1 are integers, for -b < -b(q - q1) < b to be true, (q - q1) = 0, because -b(q - q1) defines a multiple of b. Hence, the only multiple of -b between -b and b is 0, namely (q-q1) = 0, and (r-r1) = 0
(6)
\begin{align} r - r_1 = 0 \quad \mathbf{or} \quad r = r1 \end{align}
• Notice that since (r-r1) =0, the following substitution can be made:
(7)
$$0 = b(q - q_1)$$
• Division of both sides by b can exist because b | 0, and b | b, hence:
(8)
\begin{align} 0 = (q - q_1) \quad q = q_1 \end{align}
• Hence, q is unique as well.

## Lemma 1: When a = bq + r, then (a , b) = (b , r).

• Proof: By the definition of the greatest common divisor, there exists an integer d ≥ 1, such that d = (a , b). Thus it follows that d | a, and d | b. From the equation, a = bq + r, it follows that since d | a and d | bq, then d | r. Additionally, assume that the integer c ≥ 1 is any divisor of b and r such that c = (b , r). It follows that c | b, and c | r, and it follows from a = bq + r, that c | a as well. Therefore, c is a common divisor of a and b (since c | a and c | b), thus there exists a c ≤ d, since d is the greatest common divisor. Hence d = (b , r)

# The Euclidean Algorithm

The Euclidean Algorithm states that for positive integers a and b where b ≠ 0, and:

(9)
\begin{align} a = bq + r \quad 0 \leq r < b \\b = rq_1 + r_1 \quad 0 \leq r_1 < r \\r = r_1q_2 + r_2 \quad 0 \leq r_2 < r_1 \\... \\ r_n = r_{n+1}q_{n+2} + r_{n+2} \quad 0 \leq r_{n+2} < r_{n+1} \end{align}

Then for n being large enough, (e.g. n = t), then it follows such that:

(10)
$$0 = r_{t+1} < ... < r2 < r1 < b$$
$$(a , b) = (b , r) = (r, r_1) = (r_1 , r_2) = ... = (r_{t-1} , r_{t}) = r_t$$