SP20:Lecture 15 GCD algorithm
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
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 is already a digit.
Let let . We have, and
As usual, in order to justify calling the base b representation of "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, ), but if we rule them out, then we have the following fact:
Arithmetic in base b
It turns out that these algorithms also work in base b; one just needs to represent digits in base . For example, to add and , 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 ; we would keep the 3 and carry the 1. We would then add the carry and the second digits to get ; 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 .
You could prove that these algorithms all work using induction.
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 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.the "greatest common