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)
\begin{align} r_{t-1} = r_tq_{t+1} \quad \mathbf{and} \quad (a , b) = r_t \quad , \quad t \in \mathbb{Z} \end{align}

## Proof of the Euclidean Algorithm

• Proof: For the set of equations:
(11)
\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}
• It follows that
(12)
$$0 = r_{t+1} < ... < r2 < r1 < b$$
• The sequence must terminate as if it doesn't terminate, then the division algorithm can be applied again setting the remainder to the new value of b. Thus, it can be applied that:
(13)
$$(a , b) = (b , r) = (r, r_1) = (r_1 , r_2) = ... = (r_{t-1} , r_{t}) = r_t$$