SP20:Lecture 15 GCD algorithm

From CS2800 wiki

We finished the proof that the base b representation exists. We also discussed base b arithmetic. Finally we introduced Euclid's GCD algorithm, and listed the properties we need to prove to justify calling it the greatest common divisor.

Base b representation

We started this lecture by further discussion of base b representation, which we started last lecture. Recall that the base b interpretation of a sequence of digits is:

If [math]d_k, d_{k-1}, \dots, d_1, d_0 [/math] are all natural numbers satisfying [math]0 \leq d_i \lt b [/math] for all [math]i [/math], then the base b interpretation of [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(d_i)} [/math], written [math](d_kd_{k-1}\cdots{}d_1d_0)_b [/math] is given by [math]\href{/cs2800/wiki/index.php/Base}{(d_i)_b} := \sum_{i} d_ib^i [/math]


For all [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and [math]b \gt 0 [/math], there exists a sequence [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(d_i)} [/math] of digits satisfying [math]a = \href{/cs2800/wiki/index.php/Base}{(d_i)_b} [/math].

Note that this proof contains an algorithm for finding the digits. Note also that The base b representation is unique.

We prove the claim by strong induction on [math]a [/math].

In the base case, we WTS must find a base b representation of 0. The natural choice might be to take the single digit [math]d_0 = 0 [/math]. Then [math]d_0 [/math] is a digit (since [math]0 \lt b [/math]), and clearly [math]0 = \sum d_i b^i = 0 \cdot 1 [/math].

However, when using this proof as an algorithm, it is preferable to take the 'empty' sequence as the representation of 0; otherwise all numbers would have a leading 0. Alternatively, one could give a special case in the inductive step for when [math]a [/math] is already a digit.

For the inductive step, assume that every number less than [math]a [/math] has a base b representation. We wish to show that [math]a [/math] has one also.

We can find the digits by dividing by [math]b [/math]: the last digit [math]d_0 [/math] is given by the remainder, and the rest of the digits are those of the quotient.

Formally, let [math]q := \href{/cs2800/wiki/index.php/Quot}{quot}(a,b) [/math] and [math]r := \href{/cs2800/wiki/index.php/Rem}{rem}(a,b) [/math]. Let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(d_i)'} [/math] be the base b representation of [math]q [/math] (which we know exists by the inductive hypothesis).

Let [math]d_0 := rem(a,b) [/math], and let [math]d_{i+1} := d_i' [/math]. We have

[math]\begin{align} (d_i)_b &= \sum_{i=0}^{k+1} d_i b^i && \href{/cs2800/wiki/index.php/Base_b_representation}{\text{by definition}} \\ &= \sum_{i=1}^{k+1} d_i b^i + d_0b^0 && \href{/cs2800/wiki/index.php?title=Algebra&action=edit&redlink=1}{\text{algebra}} \\ &= \sum_{j=0}^{k} d_{j+1}b^{j+1} + d_0b^0 && \text{by letting j+1 = i} \\ &= b \sum_{j=0}^k d_j'b^j + d_0b^0 && \text{factor out b and use definition of } d_{j+1} \\ &= b (d_j')_b + d_0b^0 = qb + r = a && \href{/cs2800/wiki/index.php/Base_b_interpretation}{\text{by definition}} \\ \end{align} [/math]


As usual, in order to justify calling the base b representation of [math]a [/math] "the" base b representation, we need to prove that it is unique. In fact, it is not necessarily unique if we allow leading 0's (for example, [math](0123)_{10} = (123)_{10} [/math]), but if we rule them out, then we have the following fact:

For all [math]k [/math], if [math]\href{/cs2800/wiki/index.php/Base}{(d_kd_{k-1}\dots{}d_1d_0)_b} = \href{/cs2800/wiki/index.php/Base}{(d_k'd_{k-1}'\dots{}d_1'd_0')_b} [/math] and if [math]d_k \neq 0 [/math] and if [math]d_k' \neq 0 [/math] then [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(d_i)} = \href{/cs2800/wiki/index.php/Sequence_notation}{(d_i')} [/math].

The proof is left as an exercise. Use induction on [math]k [/math] and the fact that The quotient and remainder are unique.

Arithmetic in base b

You are already familiar with several digit-by-digit algorithms for working with decimal numbers, such as long addition, long multiplication, and long division.

It turns out that these algorithms also work in base b; one just needs to represent digits in base [math]b [/math]. For example, to add [math](124)_7 [/math] and [math](66)_7 [/math], we can add them digit by digit, starting from the right, and handling carries appropriately. We would add 6 and 4 to get the number 10, which is represented by [math](13)_7 [/math]; we would keep the 3 and carry the 1. We would then add the carry and the second digits to get [math]2 + 6 + 1 = 9 = (12)_7 [/math]; again we keep the 2 and carry the 1. Finally we add the third digit and the carry to get the third digit 2; this gives us [math](124)_7 + (66)_7 = (223)_7 [/math].

1 2 4
+ 6 6     (base 7)
2 2 3

You could prove that these algorithms all work using induction.

GCD algorithm

An important technical tool for our study of number theory is the greatest common divisor of two numbers. Here we present an efficient algorithm for computing it:

Definition: gcd
Euclid's GCD algorithm is the function [math]\href{/cs2800/wiki/index.php/Gcd}{gcd} : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%C3%97}{×} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] which is given as follows: [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,0) := a [/math], and for [math]b \gt 0 [/math], [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) = \href{/cs2800/wiki/index.php?title=G&action=edit&redlink=1}{g}(b,r) [/math] where [math]r = \href{/cs2800/wiki/index.php/Rem}{rem}(a,b) [/math].

This function is a good inductively defined function because by definition, [math]\href{/cs2800/wiki/index.php/Rem}{rem}(a,b) \lt b [/math], so the second argument is decreasing in the inductive definition.

The algorithm can be extended to operate on negative integers by simply taking the gcd of the absolute values of its arguments.

In order to justify calling [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) [/math] the "greatest common divisor", we should check that gcd(a,b) is a common divisor of a and b and gcd(a,b) is greater than all other common divisors of a and b.